Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

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.↗
NASA NTRS1988

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.↗
NASA NTRS1988

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.↗
NASA NTRS1990

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.↗
NASA NTRS2012

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 NTRS2013

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↗
DOE OSTI2024

Cooperative Transmission Expansion Planning Experiment Data and Results

GO WEST is an open-source power grid modeling framework for U.S. Western Interconnection, which allows users to tailor the model depending on their research study and science questions. It covers 28 balancing authorities (BA) and 12 states in U.S. Western Interconnection. GO WEST allows users to select different number of nodes and come up with a simplified network by utilizing 10,000 nodal topology of U.S. Western Interconnection created by Texas A&M University. Users can try and select different number of nodes, mathematical formulations (linear programming vs. mixed-integer linear programming), transmission line limit scaling factors, and hurdle rate scaling factors. GO WEST offers a unit commitment and economic dispatch (UC/ED) module to simulate grid operations on an hourly scale. In this sense, users can calibrate and validate their model versions by comparing model outputs to historical datasets. TEP is an open-source transmission capacity expansion model, built on GO WEST framework. It utilizes linear programming to optimize transmission capacity addition investment on existing lines within GO WEST framework. In this sense, TEP model only increases the thermal capacity of existing transmission lines and does not add new lines to the system, which leaves the topology preserved. TEP minimizes the total cost of the system which comprises the operational cost of satisfying electricity demand (i.e., generation cost), cost of loss of load (i.e., unserved energy), cost of power flow, and cost of new transmission capacity additions (i.e., investment cost). In order to use TEP model, users need to create scenarios with GO WEST framework. In this analysis, outputs from several models are used to create future inputs to GO WEST and TEP models, including GCAM-USA, TELL, CERF and reV. This dataset includes experiment inputs and outputs from three different transmission expansion scenarios (cooperative, intermediate, and individual) for 2019 and 2059. For 2019, a base scenario to illustrate the default (i.e., historical) power grid operations is also included. This study utilizes rcp45hotter_ssp3 scenario from a previous version of GCAM-USA simulations. Sources of the shapefiles in supplementary data are HIFLD Open and U.S. Energy Atlas. Please see the README file for a detailed description of the main and supplementary data.

Capacity Expansion Model↗
DOE OSTI2025

IM3 Projected U.S. Western Interconnection Grid Stress Dataset

This dataset provides projected grid stress and reliability results (including all model inputs and outputs from GO WEST and TEP) for Integrated Multisector, Multiscale Modeling (IM3) Phase 2 simulations across eight different scenarios for the U.S. Western Interconnection through 2055. The scenarios include combinations of two Shared Socioeconomic Pathways (SSP3 and SSP5) with four high-resolution climate projections specific to the United States from a set of Thermodynamic Global Warming (TGW) simulations. These climate projections include "hotter" and "cooler" variants for two Representative Concentration Pathways (RCP4.5 and RCP8.5). The resulting eight simulations are: rcp45cooler_ssp3 rcp45cooler_ssp5 rcp45hotter_ssp3 rcp45hotter_ssp5 rcp85cooler_ssp3 rcp85cooler_ssp5 rcp85hotter_ssp3 rcp85hotter_ssp5 GO WEST is an open-source power grid modeling framework for the U.S. Western Interconnection, which allows users to tailor the model depending on their research study and science questions. It covers 28 balancing authorities (BAs) and 12 states in U.S. Western Interconnection. GO WEST allows users to select different number of nodes and come up with a simplified network by utilizing 10,000 nodal topology of the U.S. Western Interconnection (ACTIVSg10k). Users can select different number of nodes, mathematical formulations (linear programming vs. mixed-integer linear programming), transmission line limit scaling factors, and hurdle rate scaling factors. GO WEST offers a unit commitment and economic dispatch (UC/ED) module to simulate grid operations on an hourly scale. In this sense, users can calibrate and validate their model versions by comparing model outputs to historical datasets. TEP is an open-source transmission capacity expansion model, built on the GO WEST framework. It utilizes linear programming to optimize transmission capacity addition investment on existing lines within the GO WEST framework. The TEP model only increases the thermal capacity of existing transmission lines and does not add new lines to the system, which leaves the topology preserved. In order to use TEP model, users need to create scenarios with the GO WEST framework. Please refer to README file for a detailed description of the dataset including individual files and references.

Capacity Expansion Model↗
DOE OSTI2025

A Fast Dynamic Internal Predictive Power Scheduling Approach for Power Management in Microgrids: Preprint

This paper presents a Dynamic Internal Predictive Power Scheduling (DIPPS) approach for optimizing power management in microgrids, particularly focusing on external power exchanges among diverse prosumers. DIPPS utilizes a dynamic objective function with a time-varying binary parameter to control the timing of power transfers to the external grid, facilitated by efficient usage of energy storage for surplus renewable power. The microgrid power scheduling problem is modeled as a mixed-integer nonlinear programming (MINLP-PS) and subsequently transformed into a mixed-integer linear programming (MILPPS) optimization through McCormick's relaxation to reduce computational complexity. A predictive window window with 6 data points is solved at an average of 0.92s, a 97.6% improvement over the 38.27s required for the MINLP-PS formulation, implying the numerical feasibility of the DIPPS approach for real-time implementation. Finally, the approach is validated against a static objective using real-world load data across three case studies with different time-varying parameters, demonstrating the ability of DIPPS to optimize power exchanges and efficiently utilize distributed resources while shifting the external power transfers to specified time durations.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2022

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↗
DOE OSTI2025

Planning Amidst Uncertainty: Identifying Core CCS Infrastructure Robust to Storage Uncertainty

Carbon Capture and Storage (CCS) is a critical technology for reducing anthropogenic CO2 emissions, but its large-scale deployment is complicated by uncertainties in geological storage performance. These uncertainties pose significant financial and operational risks, as underperforming storage sites can lead to costly infrastructure modifications, inefficient pipeline routing, and economic shortfalls. To address this challenge, we propose a novel optimization workflow that is based on mixed-integer linear programming and explicitly integrates probabilistic modeling of storage uncertainty into CCS infrastructure design. This workflow generates multiple infrastructure scenarios by sampling storage capacity distributions, optimally solving each scenario using a mixed-integer linear programming model, and aggregating results into a heatmap to identify core infrastructure components that have a low likelihood of underperforming. A risk index parameter is introduced to balance trade-offs between cost, CO2 processing capacity, and risk of underperformance, allowing stakeholders to quantify and mitigate uncertainty in CCS planning. Applying this workflow to a CCS dataset from the US Department of Energy’s Carbon Utilization and Storage Partnership project reveals key insights into infrastructure resilience. Reducing the risk index from 15% to 0% is observed to lead to an 83.7% reduction in CO2 processing capacity and a 77.1% decrease in project profit, quantifying the trade-off between risk tolerance and project performance. Furthermore, our results highlight critical breakpoints, where small adjustments in the risk index produce disproportionate shifts in infrastructure performance, providing actionable guidance for decision-makers. Unlike prior approaches that aimed to cheaply repair underperforming infrastructure, our workflow constructs robust CCS networks from the ground up, ensuring cost-effective infrastructure under storage uncertainty. These findings demonstrate the practical relevance of incorporating uncertainty-aware optimization into CCS planning, equipping decision-makers with a tool to make informed project planning decisions.

Olson, Daniel↗
NASA NTRS2024

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↗
DOE OSTI2024

Decomposing a renewable energy design and dispatch model

We address a mixed-integer linear programming model which selects a cost-minimizing set of available technologies with which to design a renewable energy system and prescribe their associated dispatch decisions. Realistically sized instances of such models pose computational challenges. To this end, we develop a Lagrangian heuristic based on a decomposition methodology which partitions the model into blocks and optimizes these more manageable, smaller subproblems. It also provides a lower bound to assess solution quality. In conclusion, we apply this methodology to the National Renewable Energy Laboratory's Renewable Energy Integration and Optimization (REopt TM ) model to generate near-optimal solutions to realistic instances containing, on average, approximately 300,000 variables and at least as many constraints, with a mean 30% optimality gap improvement using a five-minute solution time limit, compared to directly solving the original monolith.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

McCormick envelopes in mixed-integer PDE-constrained optimization

McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state constraints that may be difficult to handle) in addition to the state equation for a pointwise formulation of the McCormick envelopes and renders bound-tightening procedures that successively improve the resulting convex relaxations computationally intractable. We analyze McCormick envelopes for a model problem class that is governed by a semilinear PDE involving a bilinearity and integrality constraints. We approximate the nonlinearity and in turn the McCormick envelopes by averaging the involved terms over the cells of a partition of the computational domain on which the PDE is defined. This yields convex relaxations that underestimate the original problem up to an a priori error estimate that depends on the mesh size of the discretization. These approximate McCormick relaxations can be improved by means of an optimization-based bound-tightening procedure. We show that their minimizers converge to minimizers to a limit problem with a pointwise formulation of the McCormick envelopes when driving the mesh size to zero. We provide a computational example, for which we certify all of our imposed assumptions. The results point to both the potential of the methodology and the gaps in the research that need to be closed. Our methodology provides a framework first for obtaining pointwise underestimators for nonconvexities and second for approximating them with finitely many linear inequalities in an infinite-dimensional setting.

Approximations and Expansions↗
NASA NTRS1991

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.↗
NASA NTRS2021

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↗
DOE OSTI2025

Data-Driven Energy Resilience Assessment and Enhancement in Urban Communities: A Case Study in Detroit

This paper presents a data-driven framework for assessing and enhancing energy resilience in urban communities. The resilience assessment is based on two datasets: 1) annual aggregated power outage data and 2) 15-minute interval outage data. High-impact, low-probability (HILP) events are identified within these datasets to evaluate community resilience under extreme conditions. To enhance resilience, an optimization framework utilizing mixed integer linear programming is developed to determine the optimal sizing and placement of solar photovoltaic (PV) systems and battery energy storage systems (BESS). This method offers a cost-effective and practical solution for improving energy resilience in vulnerable communities. Furthermore, a case study of the City of Detroit in Michigan demonstrates the effectiveness of the framework through simulation and validation.

Energy resilience assessment↗
DOE OSTI2024

Grid-Aware Charging and Operational Optimization for Mixed-Fleet Public Transit

The rapid growth of urban populations and the increasing need for sustainable transportation solutions have prompted a shift towards electric buses in public transit systems. However, the effective management of mixed fleets consisting of both electric and diesel buses poses significant operational challenges. One major challenge is coping with dynamic electricity pricing, where charging costs vary throughout the day. Transit agencies must optimize charging assignments in response to such dynamism while accounting for secondary considerations such as seating constraints. This paper presents a comprehensive mixed-integer linear programming (MILP) model to address these challenges by jointly optimizing charging schedules and trip assignments for mixed (electric and diesel bus) fleets while considering factors such as dynamic electricity pricing, vehicle capacity, and route constraints. We address the potential computational intractability of the MILP formulation, which can arise even with relatively small fleets, by employing a hierarchical approach tailored to the fleet composition. By using real-world data from the city of Chattanooga, Tennessee, USA, we show that our approach can result in significant savings in the operating costs of the mixed transit fleets.

Sen, Rishav↗