Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Integer Optimization”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

Dynamic Airspace Configuration

In air traffic management systems, airspace is partitioned into regions in part to distribute the tasks associated with managing air traffic among different systems and people. These regions, as well as the systems and people allocated to each, are changed dynamically so that air traffic can be safely and efficiently managed. It is expected that new air traffic control systems will enable greater flexibility in how airspace is partitioned and how resources are allocated to airspace regions. In this talk, I will begin by providing an overview of some previous work and open questions in Dynamic Airspace Configuration research, which is concerned with how to partition airspace and assign resources to regions of airspace. For example, I will introduce airspace partitioning algorithms based on clustering, integer programming optimization, and computational geometry. I will conclude by discussing the development of a tablet-based tool that is intended to help air traffic controller supervisors configure airspace and controllers in current operations.

airspace↗

Alternative regularizations for Outer-Approximation algorithms for convex MINLP

In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.

Convex Mixed-integer nonlinear programming↗

A satellite system synthesis model for orbital arc allotment optimization

A mixed integer programming formulation of a satellite system synthesis problem if presented, which is referred to as the arc allotment problem (AAP). Each satellite administration is to be allotted a weighted-length segment of the geostationary orbital arc within which its satellites may be positioned at any longitudes. The objective function maximizes the length of the unweighted arc segment allotted to every administration, subject to single-entry co-channel interference restrictions and constraints imposed by the visible arc for each administration. Useful relationships between special cases of AAP and another satellite synthesis problem are established. Solutions to two example problems are presented.

Reilly, Charles H.↗

Autonomous Guidance of Agile Small-scale Rotorcraft

This report describes a guidance system for agile vehicles based on a hybrid closed-loop model of the vehicle dynamics. The hybrid model represents the vehicle dynamics through a combination of linear-time-invariant control modes and pre-programmed, finite-duration maneuvers. This particular hybrid structure can be realized through a control system that combines trim controllers and a maneuvering control logic. The former enable precise trajectory tracking, and the latter enables trajectories at the edge of the vehicle capabilities. The closed-loop model is much simpler than the full vehicle equations of motion, yet it can capture a broad range of dynamic behaviors. It also supports a consistent link between the physical layer and the decision-making layer. The trajectory generation was formulated as an optimization problem using mixed-integer-linear-programming. The optimization is solved in a receding horizon fashion. Several techniques to improve the computational tractability were investigate. Simulation experiments using NASA Ames 'R-50 model show that this approach fully exploits the vehicle's agility.

Mettler, Bernard↗

Stacking-sequence optimization for buckling of laminated plates by integer programming

Integer-programming formulations for the design of symmetric and balanced laminated plates under biaxial compression are presented. Both maximization of buckling load for a given total thickness and the minimization of total thickness subject to a buckling constraint are formulated. The design variables that define the stacking sequence of the laminate are zero-one integers. It is shown that the formulation results in a linear optimization problem that can be solved on readily available software. This is in contrast to the continuous case, where the design variables are the thicknesses of layers with specified ply orientations, and the optimization problem is nonlinear. Constraints on the stacking sequence such as a limit on the number of contiguous plies of the same orientation and limits on in-plane stiffnesses are easily accommodated. Examples are presented for graphite-epoxy plates under uniaxial and biaxial compression using a commercial software package based on the branch-and-bound algorithm.

Haftka, Raphael T.↗

Stacking-sequence optimization for buckling of laminated plates by integer programming

Integer-programming formulations for the design of symmetric and balanced laminated plates under biaxial compression are presented. Both maximization of buckling load for given total thickness, and the minimization of total thickness subject to a buckling constraint are formulated. The design variables that define the stacking sequence of the laminate are zero-one integers. It is shown that the formulation results in a linear optimization problem that can be solved on readily aviable software. Constraints on the stacking sequence such as a limit on the number of contiguous plies of the same orientation and limits on in-plane stiffnesses are easily accommodated. Examples are presented for graphite-epoxy plates under uniaxial and biaxial compression using a commercial software package based on the branch-and-bound algorithm.

Haftka, Raphael T.↗

An Optimization Approach to Support Science Decision Making for Lunar Surface Exploration

Introduction: Scientific exploration is one of the three pillars of NASA’s Moon2Mars architecture, with crew surface extra vehicular activities (EVA) serving a critical enabling function. Development of surface EVA operational planning and execution, specifically integrating science and flight control teams (FCT), is currently being explored through analog scenarios. This integration, exercised, for example, through the Joint EVA and Hu-man Surface Mobility Test Team (JETT), allows for science input on EVA activities in near real-time through a Science Evaluation Room (SER), or Arte-mis science backroom, which integrates with the broader FCT through the Science Officer. The SER works within the FCT to support dynamic EVA planning in response to changes in operational constraints as well as science opportunities and re-prioritization, increasing the mission science return and accelerating the accomplishment of the Moon2Mars science objectives. The SER works within the FCT to provide recommendations to traverse execution in near real-time. One challenge is the requirement to deliver SER inputs to the FCT on operationally relevant timelines. Failure to do so may result in suboptimal execution of science exploration EVAs or even loss of key science objectives. To close this gap, we present a network optimization tool to allow the SER to provide rapid input to the FCT in response to changes in operational constraints or science opportunities. Inputs are predicated on approved science objectives, and clear rationale must be provided to the FCT for any requested change. Accordingly, this tool incorporates the Science Traceability Matrix (STM), SER prioritization scheme, and station characterization and action planning with operational constraints such as duration, traverse speed, and distance to maximize science objectives based on SER priorities, consistent with FCT operational requirements. Method: As a proof of concept, we used an existing linear programing software package used to simulate optimal routes through cellular metabolism. We built a Demonstrative Model with three STM objectives and four stations on a region of the Moon. The objectives were given an arbitrary prioritization and mapped to the stations through four possible crew actions. (Figs. 1 and 2). This station to STM mapping is consistent with the method used by the JETT5 Science Team to develop analog surface EVA science planning. We used a grid system with the landing site at the origin and the four stations placed across the positive x,y quadrant. Actions were assigned to each station and the accomplishment of those actions resulted in a numerical “reward” based on the ability of that action to achieve science objectives. The aggregate reward from each individual STM objective contributes to a global score (Science Yield), weighted by its priority. Operational constraints included a requirement to start and end at the landing site, 5 minutes each for initial station characterization and “clean up,” and variable total EVA time, traverse rate (fixed to 0.5 meters per second in our example), and time to perform each action (10, 5, 7, and 15 min for actions 1, 2, 3, and 4, respectively). Additional constraints and variables will be added in the future (e.g., sample mass, number of stations, traverse route constraints, illumination). Optimization. We converted the connections (arcs) between these stations (nodes) into a mixed integer linear programming optimization problem (arcs = constraints, nodes = variables) with the objective to maximize Science Yield. For any action, the Science Yield is equal to the relevance of that action to an STM objective [3, 2, and 1 point(s) for High, Med., and Low relevance, respectively], multiplied by the STM Objective Priority [3, 2, and 1 point(s) for High, Med., and Low priority, respectively]. This resulted in a model that computes the optimal station and action combination to maximize the Science Yield. These weightings can be adjusted by the SER as desired. Results: We explored three test cases for the Demonstrative Model. First, we set the maximum EVA duration to 120 minutes and computed the optimal route (Fig. 3A). The model suggested per-forming Actions 1 and 2 at Station P01, followed by Actions 1 and 2 at Station P02, and finally Actions 1 and 3 at Station P04 before returning to the Landing Site. Second, we adjusted the STM Objective Priori-ty order and computed the new optimal route (Fig. 3B). Under this situation, the model suggested per-forming all Actions at Station P02 followed by all Actions at Station P03. The previous test cases were relevant to SER planning activities. Next, we explored providing mid-EVA replanning input to the FCT. Scenario: While executing the Route in Fig. 3A the crew finishes at Station P01 and FCT decides that the EVA needs to finish in 45 minutes back at the Landing Site. FCT asks SER to recommend changes to the plan to accommodate this operation-al change. Using the model and incorporating these new constraints (start at Station P01, max. time of 45 min), the model suggested performing Actions 2 and 4 at Station P03 (Fig. 4), requiring 41 minutes to complete and return to the Landing Site. Interestingly, Station 3 was not part of the original route. Using the model, we determined the EVA would need 66 minutes, instead of 45, in order for the original Station P04 to yield a larger Science Yield than Station P03. The parametrization and simulation was per-formed in less than a minute, demonstrating the operational relevance of the approach. Future Efforts: The results from the Demonstrative Model suggest this tool can accelerate SER decision making on operationally relevant timelines. Use in analog activities, such as JETT5 or follow-ons, which have over a dozen stations for a crew to explore and over a dozen actions per station, will provide needed validation of the utility of this tool for planning EVAs, replanning mid-EVA, or planning follow-on EVAs based on previous results. Further integration with FCT execution monitoring tools may provide additional efficiency gains, al-lowing rapid and iterative exploration of operation-al and science decision space by the FCT and SER.

Science Operations↗

Low-complexity wavelet filter design for image compression

Image compression algorithms based on the wavelet transform are an increasingly attractive and flexible alternative to other algorithms based on block orthogonal transforms. While the design of orthogonal wavelet filters has been studied in significant depth, the design of nonorthogonal wavelet filters, such as linear-phase (LP) filters, has not yet reached that point. Of particular interest are wavelet transforms with low complexity at the encoder. In this article, we present known and new parameterizations of the two families of LP perfect reconstruction (PR) filters. The first family is that of all PR LP filters with finite impulse response (FIR), with equal complexity at the encoder and decoder. The second family is one of LP PR filters, which are FIR at the encoder and infinite impulse response (IIR) at the decoder, i.e., with controllable encoder complexity. These parameterizations are used to optimize the subband/wavelet transform coding gain, as defined for nonorthogonal wavelet transforms. Optimal LP wavelet filters are given for low levels of encoder complexity, as well as their corresponding integer approximations, to allow for applications limited to using integer arithmetic. These optimal LP filters yield larger coding gains than orthogonal filters with an equivalent complexity. The parameterizations described in this article can be used for the optimization of any other appropriate objective function.

Majani, E.↗

Blocking reduction of Landsat Thematic Mapper JPEG browse images using optimal PSNR estimated spectra adaptive postfiltering

Two representative sample images of Band 4 of the Landsat Thematic Mapper are compressed with the JPEG algorithm at 8:1, 16:1 and 24:1 Compression Ratios for experimental browsing purposes. We then apply the Optimal PSNR Estimated Spectra Adaptive Postfiltering (ESAP) algorithm to reduce the DCT blocking distortion. ESAP reduces the blocking distortion while preserving most of the image's edge information by adaptively postfiltering the decoded image using the block's spectral information already obtainable from each block's DCT coefficients. The algorithm iteratively applied a one dimensional log-sigmoid weighting function to the separable interpolated local block estimated spectra of the decoded image until it converges to the optimal PSNR with respect to the original using a 2-D steepest ascent search. Convergence is obtained in a few iterations for integer parameters. The optimal logsig parameters are transmitted to the decoder as a negligible byte of overhead data. A unique maxima is guaranteed due to the 2-D asymptotic exponential overshoot shape of the surface generated by the algorithm. ESAP is based on a DFT analysis of the DCT basis functions. It is implemented with pixel-by-pixel spatially adaptive separable FIR postfilters. PSNR objective improvements between 0.4 to 0.8 dB are shown together with their corresponding optimal PSNR adaptive postfiltered images.

Linares, Irving↗

Optimization of Operations Resources via Discrete Event Simulation Modeling

The resource levels required for operation and support of reusable launch vehicles are typically defined through discrete event simulation modeling. Minimizing these resources constitutes an optimization problem involving discrete variables and simulation. Conventional approaches to solve such optimization problems involving integer valued decision variables are the pattern search and statistical methods. However, in a simulation environment that is characterized by search spaces of unknown topology and stochastic measures, these optimization approaches often prove inadequate. In this paper, we have explored the applicability of genetic algorithms to the simulation domain. Genetic algorithms provide a robust search strategy that does not require continuity and differentiability of the problem domain. The genetic algorithm successfully minimized the operation and support activities for a space vehicle, through a discrete event simulation model. The practical issues associated with simulation optimization, such as stochastic variables and constraints, were also taken into consideration.

Joshi, B.↗

A satellite system synthesis model for orbital arc allotment optimization

A mixed-integer programming formulation is presented of a satellite system synthesis problem, or geostationary-orbital-planning synthesis problem, which is refered to as the arc allotment problem (AAP). Each satellite administration is to be allotted a weighted-length segment of the geostationary orbital arc within which its satellites may be positioned at any longitude. The objective function maximizes the length of the unweighted arc segment allotted to every administration, subject to single-entry cochannel interference restrictions and constraints imposed by the visible arc for each administration. Useful relationships between special cases of AAP and another satellite synthesis problem are established. Solutions to two example problems are presented.

Reilly, Charles H.↗

A digital algorithm for spectral deconvolution with noise filtering and peak picking: NOFIPP-DECON

Noise-filtering, peak-picking deconvolution software incorporates multiple convoluted convolute integers and multiparameter optimization pattern search. The two theories are described and three aspects of the software package are discussed in detail. Noise-filtering deconvolution was applied to a number of experimental cases ranging from noisy, nondispersive X-ray analyzer data to very noisy photoelectric polarimeter data. Comparisons were made with published infrared data, and a man-machine interactive language has evolved for assisting in very difficult cases. A modified version of the program is being used for routine preprocessing of mass spectral and gas chromatographic data.

Edwards, T. R.↗

Mixed Integer Programming and Heuristic Scheduling for Space Communication

Optimal planning and scheduling for a communication network was created where the nodes within the network are communicating at the highest possible rates while meeting the mission requirements and operational constraints. The planning and scheduling problem was formulated in the framework of Mixed Integer Programming (MIP) to introduce a special penalty function to convert the MIP problem into a continuous optimization problem, and to solve the constrained optimization problem using heuristic optimization. The communication network consists of space and ground assets with the link dynamics between any two assets varying with respect to time, distance, and telecom configurations. One asset could be communicating with another at very high data rates at one time, and at other times, communication is impossible, as the asset could be inaccessible from the network due to planetary occultation. Based on the network's geometric dynamics and link capabilities, the start time, end time, and link configuration of each view period are selected to maximize the communication efficiency within the network. Mathematical formulations for the constrained mixed integer optimization problem were derived, and efficient analytical and numerical techniques were developed to find the optimal solution. By setting up the problem using MIP, the search space for the optimization problem is reduced significantly, thereby speeding up the solution process. The ratio of the dimension of the traditional method over the proposed formulation is approximately an order N (single) to 2*N (arraying), where N is the number of receiving antennas of a node. By introducing a special penalty function, the MIP problem with non-differentiable cost function and nonlinear constraints can be converted into a continuous variable problem, whose solution is possible.

Lee, Charles H.↗

Optimization of Airport Surface Traffic: A Case-Study of Incheon International Airport

This study aims to develop a controllers' decision support tool for departure and surface management of ICN. Airport surface traffic optimization for Incheon International Airport (ICN) in South Korea was studied based on the operational characteristics of ICN and airspace of Korea. For surface traffic optimization, a multiple runway scheduling problem and a taxi scheduling problem were formulated into two Mixed Integer Linear Programming (MILP) optimization models. The Miles-In-Trail (MIT) separation constraint at the departure fix shared by the departure flights from multiple runways and the runway crossing constraints due to the taxi route configuration specific to ICN were incorporated into the runway scheduling and taxiway scheduling problems, respectively. Since the MILP-based optimization model for the multiple runway scheduling problem may be computationally intensive, computation times and delay costs of different solving methods were compared for a practical implementation. This research was a collaboration between Korea Aerospace Research Institute (KARI) and National Aeronautics and Space Administration (NASA).

surface management↗

Optimization of Airport Surface Traffic: A Case-Study of Incheon International Airport

This study aims to develop a controllers decision support tool for departure and surface management of ICN. Airport surface traffic optimization for Incheon International Airport (ICN) in South Korea was studied based on the operational characteristics of ICN and airspace of Korea. For surface traffic optimization, a multiple runway scheduling problem and a taxi scheduling problem were formulated into two Mixed Integer Linear Programming (MILP) optimization models. The Miles-In-Trail (MIT) separation constraint at the departure fix shared by the departure flights from multiple runways and the runway crossing constraints due to the taxi route configuration specific to ICN were incorporated into the runway scheduling and taxiway scheduling problems, respectively. Since the MILP-based optimization model for the multiple runway scheduling problem may be computationally intensive, computation times and delay costs of different solving methods were compared for a practical implementation. This research was a collaboration between Korea Aerospace Research Institute (KARI) and National Aeronautics and Space Administration (NASA).

taxi scheduler↗

Mixed Integer Programming and Heuristic Scheduling for Space Communication Networks

We developed framework and the mathematical formulation for optimizing communication network using mixed integer programming. The design yields a system that is much smaller, in search space size, when compared to the earlier approach. Our constrained network optimization takes into account the dynamics of link performance within the network along with mission and operation requirements. A unique penalty function is introduced to transform the mixed integer programming into the more manageable problem of searching in a continuous space. The constrained optimization problem was proposed to solve in two stages: first using the heuristic Particle Swarming Optimization algorithm to get a good initial starting point, and then feeding the result into the Sequential Quadratic Programming algorithm to achieve the final optimal schedule. We demonstrate the above planning and scheduling methodology with a scenario of 20 spacecraft and 3 ground stations of a Deep Space Network site. Our approach and framework have been simple and flexible so that problems with larger number of constraints and network can be easily adapted and solved.

Mixed Integer Programming↗