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
DOE OSTI2019

Mixed Integer Nonlinear Programming Approaches to Enhance Resiliency and Response Strategies in Critical Infrastructure

Motivation. Critical infrastructures are large, complex engineered systems that must be operated robustly under abnormal conditions resulting from natural hazards or intentional acts. For example, electric power systems must be robust to line faults, water utilities must rapidly mitigate contamination incidents, and computing networks must adapt to adversarial intrusions to protect critical information. Problem. It is difficult for decision-makers within resiliency analysis in critical infrastructure to optimize designs and develop effective response strategies that can account for uncertainties. Facing incomplete information and the sheer scope that a natural hazard or attack vector may incorporate, response can be ineffective without reliable, scalable decision support tools. These problems are intrinsically nonlinear and involve discrete decisions, and unfortunately, existing off-the-shelf mathematical programming methods cannot support optimization-based decision-making of these nonlinear at scale. Method/Approach and Results. This project emphasized development of fundamental optimization strategies that supported real- time mitigation and response for critical infrastructures. In particular, the project developed multi- tree approaches based on piecewise outer-approximations for solution of mixed-integer nonlinear programming (MINLP) problems. These techniques alternate between an MILP or MISOCP relaxation to obtain a lower bound and candidate discrete solutions and an NLP subproblem to obtain upper bounds. Using tailored relaxations based on problem structure, these methods were used to solve several key applications in resilience and response of critical infrastructure. This work resulted in two open-source, copyrighted software packages: CORAMIN (https://github.com/Coramin/Coramin) -- an object-oriented mathematical programming framework that supports tailored multi-tree algorithms for solution of large- scale mixed-integer nonlinear programming; and EGRET (Electrical Grid Research and Engineering Toolkit) (https://github.com/grid- parity-exchange/Egret) -- a declarative mathematical programming framework built upon CORAMIN and Pyomo for formulation and solution of resilience and operations problems in power grid systems. Furthermore, these tools resulted in several important published results, including the following: The first known global optimization approach that could solve the unit-commitment problem with nonlinear power flow constraints on medium-sized test problems; Improved parallel optimization-based bounds tightening and strengthening of relaxations of AC power flow constraints; and, Optimization-based approaches for improved grid resilience and use of demand response to improve grid resilience with reduction in capital requirements. Result Implications. This project developed first-of-a-kind algorithms for decision-making in critical infrastructure resilience operations and planning, as well as a next-generation toolkit for MINLP researchers. These approaches leveraged high-performance computing architectures to solve some of the largest, most challenging nonlinear discrete optimization problems to global optimality, and these successes were captured in open-source software to enable optimization-based decision-making, and efficient solution of MINLP formulations for electric power transmission grids.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2024

Multi-parametric analysis for mixed integer linear programming: An application to transmission upgrade and congestion management

Upgrading the capacity of existing transmission lines is essential for meeting the growing energy demands, facilitating the integration of renewable energy, and ensuring the security of the transmission system. This study focuses on the selection of lines whose capacities and by how much should be expanded from the perspective of the Independent System Operators (ISOs) to minimize the total system cost. We employ advanced multi-parametric programming and an enhanced branch-and-bound algorithm to address complex mixed-integer linear programming (MILP) problems, considering multi-period time constraints and physical limitations of generators and transmission lines. To characterize the various decisions in transmission expansion, we model the increased capacity of existing lines as parameters within a specified range. This study first relaxes the binary variables to continuous variables and applies the Lagrange method and Karush-Kuhn-Tucker (KKT) conditions to obtain optimal solutions and identify critical regions associated with active and inactive constraints. Moreover, we extend the traditional branch-and-bound (B&B) method by determining the problem’s upper and lower bounds at each node of the B&B decision tree, helping to manage computational challenges in large-scale MILP problems. Here, we compare the difference between the upper and lower bounds to obtain an approximate optimal solution within the decision-makers’ tolerable error range. In addition, the first derivative of the objective function on the parameters of each line is used to inform the selection of lines for easing congestion and maximizing social welfare. Finally, the capacity upgrades are selected by weighing the reductions in system costs against the expense of upgrading line capacities. The findings are supported by numerical simulations and provide transmission-line planners with decision-making guidance.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2026

Optimizing district energy systems by integrating Borehole Thermal Energy Storage Using a Mixed-Integer Linear Programming g-function framework with a Multi-Timescale Rolling Horizon method

Shallow geothermal has gained increasing attention in recent years; however, a reliable framework for its accurate incorporation into large-scale energy system optimization remains lacking. This study proposes a Mixed-Integer Linear Programming (MILP) framework combined with the g-function approach to integrate Borehole Thermal Energy Storage (BTES) technology into energy system optimization. Validation against a Modelica-based reservoir network simulation demonstrates that the proposed framework effectively captures the ground thermal response under varying energy loads and accurately estimates the borefield energy supply. To enhance scalability, a Rolling Horizon with Multi-Timescale (RH-MTS) method is further introduced, reducing computational time by 73 % for the 1-year optimization model with only minor loss of optimality. The framework is demonstrated through the case study of the UC Berkeley campus. Results indicate that BTES is a cost-effective and low-carbon solution: two borefields comprising 382 boreholes can meet 8.0 % and 6.6 % of the total campus heating and cooling demand, respectively, at an average energy rate of 0.70–0.77 USD/kWh and carbon intensity of 0.54 kg-CO2/kWh. Short-term analysis reveals a 35%–65% decline in BTES energy flow after 3–6 months of continuous heating/cooling operation, while long-term simulation shows that annual energy production of BTES can vary by up to 12.0 % after four years before stabilizing. Overall, this study develops a novel optimization framework that couples physics-based g-function method with MILP optimization framework, thereby advancing methodological development for shallow-geothermal integration and providing actionable guidance for BTES deployment in district-energy systems.

Yang, Jiahui↗
DOE OSTI2021

Disjunctive linear separation conditions and mixed-integer formulations for aircraft conflict resolution

In this paper, we address the aircraft conflict resolution problem in air traffic control. We introduce new mixed-integer programming formulations for aircraft conflict resolution with speed, heading and altitude control which are based on disjunctive linear separation conditions. We first examine the two-dimensional aircraft conflict resolution problem with speed and heading control represented as continuous decision variables. We show that the proposed disjunctive linear separation conditions are equivalent to the classical nonlinear conditions for aircraft separation. Further, we characterise conflict-free trajectories based on aircraft velocity bounds and propose a simple pre-processing algorithm to identify aircraft pairs which are either always conflict-free, or which cannot be separated using speed and heading control only. We then incorporate altitude control and propose a lexicographic optimisation formulation that aims to minimise the number of flight level changes before resolving outstanding conflicts via two-dimensional velocity control. The proposed mixed-integer programming formulations are nonconvex, and we propose convex relaxations, decomposition methods and constraint generation algorithms to solve the two-dimensional and lexicographic optimisation formulations to guaranteed optimality. Numerical experiments on four types of conflict resolution benchmarking instances are conducted to test the performance of the proposed mixed-integer formulations. Further, the proposed method is compared against two benchmarks based on state-of-the-art approaches for the aircraft conflict resolution problem. Our numerical results show that the proposed method largely outperforms both benchmarks in terms of runtime and is able to solve significantly more instances to global optimality.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2009

A Mixed Integer Linear Program for Airport Departure Scheduling

Aircraft departing from an airport are subject to numerous constraints while scheduling departure times. These constraints include wake-separation constraints for successive departures, miles-in-trail separation for aircraft bound for the same departure fixes, and time-window or prioritization constraints for individual flights. Besides these, emissions as well as increased fuel consumption due to inefficient scheduling need to be included. Addressing all the above constraints in a single framework while allowing for resequencing of the aircraft using runway queues is critical to the implementation of the Next Generation Air Transport System (NextGen) concepts. Prior work on airport departure scheduling has addressed some of the above. However, existing methods use pre-determined runway queues, and schedule aircraft from these departure queues. The source of such pre-determined queues is not explicit, and could potentially be a subjective controller input. Determining runway queues and scheduling within the same framework would potentially result in better scheduling. This paper presents a mixed integer linear program (MILP) for the departure-scheduling problem. The program takes as input the incoming sequence of aircraft for departure from a runway, along with their earliest departure times and an optional prioritization scheme based on time-window of departure for each aircraft. The program then assigns these aircraft to the available departure queues and schedules departure times, explicitly considering wake separation and departure fix restrictions to minimize total delay for all aircraft. The approach is generalized and can be used in a variety of situations, and allows for aircraft prioritization based on operational as well as environmental considerations. We present the MILP in the paper, along with benefits over the first-come-first-serve (FCFS) scheme for numerous randomized problems based on real-world settings. The MILP results in substantially reduced delays as compared to FCFS, and the magnitude of the savings depends on the queue and departure fix structure. The MILP assumes deterministic aircraft arrival times at the runway queues. However, due to taxi time uncertainty, aircraft might arrive either earlier or later than these deterministic times. Thus, to incorporate this uncertainty, we present a method for using the MILP with "overlap discounted rolling planning horizon". The approach is based on valuing near-term decision results more than future ones. We develop a model of taxitime uncertainty based on real-world data, and then compare the baseline FCFS delays with delays using the above MILP in a simple rolling-horizon method and in the overlap discounted scheme.

Gupta, Gautam↗
DOE OSTI2024

Optimal Electrification Using Renewable Energies: Microgrid Installation Model with Combined Mixture k-Means Clustering Algorithm, Mixed Integer Linear Programming, and Onsset Method

Optimal planning and design of microgrids are priorities in the electrification of off-grid areas. Indeed, in one of the Sustainable Development Goals (SDG 7), the UN recommends universal access to electricity for all at the lowest cost. Several optimization methods with different strategies have been proposed in the literature as ways to achieve this goal. This paper proposes a microgrid installation and planning model based on a combination of several techniques. The programming language Python 3.10 was used in conjunction with machine learning techniques such as unsupervised learning based on K-means clustering and deterministic optimization methods based on mixed linear programming. These methods were complemented by the open-source spatial method for optimal electrification planning: onsset. Four levels of study were carried out. The first level consisted of simulating the model obtained with a cluster, which is considered based on the elbow and k-means clustering method as a case study. The second level involved sizing the microgrid with a capacity of 40 kW and optimizing all the resources available on site. The example of the different resources in the Togo case was considered. At the third level, the work consisted of proposing an optimal connection model for the microgrid based on voltage stability constraints and considering, above all, the capacity limit of the source substation. Finally, the fourth level involved a planning study of electrification strategies based mainly on microgrids according to the study scenario. The results of the first level of study enabled us to obtain an optimal location for the centroid of the cluster under consideration, according to the different load positions of this cluster. Then, the results of the second level of study were used to highlight the optimal resources obtained and proposed by the optimization model formulated based on the various technology costs, such as investment, maintenance, and operating costs, which were based on the technical limits of the various technologies. In these results, solar systems account for 80% of the maximum load considered, compared to 7.5% for wind systems and 12.5% for battery systems. Next, an optimal microgrid connection model was proposed based on the constraints of a voltage stability limit estimated to be 10% of the maximum voltage drop. The results obtained for the third level of study enabled us to present selective results for load nodes in relation to the source station node. Finally, the last results made it possible to plan electrification using different network technologies and systems in the short and long term. The case study of Togo was taken into account. The various results obtained from the different techniques provide the necessary leads for a feasibility study for optimal electrification of off-grid areas using microgrid systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Optimal, centralized dynamic curbside parking space zoning

In this paper we formulate a dynamic mixed integer program for optimally zoning curbside parking spaces subject to transportation policy-inspired constraints and regularization terms. First, we illustrate how given some objective of curb zoning valuation as a function of zone type (paid parking, bus stop, etc.), dynamically rezoning involves unrolling this optimization program over a fixed time horizon. Second, we implement two different solution methods given an example curb zoning valuation. In the first method, we solve long horizon dynamic zoning problems via approximate dynamic programming. In the second method, we employ Dantzig-Wolfe decomposition to break-up the mixed-integer program into a master problem and several sub-problems that can be solved in parallel. This speeds up the computational solve-time of the MIP considerably. We present simulation results and comparisons of the different employed techniques on vehicle arrival-rate data obtained for a neighborhood in downtown Seattle, Washington, USA.

Nazir, Mohammad Nawaf↗
DOE OSTI2025

Mixed-Integer Linear Programming Formulation with Embedded Machine Learning Surrogates for the Design of Chemical Process Families

In previous work, we introduced process family design. The main idea is to design a platform of common elements, and, allowing us to capture additional cost savings, simultaneously design a family of processes, and reducing both engineering and deployment timelines. We formulate this as an optimization problem, specifically a nonlinear generalized disjunctive program (GDP). We have proposed two approaches for reformulating and solving this problem: one based on full-discretization of the design space and one that uses Machine Learning (ML) surrogates to replace the nonlinear process models. Using ML surrogates to predict required system costs and performance indicators allows us to reformulate the nonlinearities in the GDP generate an efficient MILP formulation. In this work, we apply the ML surrogate approach to two case studies. One case study involves designing a family of carbon capture systems to cover a set of different flue gas flow rates and inlet CO 2 concentrations, where we consider the absorber and stripper as common unit module types. The second case study focuses on a water-desalination process, where we design a family of these processes for a variety of salt concentrations and flow rates. In both of these case studies, we demonstrate a scalable optimization approach that enables the design of multiple processes simultaneously, reducing the time-to-market and overall costs by maximizing the cost savings due to both economies of scale and economies of numbers.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1985

Engineering calculations for communications satellite systems planning

Computer-based techniques for optimizing communications-satellite orbit and frequency assignments are discussed. A gradient-search code was tested against a BSS scenario derived from the RARC-83 data. Improvement was obtained, but each iteration requires about 50 minutes of IBM-3081 CPU time. Gradient-search experiments on a small FSS test problem, consisting of a single service area served by 8 satellites, showed quickest convergence when the satellites were all initially placed near the center of the available orbital arc with moderate spacing. A transformation technique is proposed for investigating the surface topography of the objective function used in the gradient-search method. A new synthesis approach is based on transforming single-entry interference constraints into corresponding constraints on satellite spacings. These constraints are used with linear objective functions to formulate the co-channel orbital assignment task as a linear-programming (LP) problem or mixed integer programming (MIP) problem. Globally optimal solutions are always found with the MIP problems, but not necessarily with the LP problems. The MIP solutions can be used to evaluate the quality of the LP solutions. The initial results are very encouraging.

Reilly, C. H.↗
DOE OSTI2024

A Mixed Integer Linear Programming-basedDistributed Energy Management for Three-phaseUnbalanced Active Distribution Network

A mixed integer linear programming (MILP)–baseddistributed energy management for three-phase unbalancedactive distribution network is proposed. Modern distributionnetworks have becoming more and more active with increasingdeployment of microgrids, distributed energy resources (DERs)as well as controllable loads. Considering various ownership andcontrol models of microgrids, DERs and controllable loads, adistributed energy management was formulated using the alternatingdirection method of multipliers (ADMM) algorithm. ByADMM, the distribution management system (DMS) and theseactive components are coordinated through price signals, whichare adjusted according to the generation-load mismatch per nodeper phase. To enable resolution of the ADMM-based distributedoptimization using more accessible and popular MILP solver,different linearization techniques were proposed to linearize theaugmented Lagrangian terms and other nonlinear terms. Resultsof case studies on a three-phase active distribution network withthree microgrids and several DERs and controllable loads validatedthe effectiveness of proposed MILP-based distributed energymanagement. In addition, the capability of proposed method inmitigating phase power unbalance has been demonstrated.

Liu, Guodong↗
DOE OSTI2024

Flexible dynamic boundary microgrid operation considering network and load unbalances

Flexible microgrids with dynamic boundaries have recently been introduced in the literature. With the ability to reconfigure the topology of the microgrids dynamically through remotely controlled switches, flexible microgrids with dynamic boundaries can further improve the resiliency and energy efficiency of microgrids with distributed energy resources (DERs). This paper focuses on the optimal operation considering one of the predominant characteristics of microgrids and distribution systems – unbalanced networks and loads. In existing literature, balanced modeling of microgrids is more common due to its attractive simplicity. The three-phase power unbalance has not been considered as a constraint on the generation units in a microgrid. Further, negative sequence constraints have also been neglected. In this article, we propose a set of constraints that is specifically related to the capabilities of inverter interfaced resources to supply unbalanced current/power when the microgrid is islanded from the main distribution grid. We incorporate the new set of constraints into two optimization formulations leveraging two convex relaxations of the three-phase power flow equations: mixed-integer linear programming (MILP) and mixed-integer semidefinite programming (MISDP) that optimize the dispatch of controllable switches and DERs in the microgrid. The algorithms are then extended to networked microgrids with grid-forming sources. We test the algorithms on a realistic community microgrid model in Puerto Rico as well as standardized IEEE distribution test feeders. The testing results demonstrate the performance of the proposed algorithms. The MILP is fast and scalable, and the MISDP enforces the negative sequence voltage constraints.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Optimizing design and dispatch of a renewable energy system with combined heat and power

We embellish a mixed-integer program that prescribes a set of renewable energy, conventional generation, and storage technologies to procure, along with a corresponding dispatch strategy. Specifically, we add combined heat and power to this set. The model minimizes fixed and operational costs less incentives for the use of various technologies, subject to a series of component interoperability and system-wide constraints. The resulting mixed-integer linear program contains hundreds of thousands of variables and constraints. We demonstrate how to efficiently formulate and solve the corresponding instances such that we produce near-optimal solutions in minutes. A previous rendition of the model required hours of solution time for the same instances.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Optimization of a Mixed Fleet of Aerial Drones for Medical Supplies: A Case Study of Blood Delivery Logistics

Aerial drones have emerged as an innovative solution for faster transportation of time-sensitive items (e.g., emergency medical supplies), potentially reducing the transmission of contagious diseases and enhancing healthcare availability through contactless autonomous delivery. We study fleet sizing and efficient scheduling of a mixed fleet of drones for delivering time-sensitive medical items having distinct release and due times to minimize the required fleet size and fleet composition, the required number of additional batteries, and the total energy consumption. We continuously track the remaining battery energy of drones to determine the optimal timing for battery replacement, rather than replacing the battery at each node. Using actual drone flight test data, we employed a machine learning (ML) method to estimate the energy consumption of different drone types during flight segments for different operating parameters. We present a novel mixed-integer programming model to efficiently formulate the problem that integrates the estimated energy consumption functions from ML. We propose a new greedy heuristic (GH) algorithm and a customized genetic algorithm (GA) for solving large-scale instances of this problem faster. Results demonstrate that the GH algorithm is substantially faster than the accelerated CPLEX and the GA, while sacrificing the solution quality by a small amount. Results based on an actual blood sample delivery case study from Pendleton, Oregon, United States, show that using a mixed fleet of drones reduces the total cost and total energy consumption up to 18.18% and 28.7%, respectively, compared to using a homogeneous fleet.

29 - ENERGY PLANNING, POLICY AND ECONOMY↗