Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “mixed integer program (MIP)”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2014

Water Security Toolkit User Manual Version 1.2.

The Water Security Toolkit (WST) is a suite of open source software tools that can be used by water utilities to create response strategies to reduce the impact of contamination in a water distribution network . WST includes hydraulic and water quality modeling software , optimizati on methodologies , and visualization tools to identify: (1) sensor locations to detect contamination, (2) locations in the network in which the contamination was introduced, (3) hydrants to remove contaminated water from the distribution system, (4) locations in the network to inject decontamination agents to inactivate, remove, or destroy contaminants, (5) locations in the network to take grab sample s to help identify the source of contamination and (6) valves to close in order to isolate contaminate d areas of the network. This user manual describes the different components of WST , along w ith examples and case studies. License Notice The Water Security Toolkit (WST) v.1.2 Copyright c 2012 Sandia Corporation. Under the terms of Contract DE-AC04-94AL85000, there is a non-exclusive license for use of this work by or on behalf of the U.S. government. This software is distributed under the Revised BSD License (see below). In addition, WST leverages a variety of third-party software packages, which have separate licensing policies: Acro Revised BSD License argparse Python Software Foundation License Boost Boost Software License Coopr Revised BSD License Coverage BSD License Distribute Python Software Foundation License / Zope Public License EPANET Public Domain EPANET-ERD Revised BSD License EPANET-MSX GNU Lesser General Public License (LGPL) v.3 gcovr Revised BSD License GRASP AT&T Commercial License for noncommercial use; includes randomsample and sideconstraints executable files LZMA SDK Public Domain nose GNU Lesser General Public License (LGPL) v.2.1 ordereddict MIT License pip MIT License PLY BSD License PyEPANET Revised BSD License Pyro MIT License PyUtilib Revised BSD License PyYAML MIT License runpy2 Python Software Foundation License setuptools Python Software Foundation License / Zope Public License six MIT License TinyXML zlib License unittest2 BSD License Utilib Revised BSD License virtualenv MIT License Vol Common Public License vpykit Revised BSD License Additionally, some precompiled WST binary distributions might bundle other third-party executables files: Coliny Revised BSD License (part of Acro project) Dakota GNU Lesser General Public License (LGPL) v.2.1 PICO Revised BSD License (part of Acro project) i Revised BSD License Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of Sandia National Laboratories nor Sandia Corporation nor the names of its con- tributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IM- PLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUD- ING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ii Acknowledgements This work was supported by the U.S. Environmental Protection Agency through its Office of Research and Development (Interagency Agreement # DW8992192801). The material in this document has been subject to technical and policy review by the U.S. EPA, and approved for publication. The views expressed by individual authors, however, are their own, and do not necessarily reflect those of the U.S. Environmental Protection Agency. Mention of trade names, products, or services does not convey official U.S. EPA approval, endorsement, or recommendation. The Water Security Toolkit is an extension of the Threat Ensemble Vulnerability Assessment-Sensor Place- ment Optimization Tool (TEVA-SPOT), which was also developed with funding from the U.S. Environ- mental Protection Agency through its Office of Research and Development (Interagency Agreement # DW8992192801). The authors acknowledge the following individuals for their contributions to the devel- opment of TEVA-SPOT: Jonathan Berry (Sandia National Laboratories), Erik Boman (Sandia National Laboratories), Lee Ann Riesen (Sandia National Laboratories), James Uber (University of Cincinnati), and Jean-Paul Watson (Sandia National Laboratories). iii Acronyms ATUS American Time-Use Survey BLAS Basic linear algebra sub-routines CFU Colony-forming unit CVAR Conditional value at risk CWS Contamination warning system EA Evolutionary algorithm EDS Event detection system EPA U.S. Environmental Protection Agency EC Extent of Contamination ERD EPANET results database file GLPK GNU Linear Programming Kit GRASP Greedy randomized adaptive sampling process HEX Hexadecimal HTML HyperText markup language INP EPANET input file LP Linear program MC Mass consumed MILP Mixed integer linear program MIP Mixed integer program MSX Multi-species extension for EPANET NFD Number of failed detections NS Number of sensors NZD Non-zero demand PD Population dosed PE Population exposed PK Population killed TAI Threat assessment input file TCE Tailed-conditioned expectation TD Time to detection TEC Timed extent of contamination TEVA Threat ensemble vulnerability assessment TSB Tryptic soy broth TSG Threat scenario generation file TSI Threat simulation input file VAR Value at risk VC Volume consumed WST Water Security Toolkit YML YAML configuration file format for WST iv Symbols Notation Definition Example { , } set brackets { 1,2,3 } means a set containing the values 1,2, and 3. [?] is an element of s [?] S means that s is an element of the set S . [?] for all s = 1 [?] s [?] S means that the statement s = 1 is true for all s in set S . P summation P n i =1 s i means s 1 + s 2 + * * * + s n . \ set minus S \ T means the set that contains all those elements of S that are not in set T . %7C given %7C is used to define conditional probability. P ( s %7C t ) means the prob- ability of s occurring given that t occurs. %7C ... %7C cardinality Cardinality of a set is the number of elements of the set. If set S = { 2,4,6 } , then %7C S %7C = 3. v

Klise, Katherine A.↗
DOE OSTI2016

Solving Open MIP Instances with ParaSCIP on Supercomputers Using up to 80,000 Cores

This paper describes how we solved 12 previously unsolved mixed-integer programming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Robust Reconfiguration of A Distribution System

In this paper, a robust reconfiguration approach based on Mixed Integer Programming (MIP) is proposed to minimize loss in distribution systems. A Depth-First Search (DFS) algorithm to enumerate possible loops provides radiality constraint. This provides a general solution to the radiality constraint for distribution system reconfiguration/expansion problems. Still, imprecision and ambiguity in net loads, i.e. load minus renewable generation, due to lack of sufficient measurements and high utilization of demand response programs and renewable resources, creates challenges for effective reconfiguration. Deterministic optimization of reconfiguration may no lead to optimal/feasible results. Two methods to address these uncertainties are introduced in this paper: one, based on a stochastic MIP (SMIP) formulation and two, based on a fuzzy MIP (FMIP) formulation. Case studies demonstrate the robustness and efficiency of the proposed reconfiguration methods.

Depth-First Search (DFS)↗
DOE OSTI2015

Electricity market design for generator revenue sufficiency with increased variable generation

Here, we present a computationally efficient mixed-integer program (MIP) that determines optimal generator expansion decisions, and hourly unit commitment and dispatch in a power system. The impact of increasing wind power capacity on the optimal generation mix and generator profitability is analyzed for a test case that approximates the electricity market in Texas (ERCOT). We analyze three market policies that may support resource adequacy: Operating Reserve Demand Curves (ORDC), Fixed Reserve Scarcity Prices (FRSP) and fixed capacity payments (CP). Optimal expansion plans are comparable between the ORDC and FRSP implementations, while capacity payments may result in additional new capacity. The FRSP policy leads to frequent reserves scarcity events and corresponding price spikes, while the ORDC implementation results in more continuous energy prices. Average energy prices decrease with increasing wind penetration under all policies, as do revenues for baseload and wind generators. Intermediate and peak load plants benefit from higher reserve prices and are less exposed to reduced energy prices. All else equal, an ORDC approach may be preferred to FRSP as it results in similar expansion and revenues with less extreme energy prices. A fixed CP leads to additional new flexible NGCT units, but lower profits for other technologies.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2015

Capacity Adequacy and Revenue Sufficiency in Electricity Markets With Wind Power

We present a computationally efficient mixed-integer program (MIP) that determines optimal generator expansion decisions, as well as periodic unit commitment and dispatch. The model is applied to analyze the impact of increasing wind power capacity on the optimal generation mix and the profitability of thermal generators. In a case study, we find that increasing wind penetration reduces energy prices while the prices for operating reserves increase. Moreover, scarcity pricing for operating reserves through reserve shortfall penalties significantly impacts the prices and profitability of thermal generators. Without scarcity pricing, no thermal units are profitable, however scarcity pricing can ensure profitability for peaking units at high wind penetration levels. Capacity payments can also ensure profitability, but the payments required for baseload units to break even increase with the amount of wind power. The results indicate that baseload units are most likely to experience revenue sufficiency problems when wind penetration increases and new baseload units are only developed when natural gas prices are high and wind penetration is low.

capacity adequacy↗
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

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

Mixed Integer Programming and Heuristic Scheduling for Space Communication

Optimal planning and scheduling for a communication network was created where the nodes within the network are communicating at the highest possible rates while meeting the mission requirements and operational constraints. The planning and scheduling problem was formulated in the framework of Mixed Integer Programming (MIP) to introduce a special penalty function to convert the MIP problem into a continuous optimization problem, and to solve the constrained optimization problem using heuristic optimization. The communication network consists of space and ground assets with the link dynamics between any two assets varying with respect to time, distance, and telecom configurations. One asset could be communicating with another at very high data rates at one time, and at other times, communication is impossible, as the asset could be inaccessible from the network due to planetary occultation. Based on the network's geometric dynamics and link capabilities, the start time, end time, and link configuration of each view period are selected to maximize the communication efficiency within the network. Mathematical formulations for the constrained mixed integer optimization problem were derived, and efficient analytical and numerical techniques were developed to find the optimal solution. By setting up the problem using MIP, the search space for the optimization problem is reduced significantly, thereby speeding up the solution process. The ratio of the dimension of the traditional method over the proposed formulation is approximately an order N (single) to 2*N (arraying), where N is the number of receiving antennas of a node. By introducing a special penalty function, the MIP problem with non-differentiable cost function and nonlinear constraints can be converted into a continuous variable problem, whose solution is possible.

Lee, Charles H.↗
DOE OSTI2025

Tightest Mixed-Integer Programming Formulations for Quadratic SCUC Optimization

In this project, we developed new, tighter Mixed-Integer Programming (MIP) formulations for the combined Alternating Current (AC) Security-Constrained Unit Commitment (SCUC) and Security-Constrained Optimal Power Flow (SCOPF). The work addresses a critical challenge in power system operations: efficiently determining which generation units to commit and how to optimally dispatch them while maintaining network reliability constraints for both normal and contingency scenarios. Our efforts: 1. Advance the Understanding of SCUC/SCOPF Modeling: By introducing tighter MIP formulations and leveraging cutting-edge optimization tools (Julia/JuMP, PowerModels.jl), this project has pushed forward the state of the art in efficient power systems scheduling. 2. Enhance Technical and Economic Feasibility: The methods developed provide more accurate and potentially faster solutions to large-scale, realistic scheduling and dispatch problems in electric power systems, which can translate into improved reliability and potentially lower costs for grid operations. 3. Benefit to the Public: Greater efficiency in power system operations leads to cost savings for utilities and end-users. Improved reliability and integration of advanced modeling approaches can facilitate the adoption of clean energy resources and better accommodate uncertainties in renewable generation. Because this technology could impact bulk power markets and reliability, these innovations have far-reaching public benefits in terms of cost savings, reliability, and sustainability.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2015

A Parallel Computing Framework for Finding the Supported Solutions to a Biobjective Network Optimization Problem

Abstract Solving multi‐objective combinatorial optimization problems can quickly become computationally challenging when applied to large networks generated from big data. Present‐day first‐rate Mixed Integer Programming (MIP) solvers have parallelism built‐in to take advantage of multicore architectures; but specialized network optimization algorithms that can often solve graph problems more efficiently than a general MIP solver are typically programmed serially. Thus, these network algorithm implementations do not take full advantage of modern multicore computer capabilities. Many parallel computing languages include a fork/join framework into their concurrency packages that allow for simple conversion of recursive serial algorithms to operate in parallel without having to use complicated low‐level message‐passing interfaces. Fork/join is particularly well suited to divide and conquer algorithms such as Non‐Inferior Set Estimation (NISE) method for computing the supported Pareto front of a multi‐objective optimization problem. This work develops a simple general parallel NISE (pNISE) implementation using the Java 7 concurrency tools, and then offers results from a specific implementation of solving a bi‐objective shortest path problem. The results indicate that this method is capable of sizeable speed‐ups on both small‐scale personal computers as well as large‐scale shared memory supercomputers. Finally, other network problems suitable to this method are discussed, including multi‐objective variants of the minimum spanning tree problem, transportation problem, assignment problem, maximum flow problem, and the minimum‐cost flow problem. Copyright © 2015 John Wiley & Sons, Ltd.

Medrano, Fernando Antonio↗
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 OSTI2018

Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty

We introduce the problem of scheduling observations on a constellation of remote sensors, to maximize the aggregate quality of the collections obtained. While automated tools exist to schedule remote sensors, they are often based on heuristic scheduling techniques, which typically fail to provide bounds on the quality of the resultant schedules. To address this issue, we first introduce a novel deterministic mixed-integer programming (MIP) model for scheduling a constellation of one to n satellites, which relies on extensive pre-computations associated with orbital propagators and sensor collection simulators to mitigate model size and complexity. Our MIP model captures realistic and complex constellation-target geometries, with solutions providing optimality guarantees. We then extend our base deterministic MIP model to obtain two-stage and three-stage stochastic MIP models that proactively schedule to maximize expected collection quality across a set of scenarios representing cloud cover uncertainty. Our experimental conclusions on instances of one and two satellites demonstrate that our stochastic MIP models yield significantly improved collection quality relative to our base deterministic MIP model. We further demonstrate that commercial off-the-shelf MIP solvers can produce provably optimal or near-optimal schedules from these models in time frames suitable for sensor operations.

47 OTHER INSTRUMENTATION↗
DOE OSTI2016

Co-optimizing Generation and Transmission Expansion with Wind Power in Large-Scale Power Grids Implementation in the US Eastern Interconnection

This paper studies the generation and transmission expansion co-optimization problem with a high wind power penetration rate in the US Eastern Interconnection (EI) power grid. In this paper, the generation and transmission expansion problem for the EI system is modeled as a mixed-integer programming (MIP) problem. Our paper also analyzed a time series generation method to capture the variation and correlation of both load and wind power across regions. The obtained series can be easily introduced into the expansion planning problem and then solved through existing MIP solvers. Simulation results show that the proposed planning model and series generation method can improve the expansion result significantly through modeling more detailed information of wind and load variation among regions in the US EI system. Moreover, the improved expansion plan that combines generation and transmission will aid system planners and policy makers to maximize the social welfare in large-scale power grids.

17 WIND ENERGY↗
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 OSTI2015

Real-Time Corrective Switching in Response to Simultaneous Contingencies

The standard optimal power flow (OPF) problem is an economic dispatch (ED) problem combined with transmission constraints, which are based on a static topology. Prior research has demonstrated that cooptimization of generation dispatch and transmission topology results in cost savings. However, the computational complexity associated with topology control (TC) has been a major deterrent to its implementation. The proposed work investigates the application of a heuristic, a greedy algorithm, to improve the computational time for the TC problem while still maintaining the ability to find quality solutions. An expression is derived, which indicates the impact on the objective for a marginal change in the state of a transmission line. This expression is used to generate a priority list with potential candidate lines for switching, which may provide huge improvements to the system. The advantage of this method is that it is a fast heuristic as compared to using mixed integer programming (MIP) to find a solution. The heuristic is tested on real-time applications such as N-1 events, N - m events (m simultaneous contingencies), and cascading events. The proposed algorithm specifically targets cases that lead to load shedding in the system and provides a quick and efficient method to restore the loads by improving the deliverability of reserves via TC. Simulation results on the IEEE 73 bus test system and the IEEE 118 bus test system suggest a significant improvement in the amount of load served to the system with TC as opposed to without TC with minimal time and computation.

Electric power systems↗
DOE OSTI2023

Co-design optimization of combined heat and power-based microgrids

With the emergent need for clean and reliable energy resources, hybrid energy systems, such as the microgrid, are widely adopted in the United States. A microgrid can consist of various distributed energy resources, for instance, combined heat and power (CHP) systems. Here, the CHP module is a distributed cogeneration technology that produces electricity and recaptures heat generated as a by-product. It is an energy-efficient technology converting heat that would otherwise be wasted to valuable thermal energy. For an optimal system configuration, this study develops a novel co-design optimization framework for CHP-based cogeneration microgrids. The framework provides the stakeholder with a method to optimize investments and attain resilient operations. The proposed co-design framework has a mixed integer programming (MIP) model that outputs decisions for both plant designs and operating controls. The microgrid considered in this study contains six components: the CHP, boiler, heat recovery unit, thermal storage system, power storage system, and photovoltaic plant. After solving the MIP model, the optimal design parameters of each component can be found to minimize the total installation cost of all components in the microgrid. Furthermore, the online costs from energy production, operation, maintenance, machine startup, and disruption-induced unsatisfied loads are minimized by solving the optimal control decisions for operations. Case studies based on designing a CHP-based microgrid with empirical data are conducted. Moreover, we consider both nominal and disruptive operational scenarios to validate the performance of the proposed co-design framework in terms of a cost-effective, resilient system.

42 ENGINEERING↗