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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Hybrid Imitation Learning for Real-Time Service Restoration in Resilient Distribution Systems

Self-healing capability is a critical factor for a resilient distribution system, which requires intelligent agents to automatically perform service restoration online, including network reconfiguration and reactive power dispatch. Here, the article proposes the imitation learning framework for training such an agent, where the agent will interact with an expert built based on the mixed-integer program to learn its optimal policy, and therefore significantly improve the training efficiency compared with exploration-dominant reinforcement learning (RL) methods. This significantly improved training efficiency makes the training problem under N-k scenarios tractable. A hybrid policy network is proposed to handle tie-line operations and reactive power dispatch simultaneously to further improve the restoration performance. The 33-bus and 119-bus systems with N-k disturbances are employed to conduct the training. The results indicate that the proposed method outperforms traditional RL algorithms such as the deep-Q network.

42 ENGINEERING↗
DOE OSTI2024

Aerial drone fleet deployment optimization with endogenous battery replacements for direct delivery of time-sensitive products

Aerial drones offer a distinct potential to reduce the delivery time and energy consumption for the delivery of time-sensitive and small products. However, there is still a need in the relevant industry to understand the performance of drone-based delivery under different business needs and drone operating conditions. We studied a drone deployment optimization problem for direct delivery of time-sensitive products with release dates to customers maintaining a specified time window. This paper presents a new mixed-integer programming model, new valid inequalities, a new greedy heuristic algorithm, and a Genetic algorithm to help business owners optimally schedule and route their drone fleet minimizing the required fleet size, the required number of additional batteries, and total energy consumption. A realistic feature of the optimization method is that instead of replacing the drone battery after each return to the depot, it keeps track of the remaining energy in the drone battery and decides on battery replacements accounting for the drone routing and the user-specified minimum required battery energy. Numerical results based on real data from drone flight tests and prepared food delivery industry provide insights into the effect of different practical drone operating parameters on the required fleet size, the required number of battery replacements, and energy consumption. Here, results demonstrate that the proposed heuristic algorithm substantially outperforms the accelerated CPLEX in runtime while sacrificing the solution quality by a small amount. Additionally, results show that using a mixed fleet of hexacopter and quadcopter drones reduces the total energy consumption by 48.52% compared to using a homogeneous fleet of only hexacopters.

Drone energy consumption↗
NASA NTRS1986

Alternative mathematical programming formulations for FSS synthesis

A variety of mathematical programming models and two solution strategies are suggested for the problem of allocating orbital positions to (synthesizing) satellites in the Fixed Satellite Service. Mixed integer programming and almost linear programming formulations are presented in detail for each of two objectives: (1) positioning satellites as closely as possible to specified desired locations, and (2) minimizing the total length of the geostationary arc allocated to the satellites whose positions are to be determined. Computational results for mixed integer and almost linear programming models, with the objective of positioning satellites as closely as possible to their desired locations, are reported for three six-administration test problems and a thirteen-administration test problem.

Reilly, C. H.↗
DOE OSTI2021

Enhancing Active Distribution Systems Resilience by Fully Distributed Self-Healing Strategy

Distributed restoration can exploit smart grid technologies to enhance the resilience of active distribution networks toward a self-healing smart grid. However, the large number of decision variables, especially the binary ones for reconfiguration, bring challenges to developing scalable distributed distribution service restoration (DDSR) strategies. This paper proposes a fully distributed solution procedure based on the alternating direction method of multipliers (ADMM) for mixed-integer programming problems and applies to develop the DDSR framework. The method consists of relax-drive-polish phases, 1) relaxing binary variables, and applying the convex ADMM as a warm start; 2) driving the solutions toward Boolean values through a proximal operator; 3) fixing the obtained binding binary variables and solving the rest of the problem to polish results and achieve a high-quality suboptimal solution. Then, an autonomous clustering strategy and consensus ADMM are integrated with the proposed method to realize the fully distributed cluster-based framework of DDSR. This framework can first determine DER scheduling and switch status for reconfiguration to energize the out-of-service areas from local faults, and then provide the load restoration solution in a distributed manner for total blackouts in large-scale distribution networks. Furthermore, the effectiveness and scalability of the proposed DDSR framework are demonstrated through testing on the IEEE 123-node, IEEE 8500-node, and synthetic 100k-node test feeders.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

A Multi-Parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems

Optimization problems involving two decision makers at two different decision levels are referred to as bi-level programming problems. Herein, we present novel algorithms for the exact and global solution of two classes of bi-level programming problems, namely (i) bi-level mixed-integer linear programming problems (B-MILP) and (ii) bi-level mixed-integer convex quadratic programming problems (B-MIQP) containing both integer and bounded continuous variables at both optimization levels. Based on multi-parametric programming theory, the main idea is to recast the lower level problem as a multi-parametric programming problem, in which the optimization variables of the upper level problem are considered as bounded parameters for the lower level. The resulting exact multi-parametric mixed-integer linear or quadratic solutions are then substituted into the upper level problem, which can be solved as a set of single-level, independent, deterministic mixed-integer optimization problems. Extensions to problems including right-hand-side uncertainty on both lower and upper levels are also discussed. Finally, computational implementation and studies are presented through test problems.

42 ENGINEERING↗
DOE OSTI2019

A Bi-Level Formulation And Solution Method For The Integration Of Process Design And Scheduling

Design and operation decisions of manufacturing plants can often be expressed within a hierarchical structure, where optimal decisions at lower operating level provide constraints for the decision raking at a higher decision level. In this work, we are addressing the case of a hierarchical design and scheduling optimization problem. The integration of design and scheduling decisions can play a big role in designing economically profitable plants and improving their operational performance. This problem can be expressed as a bi-level problem, where design related decisions occur at the upper level and operational scheduling decisions at the lower level. Since discrete decisions are involved in both optimization levels, the resulting formulation typically corresponds to bi-level mixed-integer programming problems (B-MIP). The solution of B-MIP problems is very challenging, and typically requires the use of global optimization techniques, with many algorithms not able to guarantee feasibility. To overcome the challenges in solving this class of problems we propose the use of a multi-parametric based algorithm for the solution of bi-level mixed-integer linear and quadratic programming problems, capable of providing the exact and global solution. The main idea of this approach is to treat the lower scheduling problem as a multi-parametric programming problem in which the design decisions are considered as parameters. Here, the resulting parametric solutions can then be substituted into the upper level design problem, which can be solved as a set of single-level deterministic programming problems. Through the developed formulation and algorithm we are able to supply the decision makers with the exact solution of the integrated design and scheduling problem.

42 ENGINEERING↗
DOE OSTI2019

Utilising demand response for distribution service restoration to achieve grid resiliency against natural disasters

The increased frequency of power outages due to natural disasters in recent years has highlighted the urgency of enhancing distribution grid resilience. The effective distribution service restoration (DSR) is an important measure for a resilient distribution grid. In this work, the authors demonstrate that DSR can be significantly improved by leveraging the flexibility provided by the inclusion of demand response (DR). The authors propose a framework for this by considering integrated control of household-level flexible appliances to vary the load demand at the distribution-grid level to improve DSR. The overall framework of the proposed system is modelled as a three-step method considering three optimization problems to (i) calculate feasible controllable aggregated load range for each bus, (ii) determine candidate buses to perform DR and their target load demand, and (iii) maintain the load level in each house through home energy management during the DSR, considering uncertainties in load and solar generation sequentially. The optimization problems are formulated as linear programming, mixed-integer linear programming, and multistage stochastic programming (solved using the stochastic dual dynamic programming) models. Finally, case studies performed in the IEEE 123-node test feeder show improvements in resilience in terms of energy restored compared to the restoration process without DR.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1987

Mathematical programming formulations for satellite synthesis

The problem of satellite synthesis can be described as optimally allotting locations and sometimes frequencies and polarizations, to communication satellites so that interference from unwanted satellite signals does not exceed a specified threshold. In this report, mathematical programming models and optimization methods are used to solve satellite synthesis problems. A nonlinear programming formulation which is solved using Zoutendijk's method and a gradient search method is described. Nine mixed integer programming models are considered. Results of computer runs with these nine models and five geographically compatible scenarios are presented and evaluated. A heuristic solution procedure is also used to solve two of the models studied. Heuristic solutions to three large synthesis problems are presented. The results of our analysis show that the heuristic performs very well, both in terms of solution quality and solution time, on the two models to which it was applied. It is concluded that the heuristic procedure is the best of the methods considered for solving satellite synthesis problems.

Bhasin, Puneet↗
DOE OSTI2021

Optimal decision trees for categorical data via integer programming

Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mixed integer programming formulation to construct optimal decision trees of a prespecified size. We take the special structure of categorical features into account and allow combinatorial decisions (based on subsets of values of features) at each node. Our approach can also handle numerical features via thresholding. Here we show that very good accuracy can be achieved with small trees using moderately-sized training sets. The optimization problems we solve are tractable with modern solvers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Refueling infrastructure planning in intercity networks considering route choice and travel time delay for mixed fleet of electric and conventional vehicles

The range anxiety has been a major factor that affects the market acceptance of electric vehicles. Even with the recent development of battery technologies, a lack of charging stations and range anxiety are still significant concerns, specifically for intercity trips. This calls for more investments in building charging stations and advancing battery technologies to increase the market share of electric vehicles and improve sustainability. This study suggests a configuration for plug-in electric vehicle charging infrastructure to support long-distance intercity trips of electric vehicles at the network level. A model is proposed to minimize the total system cost including infrastructure investment (building charging stations/spots) and travel time delays (charging time, waiting time in the queue, and detour time to access charging stations). This study fills existing gaps in the literature by capturing realistic patterns of travel demand and considering flow-dependent charging delays at charging stations. Furthermore, the proposed model, which is formulated as a mixed-integer program with nonlinear constraints, solves the optimization problem at the network level. At the network level, impacts of charging station locations on the traffic assignment problem with a mixed fleet of electric and conventional vehicles need to be considered. To this end, a traffic assignment module is integrated with a simulated annealing algorithm. The numerical experiments show a satisfactory application of the model for a full-scale case study (intercity network in Michigan). The solution quality and efficiency of the proposed solution algorithm are evaluated against those of an enumeration approach for a small case study. The results suggest that even for the current market share and charging stations’ setting, a significant investment is needed to support intercity trips without range anxiety issues and with acceptable delays. Additionally, through sensitivity analyses, the required infrastructure and battery investments to support intercity trips with acceptable delays are established for hypothetical increased market shares and battery size in the future.

42 ENGINEERING↗
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 OSTI2022

A shared-mobility-based framework for evacuation planning and operations under forecast uncertainty

To meet evacuation needs from carless populations who need personalized assistance to evacuate safely, in this article we propose a ridesharing-based evacuation program that recruits volunteer drivers before a disaster strikes, and then matches volunteer drivers with evacuees once demand is realized. Here we optimize resource planning and evacuation operations under uncertain spatiotemporal demand, and construct a two-stage stochastic mixed-integer program to ensure high demand fulfillment rates. We consider three formulations to improve the number of evacuees served, by minimizing an expected penalty cost, imposing a probabilistic constraint, and enforcing a constraint on the conditional value at risk of the total number of unserved evacuees, respectively. We discuss the benefits and disadvantages of the different risk measures used in the three formulations, given certain carless population sizes and the variety of evacuation modes available. We also develop a heuristic approach to provide quick, dynamic and conservative solutions. We demonstrate the performance of our approaches using five different networks of varying sizes based on regions of Charleston County, South Carolina, an area that experienced a mandatory evacuation order during Hurricane Florence, and utilize real demographic data and hourly traffic count data to estimate the demand distribution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Model Predictive Control of Discrete-Continuous Energy Systems via Generalized Disjunctive Programming

Generalized Disjunctive Programming (GDP) provides an alternative framework to model optimization problems with both discrete and continuous variables. The key idea behind GDP involves the use of logical disjunctions to represent discrete decisions in the continuous space, and logical propositions to denote algebraic constraints in the discrete space. Compared to traditional mixed-integer programming (MIP), the inherent logic structure in GDP yields tighter relaxations that are exploited by global branch and bound algorithms to improve solution quality. In this paper, we present a general GDP model for optimal control of hybrid systems that exhibit both discrete and continuous dynamics. Specifically, we use GDP to formulate a model predictive control (MPC) model for piecewise-affine systems with implicit switching logic. As an example, the GDP-based MPC approach is used as a supervisory control to improve energy efficiency in residential buildings with binary on/off, relay-based thermostats. A simulation study is used to demonstrate the validity of the proposed approach, and the improved solution quality compared to existing MIPbased control approaches.

Bhattacharya, Arnab↗
DOE OSTI2019

Allocating limited deicing resources in winter snow events

As the number and severity of snowfall events continue to grow, the need to direct road maintenance intelligently during these snowfall events will also grow. In several locations, local governments lack the resources to treat all roadways completely during snow events. Furthermore, some governments utilize only traffic data to determine which roads should be treated. As a result, many schools, businesses, and government offices must be unnecessarily closed, which directly impacts the social, educational, and economic well-being of citizens and institutions. In this work, we propose a mixed integer programming (MIP) formulation to allocate resources to manage snowfall on roads using meteorological, geographical, and environmental parameters. Furthermore, given that MIPs often scale poorly with problem size, we also present a constructive heuristic designed for the problem. Finally, we evaluate the impacts of an increase in budget for winter road maintenance on snow control resources.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

A scalable stochastic programming approach for the design of flexible systems

We study the problem of designing systems in order to minimize cost while meeting a given flexibility target. Flexibility is attained by enforcing a joint chance constraint, which ensures that the system will exhibit feasible operation with a given target probability level. Unfortunately, joint chance constraints are complicated mathematical objects that often need to be reformulated using mixed-integer programming (MIP) techniques. In this work, we cast the design problem as a conflict resolution problem that seeks to minimize cost while maximizing flexibility. We propose a purely continuous relaxation of this problem that provides a significantly more scalable approach relative to MIP methods and show that the formulation delivers solutions that closely approximate the Pareto set of the original joint chance-constrained problem.

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

Stochastic Optimization for Grid Resilience. FY18 Final Technical Report

The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this report we present a scalable decomposition algorithm for solving this problem for realistic power systems. The algorithm has been developed in three major research threads, corresponding to the chapters in the present report. Chapter 1 studies mixed-integer programming (MIP) formulations for the requirement that each electrical island that appears after a recon guration must have at least one energized generator. We provide three alternative MIP formulations for this restriction, show their equivalence, and prove that two of them are stronger in terms of their linear programming relaxation than the formulation most commonly used in the power systems literature. Since the time to solve MIPs can vary signi cantly between equivalent formulations, we also present computational experiments on IEEE test systems for the Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) problems. We observe that a polynomially separable, exponential in size, strong formulation yields the best performance for the BSA problem and exhibits a comparable performance to a linear in size, weak formulation for the ICI problem. Chapter 2 presents a methodology to generate mixed-integer linear approximations of the AC power ow equations governing lines, transformers (including tap regulators and phase shifters), shunt and series compensators, and consumption responsive to voltage. Our approximations are capable of capturing limitations for power grids under abnormal or uncommon operating conditions where common assumptions used in power ow relaxations may not hold. Particularly, the approximation captures overvoltages under almost no load, which is a major concern when energizing lines after a blackout. The method constructs piecewise linear approximations of the non-linear power ow equations by minimizing the squared approximation error over a subset of the feasible domain. We test the method using a realistic database for the Chilean system (1548 buses, 1114 lines, 564 transformers). The resulting approximations yield root mean square errors in the order of 0.05pu and are successfully applied to solve a transmission switching instance for the Chilean system. Chapter 3 presents our algorithm for optimal restoration. The algorithm works by partitioning the problem into a master problem and a slave problem. The master problem optimizes over energization sequences of generators, buses and branches, for the entire restoration horizon, while respecting the energization requiments studied in Chapter 1. The slave problem veri es that there exist power ow solutions supporting the energization sequences proposed by the master problem, adding cuts to the master if an infeasible sequence is detected.

24 POWER TRANSMISSION AND DISTRIBUTION↗
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↗
NASA NTRS1981

An optimization model for energy generation and distribution in a dynamic facility

An analytical model is described using linear programming for the optimum generation and distribution of energy demands among competing energy resources and different economic criteria. The model, which will be used as a general engineering tool in the analysis of the Deep Space Network ground facility, considers several essential decisions for better design and operation. The decisions sought for the particular energy application include: the optimum time to build an assembly of elements, inclusion of a storage medium of some type, and the size or capacity of the elements that will minimize the total life-cycle cost over a given number of years. The model, which is structured in multiple time divisions, employ the decomposition principle for large-size matrices, the branch-and-bound method in mixed-integer programming, and the revised simplex technique for efficient and economic computer use.

Lansing, F. L.↗