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

Modeling the AC Power Flow Equations with Optimally Compact Neural Networks: Application to Unit Commitment

Nonlinear power flow constraints render a variety of power system optimization problems computationally intractable. Emerging research shows, however, that the nonlinear AC power flow equations can be successfully modeled using neural networks. These neural networks can be exactly transformed into mixed integer linear programs and embedded inside challenging optimization problems, thus replacing nonlinearities that are intractable for many applications with tractable piecewise linear approximations. Such approaches, though, suffer from an explosion of the number of binary variables needed to represent the neural network. Accordingly, this paper develops a technique for training an "optimally compact'' neural network, i.e., one that can represent the power flow equations with a sufficiently high degree of accuracy while still maintaining a tractable number of binary variables. We demonstrate the use of this neural network as an approximator of the nonlinear power flow equations by embedding it in the AC unit commitment problem, transforming the problem from a mixed integer nonlinear program into a more manageable mixed integer linear program. We use the 14-, 57-, and 89-bus networks as test cases and compare the AC-feasibility of commitment decisions resulting from the neural network, DC, and linearized power flow approximations. Our results show that the neural network model outperforms both the DC and linearized power flow approximations when embedded in the unit commitment problem. The neural network formulation most often selects a feasible unit commitment schedule, and furthermore, it only s

AC power flow↗
DOE OSTI2020

Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. Here, we also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Optimal Network Topology for Node-Breaker Representations With AC Power Flow Constraints

It has been demonstrated that network topology optimization (NTO) may change the topology of power system networks, and consequently, provide additional flexibility to reduce network congestion and violations. Most NTO problems are formulated based on the bus-branch model in which it is challenging to represent a realistic picture of all substation configurations. In this paper, we explore advantages of substation reconfiguration modeling based on node-breaker representations for NTO problem with full nonlinear alternating current power flow. It also proposes a tailored solution algorithm to solve this nonconvex mixed-integer nonlinear programming through the outer approximation method. The proposed solution approach iterates between a mixed-integer linear programming and a nonlinear subproblem. Additional enhancements to further accelerate the iteration process are illustrated. Numerical case studies demonstrate the relative economic and operational impact of optimal network topology with node-breaker representations.

42 ENGINEERING↗
DOE OSTI2021

Proactive Operations and Investment Planning via Stochastic Optimization to Enhance Power Systems’ Extreme Weather Resilience

We present scalable stochastic optimization approaches for improving power systems’ resilience to extreme weather events. We consider both proactive redispatch and transmission line hardening as alternatives for mitigating expected load shed due to extreme weather, resulting in large-scale stochastic linear programs (LPs) and mixed-integer linear programs (MILPs). We solve these stochastic optimization problems with progressive hedging (PH), a parallel, scenario-based decomposition algorithm. Our computational experiments indicate that our proposed method for enhancing power system resilience can provide high-quality solutions efficiently. With up to 128 scenarios on a 2,000-bus network, the operations (redispatch) and investment (hardening) resilience problems can be solved in approximately 6 min and 2 h of wall-clock time, respectively. Additionally, we solve the investment problems with up to 512 scenarios, demonstrating that the approach scales very well with the number of scenarios. Moreover, the method produces high quality solutions that result in statistically significant reductions in expected load shed. Our proposed approach can be augmented to incorporate a variety of other operational and investment resilience strategies, or a combination of such strategies.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

The allocation of a variable series reactor considering AC constraints and contingencies

The Variable Series Reactors (VSRs) can efficiently control the power flow through the adjustment of the line reactance. When they are appropriately allocated in the power network, the transmission congestion and generation cost can be reduced. Our work proposes a planning model to optimally allocate VSRs considering AC constraints and multi-scenarios including base case and contingencies. The planning model is originally a non-convex large scale mixed integer nonlinear program (MINLP), which is generally intractable. The proposed Benders approach decomposes the MINLP model into a mixed integer linear program (MILP) master problem and a number of nonlinear subproblems. Numerical case studies based on IEEE 118-bus demonstrate the high performance of the proposed approach.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

An MINLP formulation for the optimization of multicomponent distillation configurations

Designing configurations for multicomponent distillation, a ubiquitous process in chemical and petrochemical industries, is often challenging. This is because, as the number of components increases, the number of admissible distillation configurations grows rapidly and these configurations vary substantially in their energy needs. Consequently, if a method could identify a few energy-efficient choices from this large set of alternatives, it would be extremely attractive to process designers. This paper develops here such a method by solving a Mixed Integer Nonlinear Program (MINLP) that is formulated to pick, among the regular-column configurations of Shah and Agrawal (2010b), those configurations that have a low vapor-duty requirement. To compute the minimum vapor-duty requirement for each column within the configuration, we use techniques that rely on the Underwood’s method. The combined difficulty arising from the nonlinearity of Underwood equations and the combinatorial explosion of the choice-set of alternatives poses unmistakable challenges for the branch-and-bound algorithm, the current method of choice to globally solve MINLPs. To address this difficulty, we exploit the structure of Underwood equations and derive valid cuts that expedite the convergence of branch-and-bound by enabling global solvers, such as BARON, infer tighter bounds on Underwood roots. This provides a quick way to identify a few lucrative alternative configurations for separation of a given non-azeotropic mixture. We illustrate the practicality of our approach on a case-study concerning heavy-crude distillation and on various other examples from the literature.

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

Evaluation of Horizon of Viability Optimization Engine for Sustained Power to Critical Infrastructure: Preprint

In the aftermath of increasingly frequent catastrophic events, a typical scenario is Critical Infrastructure (CI) units being supported by available backup sources with a weak power grid that can be intermittent or absent. Such a scenario is significantly challenging in the sense of reliable supply of power to CI units. In this article, an intelligent optimization scheme termed as Horizon of Viability (HoV) engine is developed to guarantee the viability of a sustained reliable supply of power to the CI units over a time-horizon. The proposed HoV engine generates a cost-optimal portfolio of the locally available generation sources and the loads over a time horizon using a mixed-integer convex programming problem. A Controller hardware-in-the-loop (CHIL) platform is developed to evaluate the control performance of the HoV engine. The experimental results corroborates the efficacy in maintaining the viability of the CI units after a grid interruption event. Further, the proposed HoV optimization scheme performs better compared to existing net-load management schemes in the literature.

disaster resiliency↗
DOE OSTI2023

Dispatch optimization of electric thermal energy storage within System Advisor Model

A stand-alone electric thermal energy storage (ETES) system converts low-value electricity into heat using resistance heating elements. During periods of high-value electricity, an ETES system uses a thermodynamic power cycle to convert stored thermal energy back to electricity. These dispatchable systems derive value from their ability to store energy when prices are low and generate electricity when prices are favorable, i.e., energy arbitrage. Consequently, dispatch optimization of system operations, through maximizing revenue subject to system constraints, is essential to evaluate the economic value of a particular system design. While stand-alone ETES systems offer potential advantages as dispatchable grid storage technologies, there is a lack of a neutral third-party, publicly available, open-source model to evaluate the performance, dispatch, and financial viability of these systems. To address this problem, we have developed a techno-economic model for stand-alone ETES systems, within National Renewable Energy Laboratory's (NREL's) System Advisor Model (SAM). We implement a mixed-integer linear program to determine an ETES optimal operating schedule that maximizes electricity sales less maintenance costs caused by operation and cycling given temporal-varying grid electricity prices. Our contributions include a mixed-integer linear program for energy arbitrage of an ETES system, an ETES performance model through a publicly-available software (i.e., SAM), and an exercise of our model through case studies that compare ETES operational strategies and annual financial metrics. With our dispatch optimization model, we were able to improve revenue by 20% compared to a myopic heuristic while reducing the operational cost of the ETES system through decreases in cycle starts, cycles per day, and heater starts.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

From graphical to model-based distillation column design: A McCabe-Thiele-inspired mathematical programming approach

We propose a mixed-integer nonlinear programming (MINLP) model for simple and complex distillation column design and optimization. The model is based upon the concepts and equations underpinning the McCabe-Thiele method. Generalizing this method, we introduce material balances at various locations of the column and employ binary variables to determine the optimal number of trays and optimal feed locations. We model the vapor–liquid equilibrium using continuous piecewise linear approximating functions. The model is extended to account for multicomponent mixtures and non-constant-molar overflow. We also discuss how to estimate the minimum number of trays and the minimum reflux ratio.

42 ENGINEERING↗
DOE OSTI2021

Joint Topology Identification and State Estimation in Unobservable Distribution Grids

Many distribution system operations (e.g., state estimation, control, fault detection/localization) rely on the assumption that the underlying topology is accurately defined. In general, topology identification is a challenging problem in distribution systems as these systems are unobservable with a very limited number of available measurements. In this paper, we tackle this problem by designing a compressive sensing framework that jointly estimates the systems states and network topology via an integrated mixed integer nonlinear program (MINLP) formulation. Here, two reformulations of the original MINLP problems are investigated. Firstly, in order to remove the nonlinearity in the MINLP formulation, a mixed integer linear programming (MILP) problem that employs auxiliary variables is derived. Furthermore, to achieve a faster solution, convex relaxation of the original formulation is derived. Finally, using a Markovian model for topology changes, prior information about system topology is used to improve topology identification particularly when a limited amount of measurements is available. Simulation results on IEEE 37-bus test feeder and IEEE 123-bus test feeder illustrate the efficiency and scalability of the proposed approaches from both state estimation and topology identification point of view (even with 30% of available data).

42 ENGINEERING↗
DOE OSTI2019

ADP-Based Home Energy Management System: A Case Study Using Dynamo: Preprint

This paper explores Home Energy Management System (HEMS) algorithms to minimize household cost while maintaining comfort when faced with uncertain weather, and demand. Specifically, we consider a HEMS that optimizes forward looking schedules for a home's heating, ventilation, and air conditioning (HVAC); water heater (WH); and electric vehicle (EV) charging while considering uncertainty in outside temperature, hot water usage, and non-controllable load (NCL). We adopt a Dynamic Programming (DP) formulation and utilize the Dynamic programming for Adaptive Modeling and Optimization (DYNAMO) toolkit to implement DP and approximate dynamic programming (ADP) algorithms. Simulation results under a single tariff plan compare the quality of the solution generated by ADP to that of DP, and show significant improvement in computation time while maintaining acceptable solution accuracy.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Optimizing Vehicle Fleet and Assignment for Concentrating Solar Power Plant Heliostat Washing

Concentrating solar power central-receiver plants use thousands of sun-tracking mirrors, i.e., heliostats, to reflect sunlight to a central receiver, which collects and uses the heat to generate electricity. Over time, soiling reduces the reflectivity of the heliostats and, therefore, the efficiency of the system. Current industry practice sends vehicles to wash heliostats in an ad hoc fashion. We present a mixed-integer nonlinear program that determines wash vehicle fleet size, mix, and assignment of wash crews to heliostats to minimize the sum of (i) the revenues lost due to heliostat soiling, (ii) the costs of hiring wash crews and operating the vehicles, and (iii) the costs of purchasing wash vehicles. We establish conditions for convexity of the objective function, and then propose a decomposition method that enables near-optimal solutions to the wash vehicle fleet sizing and assignment problem on the order of a couple of minutes. Furthermore, these solutions yield hundreds of thousands of dollars in savings per year over current industry practices.

14 SOLAR ENERGY↗
DOE OSTI2025

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

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

Olson, Daniel↗
DOE OSTI2019

An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs

We develop an adaptive, multivariate partitioning algorithm for solving nonconvex, Mixed-Integer Nonlinear Programs (MINLPs) with polynomial functions to global optimality. In particular, we present an iterative algorithm that exploits piecewise, convex relaxation approaches via disjunctive formulations to solve MINLPs that is different than conventional spatial branch-and-bound approaches. The algorithm partitions the domains of variables in an adaptive and non-uniform manner at every iteration to focus on productive areas of the search space. Furthermore, domain reduction techniques based on sequential, optimization-based bound-tightening and piecewise relaxation techniques, as a part of a presolve step, are integrated into the main algorithm. Finally, we demonstrate the effectiveness of the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare our algorithm with state-of-the-art global optimization solvers. With our novel approach, we solve several large-scale instances, some of which are not solvable by state-of-the-art solvers. We also succeed in reducing the best known optimality gap for a hard, generalized pooling problem instance.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems

Security-constrained unit commitment (SCUC) is a fundamental problem in power systems and electricity markets. In practical settings, SCUC is repeatedly solved via mixed-integer linear programming (MIP), sometimes multiple times per day, with only minor changes in input data. In this work, we propose a number of machine learning techniques to effectively extract information from previously solved instances in order to significantly improve the computational performance of MIP solvers when solving similar instances in the future. Based on statistical data, we predict redundant constraints in the formulation, good initial feasible solutions, and affine subspaces where the optimal solution is likely to lie, leading to a significant reduction in problem size. Computational results on a diverse set of realistic and large-scale instances show that using the proposed techniques, SCUC can be solved on average 4.3 times faster with optimality guarantees and 10.2 times faster without optimality guarantees, with no observed reduction in solution quality. Out-of-distribution experiments provide evidence that the method is somewhat robust against data-set shift. Summary of Contribution. The paper describes a novel computational method, based on a combination of mixed-integer linear programming (MILP) and machine learning (ML), to solve a challenging and fundamental optimization problem in the energy sector. The method advances the state-of-the-art, not only for this particular problem, but also, more generally, in solving discrete optimization problems via ML. We expect that the techniques presented can be readily used by practitioners in the energy sector and adapted, by researchers in other fields, to other challenging operations research problems that are solved routinely.

Machine Learning↗
DOE OSTI2021

The nth-plant scenario for blended feedstock conversion and preprocessing nationwide: biorefineries and depots

The sustainability of the biofuel industry depends on the development of a mature conversion technology on a national level that can take advantage of the economies of scale: the nth-plant. Defining the future location and supply logistics of conversion plants is imperative to ultimately transform the nation’s renewable biomass resources into cost-competitive, high-performance feedstock for production of biofuels and bioproducts. Since the US has put restrictions on production levels of conventional biofuels from edible resources, the nation needs to plan for the widespread accessibility and development of the cellulosic biofuel scenario. Conventional feedstock supply systems will be unable to handle cellulosic biomass nationwide, making it essential to expand the industry with an advanced feedstock supply system incorporating a distributed network of preprocessing depots and conversion plants, or biorefineries. Current studies are mostly limited to designing supply systems for specific regions of the country. We developed a national database with potential locations for depots and biorefineries to meet the nation’s target demand of cellulosic biofuel. Blended feedstock with switchgrass and corn stover (harvested by either a two- or three-pass method) are considered in a Mixed Integer Linear Programming model to deliver on-spec biomass that considers both, a desired quantity and quality at the biorefinery. A total delivered feedstock cost that is less than $79.07/dt (2016$) is evaluated for years 2022, 2030, and 2040. In 2022, 124 depots and 59 biorefineries could be supplied with 42.8 million dt of corn stover and switchgrass. In 2030 and 2040, the total accessible biomass could increase to 215% and 393% respectively when compared to 2022. However, an $8/dry tons reduction in targeted delivery cost could reduce total accessible biomass by 67%. Kansas, Nebraska, South Dakota and Texas were identified as potential states with a strong biofuel economy given that they had six or more biorefineries located in all scenarios. In some scenarios, Colorado, Alabama, Georgia, Minnesota, Mississippi and South Carolina would greatly benefit from a depot network as these could only deliver to a biorefinery in a nearby state. To elaborate the impact of a nationwide consideration, the findings were compared with existing literature for different US regions. We also present results for biorefinery capacities that are double, triple, and quadruple in size.

09 BIOMASS FUELS↗
DOE OSTI2019

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type Σ x i = k for binary variables x i . Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

97 MATHEMATICS AND COMPUTING↗