Search NASASearch

SEARCH · Search NASA

Results for “Mixed Integer Programming”

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

Engineering calculations for communications satellite systems planning

Observed solution times were analyzed for the extended gradient and cyclic coordinate search procedures. The times used in the analysis come from computer runs made during a previously-reported experiment conducted to assess the quality of the solutions to a BSS synthesis problem found by the two search methods. The results of a second experiment with a Fixed Satellite Service (FSS) test problem are also presented. Computational results are summarized for mixed integer programming approaches for solving FSS synthesis problems. A promising heuristic algorithm is described. A synthesis model is discussed for orbital arc allotment optimization. Research plans for the near future are also presented.

Reilly, C. H.

On orbital allotments for geostationary satellites

The following satellite synthesis problem is addressed: communication satellites are to be allotted positions on the geostationary arc so that interference does not exceed a given acceptable level by enforcing conservative pairwise satellite separation. A desired location is specified for each satellite, and the objective is to minimize the sum of the deviations between the satellites' prescribed and desired locations. Two mixed integer programming models for the satellite synthesis problem are presented. Four solution strategies, branch-and-bound, Benders' decomposition, linear programming with restricted basis entry, and a switching heuristic, are used to find solutions to example synthesis problems. Computational results indicate the switching algorithm yields solutions of good quality in reasonable execution times when compared to the other solution methods. It is demonstrated that the switching algorithm can be applied to synthesis problems with the objective of minimizing the largest deviation between a prescribed location and the corresponding desired location. Furthermore, it is shown that the switching heuristic can use no conservative, location-dependent satellite separations in order to satisfy interference criteria.

Gonsalvez, David J. A.

Engineering calculations for communications satellite systems planning

A procedure is described that was used to calculate minimum required satellite separations based on total link carrier to interference requirements. Also summarized are recent results with a switching algorithm for satellite synthesis problems. Analytic solution value bounds for two of the satellite synthesis models studied are described. Preliminary results from an empirical study of alternate mixed integer programming models for satellite synthesis are presented. Research plans for the near future are discussed.

Reilly, Charles H.

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.

A method for nonlinear optimization with discrete design variables

A numerical method is presented for the solution of nonlinear discrete optimization problems. The applicability of discrete optimization to engineering design is discussed, and several standard structural optimization problems are solved using discrete design variables. The method uses approximation techniques to create subproblems suitable for linear mixed-integer programming methods. The method employs existing software for continuous optimization and integer programming.

Olsen, Gregory R.

A k-permutation algorithm for Fixed Satellite Service orbital allotments

A satellite system synthesis problem, the satellite location problem (SLP), is addressed in this paper. In SLP, orbital locations (longitudes) are allotted to geostationary satellites in the Fixed Satellite Service. A linear mixed-integer programming model is presented that views SLP as a combination of two problems: (1) the problem of ordering the satellites and (2) the problem of locating the satellites given some ordering. A special-purpose heuristic procedure, a k-permutation algorithm, that has been developed to find solutions to SLPs formulated in the manner suggested is described. Solutions to small example problems are presented and analyzed.

Reilly, Charles H.

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.

Engineering calculations for solving the orbital allotment problem

Four approaches for calculating downlink interferences for shaped-beam antennas are described. An investigation of alternative mixed-integer programming models for satellite synthesis is summarized. Plans for coordinating the various programs developed under this grant are outlined. Two procedures for ordering satellites to initialize the k-permutation algorithm are proposed. Results are presented for the k-permutation algorithms. Feasible solutions are found for 5 of the 6 problems considered. Finally, it is demonstrated that the k-permutation algorithm can be used to solve arc allotment problems.

Reilly, C.

Finding fixed satellite service orbital allotments with a k-permutation algorithm

A satellite system synthesis problem, the satellite location problem (SLP), is addressed. In SLP, orbital locations (longitudes) are allotted to geostationary satellites in the fixed satellite service. A linear mixed-integer programming model is presented that views SLP as a combination of two problems: the problem of ordering the satellites and the problem of locating the satellites given some ordering. A special-purpose heuristic procedure, a k-permutation algorithm, has been developed to find solutions to SLPs. Solutions to small sample problems are presented and analyzed on the basis of calculated interferences.

Reilly, Charles H.

Efficient Computation of Separation-Compliant Speed Advisories for Air Traffic Arriving in Terminal Airspace

A class of problems in air traffic management asks for a scheduling algorithm that supplies the air traffic services authority not only with a schedule of arrivals and departures, but also with speed advisories. Since advisories must be finite, a scheduling algorithm must ultimately produce a finite data set, hence must either start with a purely discrete model or involve a discretization of a continuous one. The former choice, often preferred for intuitive clarity, naturally leads to mixed-integer programs, hindering proofs of correctness and computational cost bounds (crucial for real-time operations). In this paper, a hybrid control system is used to model air traffic scheduling, capturing both the discrete and continuous aspects. This framework is applied to a class of problems, called the Fully Routed Nominal Problem. We prove a number of geometric results on feasible schedules and use these results to formulate an algorithm that attempts to compute a collective speed advisory, effectively finite, and has computational cost polynomial in the number of aircraft. This work is a first step toward optimization and models refined with more realistic detail.

Sadovsky, Alexander V.

NASA Tech Briefs, May 2013

Topics include: Test Waveform Applications for JPL STRS Operating Environment; Pneumatic Proboscis Heat-Flow Probe; Method to Measure Total Noise Temperature of a Wireless Receiver During Operation; Cursor Control Device Test Battery; Functional Near-Infrared Spectroscopy Signals Measure Neuronal Activity in the Cortex; ESD Test Apparatus for Soldering Irons; FPGA-Based X-Ray Detection and Measurement for an X-Ray Polarimeter; Sequential Probability Ratio Test for Spacecraft Collision Avoidance Maneuver Decisions; Silicon/Carbon Nanotube Photocathode for Splitting Water; Advanced Materials and Fabrication Techniques for the Orion Attitude Control Motor; Flight Hardware Packaging Design for Stringent EMC Radiated Emission Requirements; RF Reference Switch for Spaceflight Radiometer Calibration; An Offload NIC for NASA, NLR, and Grid Computing; Multi-Scale CNT-Based Reinforcing Polymer Matrix Composites for Lightweight Structures; Ceramic Adhesive and Methods for On-Orbit Repair of Re-Entry Vehicles; Self-Healing Nanocomposites for Reusable Composite Cryotanks; Pt-Ni and Pt-Co Catalyst Synthesis Route for Fuel Cell Applications; Aerogel-Based Multilayer Insulation with Micrometeoroid Protection; Manufacturing of Nanocomposite Carbon Fibers and Composite Cylinders; Optimized Radiator Geometries for Hot Lunar Thermal Environments; A Mission Concept: Re-Entry Hopper-Aero-Space-Craft System on-Mars (REARM-Mars); New Class of Flow Batteries for Terrestrial and Aerospace Energy Storage Applications; Reliability of CCGA 1152 and CCGA 1272 Interconnect Packages for Extreme Thermal Environments; Using a Blender to Assess the Microbial Density of Encapsulated Organisms; Mixed Integer Programming and Heuristic Scheduling for Space Communication; Video Altimeter and Obstruction Detector for an Aircraft; Control Software for Piezo Stepping Actuators; Galactic Cosmic Ray Event-Based Risk Model (GERM) Code; Sasquatch Footprint Tool; and Multi-User Space Link Extension (SLE) System.

Source record

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 Convexification-Based Outer-Approximation Method for Convex and Nonconvex MINLP

The advancement of domain reduction techniques has significantly enhanced the performance of solvers in mathematical programming. This paper delves into the impact of integrating convexification and domain reduction techniques within the Outer-Approximation method. We propose a refined convexification-based Outer-Approximation method alongside a Branch-and-Bound method for both convex and nonconvex Mixed-Integer Nonlinear Programming problems. These methods have been developed and incorporated into the open-source Mixed-Integer Nonlinear Decomposition Toolbox for Pyomo-MindtPy. Comprehensive benchmark tests were conducted, validating the effectiveness and reliability of our proposed algorithms. These tests highlight the improvements achieved by incorporating convexification and domain reduction techniques into the Outer-Approximation and Branch-and-Bound methods.

Optimization

ALPS: A Linear Program Solver

ALPS is a computer program which can be used to solve general linear program (optimization) problems. ALPS was designed for those who have minimal linear programming (LP) knowledge and features a menu-driven scheme to guide the user through the process of creating and solving LP formulations. Once created, the problems can be edited and stored in standard DOS ASCII files to provide portability to various word processors or even other linear programming packages. Unlike many math-oriented LP solvers, ALPS contains an LP parser that reads through the LP formulation and reports several types of errors to the user. ALPS provides a large amount of solution data which is often useful in problem solving. In addition to pure linear programs, ALPS can solve for integer, mixed integer, and binary type problems. Pure linear programs are solved with the revised simplex method. Integer or mixed integer programs are solved initially with the revised simplex, and the completed using the branch-and-bound technique. Binary programs are solved with the method of implicit enumeration. This manual describes how to use ALPS to create, edit, and solve linear programming problems. Instructions for installing ALPS on a PC compatible computer are included in the appendices along with a general introduction to linear programming. A programmers guide is also included for assistance in modifying and maintaining the program.

Ferencz, Donald C.

An Approach to Reasoning Service Migration in Data and Reasoning Fabric (DRF) Implementation

In this paper we consider service migration problem for Data and Reasoning Fabric (DRF) enabled airspace operations assuming a fixed cloud/edge infrastructure with allocated computing, storage and power resources, where cloud/edge servers, and communication stations are in a wired connected network, while vehicles use a wireless network for communication. The objective is to automatically select the best location for the requested service execution, which achieves minimum cost while satisfying the user quality of service (QoS) and available resources constraints. To this end, estimates of the response time, consumed energy and total cost are defined for each potential compute location. A mixed-integer linear program is then formulated and solved to identify optimal compute locations given QoS constraints, network infrastructure limitations, with worst-case vehicle positioning. The approach is applied to trajectory re-planning use case to avoid a collision with an emergency vehicle in real time.

Air mobility

Partition-based Feasible Integer Solution Pre-computation for Hybrid Model Predictive Control

For multiparametric mixed-integer convex programming problems such as those encountered in hybrid model predictive control, we propose an algorithm for generating a feasible partition of a subset of the parameter space. The result is a static map from the current parameter to a suboptimal integer solution such that the remaining convex program is feasible. Convergence is proved with a new insight that the overlap among the feasible parameter sets of each integer solution governs the partition complexity. The partition is stored as a tree which makes querying the feasible solution efficient. The algorithm can be used to warm start a mixed integer solver with a real-time guarantee or to provide a reference integer solution in several suboptimal MPC schemes. The algorithm is tested on randomly generated systems with up to six states, demonstrating the effectiveness of the approach.

Bayard, David S.

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

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