Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Mixed integer optimization”

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

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

At least 415 records · Page 23
All sourcesNASA NTRSDOE OSTI
DOE OSTI2019

Optimal Scheduling of an Isolated Microgrid With Battery Storage Considering Load and Renewable Generation Uncertainties

By modeling the uncertainty of spinning reserves provided by energy storage with probabilistic constraints, a new optimal scheduling mode is proposed in this paper for minimizing the operating costs of an isolated microgrid (MG) by using chance-constrained programming. The model is transformed into a readily solvable mixed integer linear programming formulation in general algebraic modeling system (GAMS) via a proposed discretized step transformation approach and finally solved by applying the CPLEX solver. By properly setting the confidence levels of the spinning reserve probability constraints, the MG operation can achieve a tradeoff between reliability and economy. The test results on the modified Oak Ridge National Laboratory Distributed Energy Control and Communication lab MG test system reveal that the proposal significantly exceeds the commonly used hybrid intelligent algorithm with much better and more stable optimization results and significantly reduced calculation times.

Li, Yang↗
DOE OSTI2021

Deterministic symbolic regression with derivative information: General methodology and application to equations of state

Symbolic regression methods simultaneously determine the model functional form and the regression parameter values by generating expression trees. Symbolic regression can capture the complexity of real–world phenomena but the use of deterministic optimization for symbolic regression has been limited due to the complexity of the search space of existing formulations. Herein we present a novel deterministic mixed–integer nonlinear programming formulation for symbolic regression that incorporates derivative constraints through auxiliary expression trees. By applying the chain rule to mathematical operations, binary expression trees are capable of representing the calculation of first and second derivatives. We apply this formulation to illustrative examples using derivative information to show increased model discrimination capability. In addition, we perform a case study of a thermodynamic equation of state to gain insight on valid functional forms with thermodynamics–based constraints on the first and second derivatives.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Restoration Strategy for Active Distribution Systems Considering Endogenous Uncertainty in Cold Load Pickup

Cold load pickup (CLPU) phenomenon is identified as the persistent power inrush upon a sudden load pickup after an outage. Under the active distribution system (ADS) paradigm, where distributed energy resources (DERs) are extensively installed, the decreased outage duration can induce a strong interdependence between CLPU pattern and load pickup decisions. In this paper, we propose a novel modelling technique to tractably capture the decision-dependent uncertainty (DDU) inherent in the CLPU process. Subsequently, a two-stage stochastic decision-dependent service restoration (SDDSR) model is constructed, where first stage searches for the optimal switching sequences to decide step-wise network topology, and the second stage optimizes the detailed generation schedule of DERs as well as the energization of switchable loads. Further, to tackle the computational burdens introduced by mixed-integer recourse, the progressive hedging algorithm (PHA) is utilized to decompose the original model into scenario-wise subproblems that can be solved in parallel. The numerical test on modified IEEE 123-node test feeders has verified the efficiency of our proposed SDDSR model and provided fresh insights into the monetary and secure values of DDU quantification.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Optimization Models For Drone Deployment

Model that supports drone deployment. Analysis on speed, package weight, energy consumption, # of drones, and battery replacements. This software developed tools for drone deployment optimization for direct delivery by introducing a new model that presents new insights addressing real-life issues. Specifically, this developed a new mixed-integer programming model with both time windows and battery replacements.

Roni, MohammadS↗
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↗
DOE OSTI2025

PDPTW-DB: MILP-Based Offline Route Planning for PDPTW with Driver Breaks

The Pickup and Delivery Problem with Time Windows (PDPTW) involves optimizing routes for vehicles to meet pickup and delivery requests within specific time constraints, a challenge commonly faced in logistics and transportation. Microtransit, a flexible and demand-responsive service using smaller vehicles within defined zones, can be effectively modeled as a PDPTW. Yet, the need for driver breaks—a key human constraint—is frequently overlooked in PDPTW solutions, despite being necessary for regulatory compliance. This study presents a novel mixed-integer linear programming formulation for the Pickup and Delivery Problem with Time Windows and Driver Breaks (PDPTW-DB). To the best of our knowledge this formulation is the first to consider mandatory periodic driver breaks within optimized Microtransit routes. The proposed model incorporates regulatory compliant break scheduling directly within the vehicle routing optimization framework. By considering driver break requirements as an integral component of the optimization process, rather than as a post-processing step, the model enables the generation of routes that respect hours of service regulations while minimizing operational costs. This integrated approach facilitates the generation of schedules that are operationally efficient and prioritize driver welfare through driver breaks. We work with a public transit agency from the southern USA, and highlight the specific nuances of driver break optimization, and present a Pickup and Delivery Problem with Time Windows formulation for optimizing Microtransit operations and scheduling driver breaks. We validate our approach using real-world data from the transit agency. Our results validate our formulation in producing cost-effective, and regulation-compliant solutions.

Applied Computing, Transportation↗
DOE OSTI2022

Stochastic scheduling of generating units with weekly energy storage: A hybrid decomposition approach

We propose a solution method for the large-scale stochastic unit commitment (SUC) problem with weekly-dispatched energy storage and significant weather-dependent stochastic generating capacity. Weekly storage facilities that mostly charge during weekends and discharge during weekdays require a weekly scheduling of generating units, which result in a large-scale optimization problem. This SUC problem is formulated as a two-stage stochastic model and we use the conditional value-at-risk as a risk measure. Using a Benders framework, the proposed solution method decomposes the problem into a mixed-integer linear master problem and linear and continuous subproblems. The master problem corresponds to the first-stage decisions throughout the week and includes all the commitment (binary) variables and their corresponding constraints. The subproblems correspond to the actual dispatch of the generating units on a weekly basis. Based on the success of column-and-constraint generation algorithms to solve robust optimization problems, we improve the low communication between the master problem and the subproblems in the standard Benders decomposition by adding primal variables and constraints from the subproblems to the master problem, which provides a better approximation of the recourse function. Furthermore, our computational experiments demonstrate the effectiveness of the proposed decomposition method using an instance of the South Carolina synthetic system with 90 generating units under 40 scenarios.

25 ENERGY STORAGE↗
DOE OSTI2023

Linear model decision trees as surrogates in optimization of engineering applications

Machine learning models are promising as surrogates in optimization when replacing difficult to solve equations or black-box type models. This work demonstrates the viability of linear model decision trees as piecewise-linear surrogates in decision-making problems. Linear model decision trees can be represented exactly in mixed-integer linear programming (MILP) and mixed-integer quadratic constrained programming (MIQCP) formulations. Furthermore, they can represent discontinuous functions, bringing advantages over neural networks in some cases. We present several formulations using transformations from Generalized Disjunctive Programming (GDP) formulations and modifications of MILP formulations for gradient boosted decision trees (GBDT). We then compare the computational performance of these different MILP and MIQCP representations in an optimization problem and illustrate their use on engineering applications. Importantly, we observe faster solution times for optimization problems with linear model decision tree surrogates when compared with GBDT surrogates using the Optimization and Machine Learning Toolkit (OMLT).

42 ENGINEERING↗
DOE OSTI2020

Optimization-Driven Scenario Grouping

Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. Here, we develop an approach that improves on these bounds by reinforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into groups. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present two formulations for solving the problem: a matching formulation for a special case and a mixed-integer programming formulation for the general case. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness in solving standard test instances of two-stage 0–1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Additionally, we implement this scheme as a preprocessing step for PySP, a publicly available and widely used implementation of progressive hedging, and compare this grouping approach with standard grouping approaches on large-scale stochastic unit commitment instances. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Communication-Constrained Expansion Planning for Resilient Distribution Systems

Distributed generation and remotely controlled switches have emerged as important technologies to improve the resiliency of distribution grids against extreme weather-related disturbances. Therefore it becomes important to study how best to place them on the grid in order to meet a resiliency criteria, while minimizing costs and capturing their dependencies on the associated communication systems that sustain their distributed operations. This paper introduces the Optimal Resilient Design Problem for Distribution and Communication Systems (ORDPDC) to address this need. The ORDPDC is formulated as a two-stage stochastic mixed-integer program that captures the physical laws of distribution systems, the communication connectivity of the smart grid components, and a set of scenarios that specifies which components are affected by potential disasters. The paper proposes an exact branch-and-price algorithm for the ORDPDC that features a strong lower bound and a variety of acceleration schemes to address degeneracy. The ORDPDC model and branch-and-price algorithm were evaluated on a variety of test cases with varying disaster intensities and network topologies. The results demonstrate the significant impact of the network topologies on the expansion plans and costs, as well as the computational benefits of the proposed approach.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Generalized optimization-based synthesis of membrane systems for multicomponent gas mixture separation

Synthesizing a membrane system to separate multicomponent gas mixture is challenging due to the combinatorial number of feasible configurations and the difficulties in describing the multicomponent permeators. Here we present a mixed-integer nonlinear programming (MINLP) model for synthesizing membrane systems for multicomponent gas mixture separation. The approach employs a richly connected superstructure to represent numerous potential system configurations, and different physics-based surrogate permeator models, such as countercurrent flow or crossflow, to be used in each stage. Moreover, to describe realistic systems, pressure drop equations can be included. We also present solution methods to accelerate the solution process. Through a case study of natural gas sweetening, we demonstrate that the proposed approach is able to obtain good solutions using an off-the-shelf global optimization solver. Finally, we expand the conventional membrane system synthesis problem by introducing feed variability in our model through a case study of an integrated reactor-separation system.

42 ENGINEERING↗
DOE OSTI2022

Optimal Electric Grid Black Start Restoration Subject to Intentional Threats

Efficient restoration of the electric grid from significant disruptions – both natural and manmade – that lead to the grid entering a failed state is essential to maintaining resilience under a wide range of threats. Restoration follows a set of black start plans, allowing operators to select among these plans to meet the constraints imposed on the system by the disruption. Restoration objectives aim to restore power to a maximum number of customers in the shortest time. Current state-of-the-art for restoration modeling breaks the problem into multiple parts, assuming a known network state and full observability and control by grid operators. These assumptions are not guaranteed under some threats. This paper focuses on a novel integration of modeling and analysis capabilities to aid operators during restoration activities. A power flow-informed restoration framework, comprised of a restoration mixed-integer program informed by power flow models to identify restoration alternatives, interacts with a dynamic representation of the grid through a cognitive model of operator decision-making, to identify and prove an optimal restoration path. Application of this integrated approach is illustrated on exemplar systems. Validation of the restoration is performed for one of these exemplars using commercial solvers, and comparison is made between the steps and time involved in the commercial solver, and that required by the restoration optimization in and of itself, and by the operator model in acting on the restoration optimization output. Publications and proposals developed under this work, along with a path forward for additional expansion of the work, and summary of what was achieved, are also documented.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2023

Mathematical Programming Models for Shale Oil & Gas Development: A Review and Perspective

Here, in this paper, we provide a comprehensive review of mathematical programming models for shale oil & gas development, and we offer a perspective on outstanding research opportunities. We distinguish contributions in five major topic areas, namely: (1) development planning, (2) water management, (3) production optimization, (4) supplies, gathering & processing, and (5) life cycle analysis & sustainability. We highlight how various types of mathematical programming models (i.e., linear programs, nonlinear programs, mixed-integer linear programs, mixed-integer nonlinear programs) have been proposed primarily by the Process Systems Engineering community to address the respective decision-making problems, and we highlight instances of successful deployment in industry. Finally, based on a critical assessment of the existing body of work, we identify opportunities for future research across the major topic areas.

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

A decomposition-based design optimization method with applications

A two-level design optimization metholology is described. A progress report of its application to Printed Wiring Board (PWB) assembly examples is given. The design of PWB assemblies is a complex task which is generally conducted as a sequential process. Individual PWBs are usually designed first, followed by the composition of the PWBs into an assembly. As a result, optimizing design considerations such as assembly reliability cannot be accomplished. This study showed that a two-level decomposition method can be employed to optimize for reliability at both the PWB- and the assembly-level in a coupled manner. The two-level decomposition method also resolved the mixed-integer nonlinear programming nature of the problem rather easily.

Azarm, Shapour↗
DOE OSTI2021

Efficient Automated Driving Strategies Leveraging Anticipation and Optimal Control

Automated vehicles and advanced driver assistance systems bring computation, sensing, and communication technologies that exceed human abilities in some ways. For example, automated vehicles may sense a panorama all at once, do not suffer from human impairments and distractions, and could wirelessly communicate precise data with neighboring vehicles. Prototype and commercial deployments have demonstrated the capability to relieve human operators of some driving tasks up to and including fully autonomous taxi rides in some areas. The ultimate impact of this technology’s large-scale market penetration on energy efficiency remains unclear, with potential negative factors like road use by empty vehicles competing with positive ones like automatic eco-driving. Fundamentally enabled by historic and look-ahead data, this dissertation addresses the use of automated driving and driver assistance to optimize vehicle motion for energy efficiency. Facets of this problem include car following, co-optimized acceleration and lane change planning, and collaborative multi-agent guidance. Optimal control, especially model predictive control, is used extensively to improve energy efficiency while maintaining safe and timely driving via constraints. Techniques including chance constraints and mixed integer programming help overcome uncertainty and non-convexity challenges. Extensions of these techniques to tractor trailers on sloping roads are provided by making use of linear parameter-varying models. To approach the wheel-input energy eco-driving problem over generally shaped sloping roads with the computational potential for closed-loop implementation, a linear programming formulation is constructed. Distributed and collaborative techniques that enable connected and automated vehicles to accommodate their neighbors in traffic are also explored and compared to centralized control. Using simulations and vehicle-in-the-loop car following experiments, the proposed algorithms are benchmarked against others that do not make use of look-ahead information.

Dollar, Robert Austin↗
DOE OSTI2022

Managing Power Systems-Induced Wildfire Risks Using Optimal Scheduled Shutoffs: Preprint

The growing demands for electricity and the increase in extreme weather conditions are putting unprecedented pressure on our electrical grids. Oftentimes, this pressure leads to electrical components failures which might ignite wildfires. This work develops a novel model to balance the reliability of power networks operations and risks of wildfires ignition by optimizing the operational schedule of power transmission networks considering time-varying risk measures that consider exogenous and operational factors. Energy storage systems are considered to deliver power during peak wildfire hours and enable temporal load shifting. The problem is formulated as a mixed-integer linear program that maximizes a weighted sum of the served power demand and the reduction in grid-induced wildfires risk. The results demonstrate the ability of the model to reduce wildfires risks significantly without considerable load shedding.

energy scheduling↗