SEARCH · Search NASA

Results for “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.

SourceResearch connectionFrom yearThrough year

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

At least 199 records · Page 11

All sources NASA NTRS DOE OSTI

DOE OSTI2015

Triangular Alignment (TAME). A Tensor-based Approach for Higher-order Network Alignment

Network alignment is an important tool with extensive applications in comparative interactomics. Traditional approaches aim to simultaneously maximize the number of conserved edges and the underlying similarity of aligned entities. We propose a novel formulation of the network alignment problem that extends topological similarity to higher-order structures and provide a new objective function that maximizes the number of aligned substructures. This objective function corresponds to an integer programming problem, which is NP-hard. Consequently, we approximate this objective function as a surrogate function whose maximization results in a tensor eigenvalue problem. Based on this formulation, we present an algorithm called Triangular AlignMEnt (TAME), which attempts to maximize the number of aligned triangles across networks. We focus on alignment of triangles because of their enrichment in complex networks; however, our formulation and resulting algorithms can be applied to general motifs. Using a case study on the NAPABench dataset, we show that TAME is capable of producing alignments with up to 99% accuracy in terms of aligned nodes. We further evaluate our method by aligning yeast and human interactomes. Our results indicate that TAME outperforms the state-of-art alignment methods both in terms of biological and topological quality of the alignments.

42 ENGINEERING↗

DOE OSTI2016

Electric Grid Expansion Planning with High Levels of Variable Generation

Renewables are taking a large proportion of generation capacity in U.S. power grids. As their randomness has increasing influence on power system operation, it is necessary to consider their impact on system expansion planning. To this end, this project studies the generation and transmission expansion co-optimization problem of the US Eastern Interconnection (EI) power grid with a high wind power penetration rate. In this project, the generation and transmission expansion problem for the EI system is modeled as a mixed-integer programming (MIP) problem. This study analyzed a time series creation method to capture the diversity of load and wind power across balancing regions in the EI system. The obtained time series can be easily introduced into the MIP co-optimization problem and then solved robustly through available MIP solvers. Simulation results show that the proposed time series generation method and the expansion co-optimization model and can improve the expansion result significantly after considering the diversity of wind and load across EI regions. The improved expansion plan that combines generation and transmission will aid system planners and policy makers to maximize the social welfare. This study shows that modelling load and wind variations and diversities across balancing regions will produce significantly different expansion result compared with former studies. For example, if wind is modeled in more details (by increasing the number of wind output levels) so that more wind blocks are considered in expansion planning, transmission expansion will be larger and the expansion timing will be earlier. Regarding generation expansion, more wind scenarios will slightly reduce wind generation expansion in the EI system and increase the expansion of other generation such as gas. Also, adopting detailed wind scenarios will reveal that it may be uneconomic to expand transmission networks for transmitting a large amount of wind power through a long distance in the EI system. Incorporating more details of renewables in expansion planning will inevitably increase the computational burden. Therefore, high performance computing (HPC) techniques are urgently needed for power system operation and planning optimization. As a scoping study task, this project tested some preliminary parallel computation techniques such as breaking down the simulation task into several sub-tasks based on chronology splitting or sample splitting, and then assigning these sub-tasks to different cores. Testing results show significant time reduction when a simulation task is split into several sub-tasks for parallel execution.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

DOE OSTI2022

Reassessing the Market—Computation Interface to Enhance Grid Security and Efficiency

The goal of this project is to reconsider core market and reliability processes that can potentially yield to transformative advances in power grid security, reliability, and efficiency. Current electric power market designs are strongly a function of computing capabilities and limitations that were available in the mid-to-late 1990s, circa deregulation. This includes constructs such as: (1) a 2-tiered day-ahead/real-time market construct; and (2) linearized (“DC”) real power flow approximations in dispatch and pricing. At that time, state-of-the-art computational capabilities could at the limit address deterministic mixed-integer programming formulations of unit commitment (UC) and linear programming formulations of economic dispatch (ED) at limited fidelity and scale. Such constraints forced limited look-ahead time-horizons, crude approximations of AC power flow physics and operations, and artificial partitioning between day-ahead markets, hour(s)-ahead reliability processes, and real-time markets. Consequently, these limitations have resulted in limited security and reliability with increasing out-of-market payments, particularly as uncertainty associated with renewables and distributed energy resources grows.

24 POWER TRANSMISSION AND DISTRIBUTION↗

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 OSTI2022

Methods for Computing Physically Realistic Estimates of Electric Water Heater Demand Response Resource Suitable for Bulk Power System Planning Models

Demand response is commonly called on to reduce load during system peak times or to respond to contingency events. In future power systems with higher shares of wind and solar generation (which we describe together as variable generation [VG]), demand response could have more opportunities to provide energy shifting or operating reserve services. This report evaluates the ability of residential electric water heaters, both electric resistance water heaters (ERWHs) and heat pump water heaters (HPWHs), to provide such services starting from detailed whole-building energy models that realistically represent New England single family home stock. We use a parsimonious surrogate model to represent operational flexibility in a form suitable for linear and mixed integer programming. This enables relatively fast determination of aggregate contingency reserve resource, price-taking energy shifting outcomes, and in some cases the determination of aggregate models at the megawatt (MW) scale that can be directly included in large-scale grid models. After selecting modeling methods and parameters through various computational experiments, we find interquartile ranges of contingency reserve resource in ISO-NE for about 603,400 ERWHs of 45 MW - 69 MW for Claim10 (50 minute responses provided with 10 minutes of advanced notification) and 65 MW - 102 MW for Claim30 (30 minute responses provided with 30 minutes of advanced notification), and for about 619,000 HPWHs of 48 MW - 88 MW for Claim10 and 52 MW - 90 MW for Claim30. The overall reserve resource is up to 32% of total load for ERWHs providing Claim10 service, 47% for ERWHs providing Claim30 service, 93% for HPWHs providing Claim10 service, and 97% for HPWHs providing Claim30 service. More work is required to determine if HPWHs are inherently more suitable than ERWHs for providing contingency reserve or if these results reflect idiosyncrasies of the single family home stock model used in this study. The value of this contingency resource in a Near-term VG model of ISO-NE is $\$ 0.40$ to $\$1.20$ per water heater-year, and significantly larger, $\$ 3.80$ to $\$ 5.30$ per water heater-year in a Mid-term VG model of ISONE. Aggregating surrogate models to the MW-scale for energy shifting service is more challenging than for contingency service and we only present such results for ERWHs, because we were unable to determine satisfactory ways to deal with HPWHs' time-varying and path dependent operational characteristics. Individual surrogate models suitable for evaluating the energy shifting resource from both ERWHs and HPWHs are created, however, and dispatched against day-ahead prices from the Near-Term VG and Mid-Term VG models of ISO-NE. The individual surrogate models are able to access and potentially shift all 640 GWh of HPWH load and 1,547 GWh of ERWH load we modeled in two different single family home stock models. In contrast, the most effective model of aggregate ERWH shifting resource we created only captured 34.7% of the total ERWH load. Energy shifting affected by price-taking dispatch against modeled day-ahead energy prices produces per water heater year profits of $\$19.44$ - $\$22.93$ for individual HPWHs, $\$39.11$ - $\$40.54$ for individual ERWHs, and up to $\$4.00$ - $\$4.24$ for aggregated ERWHs, with the variations mainly due to grid conditions (more or less VG). When the supply-side response to these changes is accounted for, the per water heater year production cost savings for ISO-NE are $\$7.50$ to $\$17.70$ for the most effective set of endogenously dispatched aggregate ERWHs, $\$15.60$ to $\$15.70$ for individual ERWHs dispatched against the DA prices, and $\$10.70$ to $\$11.20$ for individual HPWHs dispatched against DA prices. Those ranges primarily represent the difference between Near-Term VG and Mid-Term VG grid conditions.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2010

Analyzing Impact of Intermodal Facilities on Design and Management of Biofuel Supply Chain

The impact of an intermodal facility on location and transportation decisions for biofuel production plants is analyzed. Location decisions affect the management of the inbound and outbound logistics of a plant. This supply chain design and management problem is modeled as a mixed integer program. Input data for this model are location of intermodal facilities and available transportation modes, cost and cargo capacity for each transportation mode, geographical distribution of biomass feedstock and production yields, and biomass processing and inventory costs. Outputs from this model are the number, location, and capacity of biofuel production plants. For each plant, the transportation mode used, timing of shipments, shipment size, inventory size, and production schedule that minimize the delivery cost of biofuel are determined. The model proposed in this research can be used as a decision-making tool for investors in the biofuels industry since it estimates the real cost of the business. The state of Mississippi is considered as the testing grounds for the model.

09 BIOMASS FUELS↗

DOE OSTI2023

Minimal Energy Routing of a Leader and a Wingmate with Periodic Connectivity

We consider a route planning problem in which two unmanned vehicles are required to complete a set of tasks present at distinct locations, referred to as targets, with minimum energy consumption. The mission environment is hazardous, and to ensure a safe operation, the UVs are required to communicate with each other at every target they visit. The problem objective is to determine the allocation of the tasks to the UVs and plan tours for the UVs to visit the targets such that the weighted sum of the distances traveled by the UVs and the distances traveled by the communicating signals between them is minimized. We formulate this problem as an Integer program and show that naively solving the problem using commercially available off-the-shelf solvers is insufficient in determining scalable solutions efficiently. To address this computational challenge, we develop an approximation and a heuristic algorithm, and employ them to compute high-quality solutions to a special case of the problem where equal weights are assigned to the distances traveled by the vehicles and the communicating signals. For this special case, we show that the approximation algorithm has a fixed approximation ratio of 3.75. We also develop lower bounds to the optimal cost of the problem to evaluate the performance of these algorithms on large-scale instances. We demonstrate the performance of these algorithms on 500 randomly generated instances with the number of targets ranging from 6 to 100, and show that the algorithms provide high-quality solutions to the problem swiftly; the average computation time of the algorithmic solutions is within a fraction of a second for instances with at most 100 targets. Finally, we show that the approximation ratio has a variable ratio for the weighted case of the problem. Specifically, if ρ denotes the ratio of the weights assigned to the distances representing the communication and travel costs, the algorithm has an a posteriori ratio of $3 + \frac{3ρ}{4}$ when ρ ≥ 1, and $\frac{3}{ρ}$ + $\frac{3}{4}$ when ρ ≤ 1.

42 ENGINEERING↗

DOE OSTI2010

The inhibiting bisection problem.

Given a graph where each vertex is assigned a generation or consumption volume, we try to bisect the graph so that each part has a significant generation/consumption mismatch, and the cutsize of the bisection is small. Our motivation comes from the vulnerability analysis of distribution systems such as the electric power system. We show that the constrained version of the problem, where we place either the cutsize or the mismatch significance as a constraint and optimize the other, is NP-complete, and provide an integer programming formulation. We also propose an alternative relaxed formulation, which can trade-off between the two objectives and show that the alternative formulation of the problem can be solved in polynomial time by a maximum flow solver. Our experiments with benchmark electric power systems validate the effectiveness of our methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2010

Strategic planning for power system restorations

This paper considers the power system restoration planning problem (PSRPP) for disaster recovery, a fundamental problem faced by all populated areas. PSRPPs are complex stochastic optimization problems that combine resource allocation, warehouse location, and vehicle routing considerations. Furthermore, electrical power systems are complex systems whose behavior can only be determined by physics simulations. Moreover, these problems must be solved under tight runtime constraints to be practical in real-world disaster situations. This work is three fold: (1) it formalizes the specification of PSRPPs; (2) introduces a simple optimization-simulation hybridization necessary for solving PSRPPs; and (3) presents a complete restoration algorithm that utilizes the strengths of mixed integer programming, constraint programming, and large neighborhood search. This paper studied a novel problem in the field of humanitarian logistics, the Power System Restoration Problem (PSRPP). The PSRPP models the strategic planning process for post disaster power system recovery. The paper proposed a multi-stage stochastic hybrid optimization algorithm that yields high quality solutions to real-world benchmarks provided by Los Alamos National Laboratory (LANL). The algorithm uses a variety of technologies, including MIP, constraint programming, and large neighborhood search, to exploit the structure of each individual optimization subproblem. The experimental results on hurricane disaster benchmarks indicate that the algorithm is practical from a computational standpoint and produce significant improvements over existing relief delivery procedures.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2010

Sensor placement for municipal water networks.

We consider the problem of placing a limited number of sensors in a municipal water distribution network to minimize the impact over a given suite of contamination incidents. In its simplest form, the sensor placement problem is a p-median problem that has structure extremely amenable to exact and heuristic solution methods. We describe the solution of real-world instances using integer programming or local search or a Lagrangian method. The Lagrangian method is necessary for solution of large problems on small PCs. We summarize a number of other heuristic methods for effectively addressing issues such as sensor failures, tuning sensors based on local water quality variability, and problem size/approximation quality tradeoffs. These algorithms are incorporated into the TEVA-SPOT toolkit, a software suite that the US Environmental Protection Agency has used and is using to design contamination warning systems for US municipal water systems.

99 GENERAL AND MISCELLANEOUS↗

DOE OSTI2014

A Multi-Objective, Hub-and-Spoke Supply Chain Design Model For Densified Biomass

In this paper we propose a model to design the supply chain for densified biomass. Rail is typically used for long-haul, high-volume shipment of densified biomass. This is the reason why a hub-and-spoke network structure is used to model this supply chain. The model is formulated as a multi-objective, mixed-integer programing problem under economic, environmental, and social criteria. The goal is to identify the feasibility of meeting the Renewable Fuel Standard (RFS) by using biomass for production of cellulosic ethanol. The focus in not just on the costs associated with meeting these standards, but also exploring the social and environmental benefits that biomass production and processing offers by creating new jobs and reducing greenhouse gas (GHG) emissions. We develop an augmented ?-constraint method to find the exact Pareto solution to this optimization problem. We develop a case study using data from the Mid-West. The model identifies the number, capacity and location of biorefineries needed to make use of the biomass available in the region. The model estimates the delivery cost of cellulosic ethanol under different scenario, the number new jobs created and the GHG emission reductions in the supply chain.

09 BIOMASS FUELS↗

DOE OSTI2014

A Multi-Objective, Hub-and-Spoke Supply Chain Design Model for Densified Biomass

In this paper we propose a model to design the supply chain for densified biomass. Rail is typically used for longhaul, high-volume shipment of densified biomass. This is the reason why a hub-and-spoke network structure is used to model this supply chain. The model is formulated as a multi-objective, mixed-integer programing problem under economic, environmental, and social criteria. The goal is to identify the feasibility of meeting the Renewable Fuel Standard (RFS) by using biomass for production of cellulosic ethanol. The focus is not just on the costs associated with meeting these standards, but also exploring the social and environmental benefits that biomass production and processing offers by creating new jobs and reducing greenhouse gas (GHG) emissions. We develop an augmented ?-constraint method to find the exact Pareto solution to this optimization problem. We develop a case study using data from the Mid-West. The model identifies the number, capacity and location of biorefineries needed to make use of the biomass available in the region. The model estimates the delivery cost of cellulosic ethanol under different scenario, the number new jobs created and the GHG emission reductions in the supply chain.

09 BIOMASS FUELS↗

DOE OSTI2017

Managing time-substitutable electricity usage using dynamic controls

A predictive-control approach allows an electricity provider to monitor and proactively manage peak and off-peak residential intra-day electricity usage in an emerging smart energy grid using time-dependent dynamic pricing incentives. The daily load is modeled as time-shifted, but cost-differentiated and substitutable, copies of the continuously-consumed electricity resource, and a consumer-choice prediction model is constructed to forecast the corresponding intra-day shares of total daily load according to this model. This is embedded within an optimization framework for managing the daily electricity usage. A series of transformations are employed, including the reformulation-linearization technique (RLT) to obtain a Mixed-Integer Programming (MIP) model representation of the resulting nonlinear optimization problem. In addition, various regulatory and pricing constraints are incorporated in conjunction with the specified profit and capacity utilization objectives.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2017

Managing time-substitutable electricity usage using dynamic controls

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2020

Probabilistic Forecasting of Generators Startups and Shutdowns in the MISO System Based on Random Forest

Solving security constrained unit commitment (SCUC) problems to plan an economical generation schedule for day-head electricity market has been an important research topic in recent years. Mixed integer programming method (MIP), the-state-of-art approach for solving SCUC problem, is known computationally hard when the number of binary status variables is large. In this paper, a machine learning-based algorithm - random forest (RF), was applied to forecast the startups (SU) and shutdowns (SD) hours of generators, based on historical hourly system condition observations in the Midcontinent Independent System Operator (MISO) system. The main purpose is to reduce the number of binary status variables, by fixing the SU/SD hours to a narrow range of high confidence. This would significantly reduce the size of the decision space, and therefore speed up SCUC solutions with reduced uncertainty.

Lin, Xinming↗

DOE OSTI2020

Managing time-substitutable electricity usage using dynamic controls

Ghosh, Soumyadip↗

DOE OSTI2020

Formulations and Valid Inequalities for Optimal Black Start Allocation in Power Systems

The restoration of a power system after a blackout starts around units with enhanced technical capabilities, referred to as black start units (BSUs). We examine the planning problem of optimally allocating these units on the grid subject to a budget constraint. We present a mixed integer programming model based on current literature in power systems. Binary variables are associated with the allocation of BSUs and with the energization state of buses, branches, and generators of the power system over a time horizon. We extract a substructure of the feasible region which imposes the requirement that each island that appears during the restoration process must have at least one operational generator. We discuss three equivalent reformulations for this requirement. We introduce a family of exponentially many, polynomially separable, valid inequalities to strengthen the formulation. Under simplifying assumptions, we show that the convex hull of the feasible region is a full-dimensional polyhedron, and prove that some of the constraints we introduced are facet-defining. We perform experiments to examine the difference in strength between the formulations as well as the computational times to solve the problem to near optimality for synthetic instances of the IEEE-39, IEEE-118, Illinois-200, WECC-225, IEEE-300, South Carolina-500, and Texas-2000 power systems. We illustrate a use case of the model. We conclude by suggesting extensions of the current work for future research.

Black Start Allocation↗

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↗