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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
NASA NTRS2017

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↗
NASA NTRS2017

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↗
NASA NTRS2018

A Markov Decision Process Framework for Optimal Airport Reconfiguration

The airport runway configuration is defined as a combination set of runways for arrivals and departures used at a point during operation of the airport. An optimal configuration of these runways depends on a number of factors, including traffic demand, wind magnitude and direction, other adverse weather conditions, and noise restrictions, among others. Based on the current state of these factors and predictions of traffic demand and weather conditions, runway configuration changes are made and coordinated between tower controller, other air traffic control facilities, pilots, and ground personnel. Reconfigurations can be quite disruptive to airport operations; minimizing their frequency and scheduling them well in advance is essential for mitigating some of the added workload for controllers and pilots. Unfortunately, deciding on an appropriate time to change is challenging for human decision makers. Not only do multiple factors need to be evaluated, but the uncertainty in their forecasts must also be considered. Previous optimization methods, such as mixed linear integer programming, have been proposed. Although these methods can reason over a large set of variables, they do not systematically handle the uncertainty associated with weather movement, traffic demands, and other variables. In this work, we introduce a Markov Decision Process (MDP)-based decision making framework which can reason effectively over the inherent uncertainties and make optimal decisions on if/when to change the airport configuration. In a prototype implementation, we present a single runway with three aircraft and utilize knowledge of the forecasted wind speed and direction to determine whether to keep or change the current runway configuration. Our aim through this work is to present a framework for airport reconfiguration which can be scalable to additional aircraft, multiple runways, and various input parameters. This technique will optimize the airport reconfiguration procedure by providing a proactive approach, optimizing not just at the next optimal opportunity for a reconfiguration based on varying atmospheric and traffic conditions in the terminal airspace, but also anticipating future necessary reconfigurations. This will eliminate the inefficiencies of frequent changes currently associated with runway reconfiguration procedures.

runway reconfiguration↗
NASA NTRS2018

Comparison of First-Come First-Served and Optimization Based Scheduling Algorithms for Integrated Departure and Arrival Management

Korea Aerospace Research Institute (KARI) and National Aeronautics and Space Administration (NASA) are investigating scheduling algorithms that will be a part of an integrated arrival and departure management system. Inha University, one of the Korean collaborators of KARI, developed an Extended First-Come First-Served (EFCFS) algorithm that is robust and efficient. However, since the EFCFS algorithm sequentially computes the schedule based on priority, the end results may not be optimal for system efficiency. The approach based on Mixed Integer Linear Programming (MILP) originally developed by NASA and modified by KARI is known to produce better schedules at the expense of computational cost. In this paper, the two different scheduling approaches are compared using common traffic scenarios and constraints at Incheon International Airport. Capabilities to apply weight class based wake turbulence runway separation minima and Miles-in-Trail (MIT) restrictions at selected meter fixes are added to the previously developed EFCFS scheduler. Based on historic data, 40 departures and 20 arrivals are chosen in a one-hour period and 100 scenarios were created by randomly assigning gate numbers, gate departure times, and runway landing times. With the current runway separation requirements, MILP resulted in about ten to twenty percent smaller average delays depending on the constraints. With artificially increased separation minima, the difference between MILP and EFCFS became more noticeable. However, the EFCFS was about ten times faster with smaller variations among different scenarios and constraints. The comparison suggests that the MILP-based algorithm has a small advantage at the current traffic level; however, has potential to be more effective in higher demand or severe weather situations. The EFCFS algorithm may be better suited for real-time applications or investigating larger scale scheduling problems.

air traffic optimization↗
NASA NTRS2015

Optimizing Integrated Arrival, Departure and Surface Operations Under Uncertainty

In airports and surrounding terminal airspaces, the integration of arrival, departure and surface scheduling and routing have the potential to improve the operations efficiency. Recent research had developed mixed-integer-linear programming algorithm-based scheduler for integrated arrival and departure operations in the presence of uncertainty. This paper extends to the surface previous research performed by the authors to integrate taxiway and runway operations. The developed algorithm is capable of computing optimal aircraft schedules and routings that reflects the integration of air and ground operations. A preliminary study case is conducted for a set of thirteen aircraft evolving in a model of the Los Angeles International airport and surrounding terminal areas. Using historical data, a representative traffic scenario is constructed and probabilistic distributions of pushback delay and arrival gate delay are obtained. To assess the benefits of optimization, a First- Come-First-Serve algorithm approach comparison is realized. Evaluation results demonstrate that the optimization can help identifying runway sequencing and schedule that reduce gate waiting time without increasing average taxi times.

Bosson, Christabelle↗
NASA NTRS2015

Integration of Uncertain Ramp Area Aircraft Trajectories and Generation of Optimal Taxiway Schedules at Charlotte Douglas (CLT) Airport

The integration of aircraft maneuver characteristics into an optimal taxiway scheduling solution is challenging due to the uncertainties that are intrinsic to ramp area aircraft trajectories. To address the challenge, we build a stochastic model of ramp area aircraft trajectories that is used to generate a probabilistic measure of conflict within the Charlotte Douglas International Airport (CLT) ramp area. Parameters of the conflict distributions are estimated and passed to a Mixed Integer Linear Program that solves for an optimal taxiway schedule constrained to be conflict free in the presence of trajectory uncertainties. Here we extend our previous research by accounting for departing and arriving aircraft whereas our prior formulation only accounted for departing aircraft.

taxiway schedule↗
NASA NTRSDate not supplied

Planning Satellite Swarm Measurements for Climate Models: Comparing Dynamic Constraint Processing and MILP Methods

We present D-SHIELD, a challenging climate science application to plan coordinated measurements (observations) for a constellation of satellites, each containing two different sensors, each with 61 pointing angle options. The L-band and P-band radar sensors collect data fed into a soil moisture model which tracks and predicts soil moisture across 1.67 million Ground Positions (GP). Soil moisture is an important predictor of wildfires, and then a predictor of floods, landslides and debris flow after a fire. Each measurement covers multiple GP due to the sensor footprint. Each GP has a "model error" which represents the uncertainty of the the soil moisture state prediction. Model error changes at different rates for each GP as the time since last observation increases and after significant events like rain. The planner's goal is to select measurements which maximize soil moisture model improvement (reduce model uncertainty). This problem is combinatorically explosive, involving many degrees of freedom for planner choices. Good domain heuristics can find solutions within a reasonable time for our application needs but cannot be proven optimal. In this paper we compare two different planning approaches to this problem: Dynamic Constraint Processing (DCP) and Mixed Integer Linear Programming (MILP). We match inputs and metrics for both DCP and MILP algorithms to enable a direct apples-to-apples comparison. We demonstrate and discuss the trades between DCP flexibility and performance vs. MILP's promise of provable optimality.

Rich Levinson↗
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Monte Carlo Tree Search Approach

Numerous unmanned aircraft systems operating at low altitudes to deliver goods and services may one day become ubiquitous in our cities. In the Unmanned Aircraft Systems (UAS) Traffic Management (UTM) framework, such a concept is envisioned, where aerial vehicles operate beyond visual line of sight (BVLOS) within specifically reserved and time stamped “corridors” in the airspace. For example, these corridors or operational intent volumes can connect an aerial vehicle’s origin site to its destination site for package delivery operations. There may also be more than one corridor available for an aerial vehicle to choose from and often different corridors may intersect with one another. Thus, it is imperative to ensure flight trajectories belonging to different aerial vehicles are not in conflict. Per the UTM CONOPs, we assume that a vehicle almost always stays inside its corridor or operational volume. This work provides a framework for strategic deconfliction of UTM or package delivery drones, where we schedule the departure time of all vehicles subject to various temporal constraints (including the corridor deconfliction at the intersections). We present the “multi-route weighted package delivery problem” which serves as an exemplifying model for strategic deconfliction in UTM. In the multi-route weighted package delivery problem, a graph network is given which consists of a set of depots (source) and drop-off (destination) nodes, with multiple routes (defined as a sequence of waypoints) connecting the depots to drop-off nodes. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is for a known set of aerial vehicles to depart from the depots, choose a route and take off time, while avoiding conflicts with other aerial vehicles, and minimizing both risk and distance traveled. We provide a mixed integer linear programming (MILP) formulation of the problem, as well as a heuristic solution based on Monte Carlo Tree Search (MCTS) – a method used in game theory and artificial intelligence – to overcome limitations inherent to optimal solvers. Computational results show the advantages of using MCTS over the MILP formulation; the former can provide a sub-optimal solution quickly, and may sometimes even reach an optimal solution, whereas the latter may not even produce a solution in reasonable time. Furthermore, results from both the MILP formulation and MCTS methods were validated using a preliminary agent-based simulator implementing the UTM concept of operations. Thus, the MCTS method can be seen as a scalable solution to the complex multi-route weighted package delivery problem and may possibly be extended to similar complex optimization problems.

Kenny Chour↗
NASA NTRS2022

Multi-Robot Assembly Scheduling for the Lunar Crater Radio Telescope on the Far-Side of the Moon

The Lunar Crater Radio Telescope (LCRT) is a pro- posed ultra-long-wavelength radio telescope to be constructed on the far side of the moon. The proposed telescope will be constructed by deploying a 1km wire mesh in a 3-5km crater using a team of wall-climbing DuAxel robots. In this work, we consider the problem of generating minimum-time assembly sequences for LCRT, using realistic models of travel speed and lighting. Specifically, we pose the assembly sequencing problem as a mixed-integer linear program (MILP), which we solve to global optimality using commercial solvers. We present methods for modeling time-varying travel and assembly times, based on variable lighting conditions (including crater shadowing), and show how such time-varying parameters can be incorporated into the MILP. Finally, we present numerical studies of our method, showing how makespan varies with the number of assembly robots.

Schwager, Mac↗
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗
NASA NTRSDate not supplied

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

In this research, the strategic deconfliction of unmanned aircraft systems for an urban package delivery environment with two depots and multiple drop-off locations is studied. This research aims to formulate a mathematical model to compute both the departure sequence and scheduled time of departure for each unmanned aircraft system at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. However, the problem formulation results in an NP-hard mixed-integer nonlinear programming problem for the global optimal solution, so instead, a "rolling horizon with𝑘-position search"heuristic method is developed. The simulation studies show that an increase in the value of𝑘(the parameter used to determine the size of the local neighborhood) reduces the average ground delay at the cost of an increase in the computation time for a given problem size. The study also shows an order of magnitude increase in the maximum number of flights scheduled with the integration of rolling horizon (time decomposition) compared to those without the integration of rolling horizon in the heuristic algorithm for a given computation time cut off.

UTM↗
NASA NTRSDate not supplied

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

This research focuses on the strategic deconfliction of unmanned aircraft systems (UAS) in an urban package delivery environment with two depots and multiple drop-off locations. Since the formulated mixed-integer nonlinear programming (MINLP) problem is non-deterministic polynomial-time (NP) hard, a heuristic algorithm called "rolling horizon with k-position search (KPS)" is used to compute the departure sequence and scheduled time of departure (STD) of each UAS at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. The simulation studies show that an increase in the value of k (local neighborhood search) in the KPS reduces the average ground delay at the cost of an increase in the computation time for a given number of UAS, size of the rolling horizon window, and number of depots involved in the local neighborhood search. The studies also show that for a given rolling horizon window, the computation time increases exponentially with an increase in the total number of UAS flights when serial processing the local neighborhood search of KPS (with k > 1) and drops by an order of magnitude upon performing the local neighborhood search of KPS using parallel processing instead of serial processing. The computation time drops with the reduction in air traffic complexity of a scenario for a given number of flights, k (local neighborhood search), and rolling horizon window.

UTM↗
DOE OSTI2024

Solving the Grid Optimization Competition Challenge 3 Problem

The Grid Optimization Competition Challenge 3 Problem posed a multiperiod security-constrained unit commitment problem with base-case AC power flow. The problem formulation includes binary unit commitment decisions, nonlinear AC power flow and balance, dispatchable loads, and linearized contingency real power flow, among other features. This talk will present a modified consensus ADMM algorithm, which splits the problem into mixed-integer linear and nonlinear components, as a heuristic solution method for this large-scale mixed integer nonlinear program. We will present some computational results from the competition for our implementation and reflect on the challenges of participating the grid optimization competition.

AC power flow↗
DOE OSTI2024

Research Highlight - Dispatch Optimization, System Design and Cost Benefit Analysis of a Nuclear Reactor with Molten Salt Thermal Storage

We highlight our work from our previous publication titled "Dispatch Optimization, System Design, and Cost Benefit Analysis of a Nuclear Reactor with Molten Salt Thermal Storage" published in MDPI Energies 2022 (doi.org/10.3390/en15103599). Variable renewable energy availability has increased the volatility in energy prices in most markets. Nuclear power plants, with a large ratio of capital to variable costs, have historically operated as base load energy suppliers but the need for more flexible operation is increasing. We simulate the techno-economic performance of a 950 MWt nuclear power plant, based on the Westinghouse lead-cooled fast reactor, coupled with molten salt thermal storage as a method for flexible energy dispatch. We use the System Advisor Model to model the nuclear reactor thermal power input and power cycle operating modes. We combine this robust engineering model with a mixed-integer linear program model for optimized dispatch scheduling. We then simulate the coupled nuclear and thermal storage system under different market scenarios with varying price volatility. We find that the coupled plant outperforms the base plant under markets where energy price peaks fluctuate by a factor of two or more about the mean price. We show that a calculated power purchase agreement price for the plant improves by up to 10% when operating under California energy market conditions. Sensitivity analysis on the thermal storage cost shows that the optimal design remains unchanged even when doubling costs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Privacy-Protected Simultaneous Provision of Energy and Primary Frequency Control Reserve

This paper investigates a Mixed Integer Linear Programming (MILP) model for simultaneous scheduling of energy and primary frequency control reserve. Given the model’s unique structure and growing concerns about privacy, we adopt Dantzig-Wolfe Decomposition (DWD) algorithm to solve the problem in a decentralized fashion while obfuscating the privacy of the energy and reserve resources. Additionally, we present a novel criterion for checking the model’s feasibility. Finally, simulation results are given and discussed.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Optimization for Bioenergy Systems

The Sustainable Aviation Fuel (SAF) Grand Challenge (Langholtz, 2024 ) seeks to generate 35 billion gallons of SAF each year by 2050, with corn stover, an agricultural byproduct, playing a key role as a feedstock. This study develops an optimization framework to enhance the quality and quantity of corn stover while ensuring economic and environmental viability. Using the Decision Support System for Agrotechnology Transfer (DSSAT) crop model, we simulate the effects of cover crops on rotation yield, soil moisture balance, and nitrogen cycling across diverse climates and soils. The model outputs, including yield data and soil quality changes, inform a Mixed-Integer Linear Programming (MILP) optimization model. This model aims to maximize economic and environmental returns by incorporating production costs, direct and indirect income, and environmental incentives. The optimization model evaluates 280 agriculture management plans composed of various crop management strategies, including corn stover removal rates, cover crop adoption, and fertilization practices. It seeks to identify the optimal combination of crop and tillage decisions for each subfield, maximizing profits while enhancing soil carbon sequestration and reducing greenhouse gas emissions. Outputs include detailed subfield locations, optimal management plans, and profits per hectare and per acre, allowing for comparison with literature values on farm profits. This study provides a robust optimization framework supporting the SAF Grand Challenge by proposing economically viable and environmentally sustainable strategies for corn stover utilization. The findings highlight corn stover's potential as a sustainable feedstock for SAF production, offering practical solutions to enhance its quality and quantity while maintaining soil health. Idaho is used as a case study to demonstrate the framework's applicability and effectiveness in real-world scenarios. Langholtz, M. H., Davis, M., Hellwinckel, C., De La Torre Ugarte, D., Efroymson, R., Jacobson, R., Milbrandt, A., Coleman, A., Davis, R., Kline, K. L., Badgett, A., Curran, S., Schmidt, E., Theiss, T., Fried, J., English, B., Lambert, L., Cook, H., Field, J., ... Walker, L. (2024). 2023 Billion-Ton Report: An Assessment of U.S. Renewable Carbon Resources. https://doi.org/10.2172/2441098 DSSAT Foundation. (2025). Decision Support System for Agrotechnology Transfer (DSSAT). Retrieved from https://dssat.net/

09 - BIOMASS FUELS↗
DOE OSTI2026

Optimal Operation of Residential High Performance Water Heater for Reduction of Electricity Cost and Peak Demand Through Field Validation

Water heating accounts for about 18% of a typical US home’s energy use. Modern water heaters have enabled control options through APIs, offering customers the opportunity to reduce their energy cost and peak demand by dynamically adjusting settings. A water heater’s capacity to store energy using its storage tank makes it an asset for peak demand reduction and energy cost savings. For this reason, a mixed-integer linear programming model is proposed to minimize the energy cost of a high-performance water heater while also reducing the peak demand of the residential household under a time-of-use utility rate by dynamically changing the water heater’s running mode. Specifically, a multi-objective optimization model is formulated to determine the mode settings of the water heater considering hot water use, time-of-use rate, and peak demand limit of the residential household. The mode settings are associated with different dead bands of water temperature for triggering on/off action of the heat pump and heating element. A 66-gal hybrid electric high performance water heater was used for numerical simulation and practical experiments. The simulation results were well aligned with measurements of practical experiments, validating the soundness of the thermodynamic model. In addition, reductions of energy cost, enabling affordability, and reducing peak demand are demonstrated. The research team also developed a software framework with dashboards to automatically and continuously monitor and manage devices.

Liu, Guodong [ORNL] (ORCID:0000000213498608)↗