Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “linear programming problem”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Scalable Predictive Control and Optimization for Grid Integration of Large-Scale Distributed Energy Resources

Integrating a large number of distributed energy resources (DERs) into the power grid needs a scalable power balancing method. We formulate the power balancing problem as a look-ahead optimization problem to be solved sequentially by a power distribution system aggregator based on a model predictive control (MPC) framework. Solving large-scale look-ahead control problems requires proper configuration of the control steps. In this paper, to solve large-scale control problems, we propose a variable time granularity where control time steps nearby the current control step have finer resolutions. The aggregator objective includes maximization of power production revenue and minimization of power purchasing expense, renewable power curtailment, and mileage costs for energy storage and electric vehicle (EV) charging stations while satisfying system capacity and operational constraints. The control problem is formulated as a mixed-integer linear program (MILP) and solved using the XpressMP solver. We perform simulations considering a copper plate representation of a large distribution network consisting of 2507 devices (controllable DERs), including curtailable photovoltaics (PVs), energy storage batteries, EV charging stations, and buildings with heating, ventilation, and air conditioning units (HVACs). We show the effectiveness of the proposed approach in managing DERs interactively for maximum energy trading profit and local supply-demand power balancing. Finally, we demonstrate that the proposed method outperforms other benchmark controllers regarding computation time without compromising operational performance.

DER↗
DOE OSTI2025

Alternative mixed integer linear programming optimization for joint job scheduling and data allocation in grid computing

This paper presents a novel approach to the joint optimization of job scheduling and data allocation in grid computing environments. We formulate this joint optimization problem as a mixed integer quadratically constrained program. To tackle the nonlinearity in the constraint, we alternatively fix a subset of decision variables and optimize the remaining ones via Mixed Integer Linear Programming (MILP). We solve the MILP problem at each iteration via an off-the-shelf MILP solver. Our experimental results show that our method significantly outperforms existing heuristic methods, employing either independent optimization or joint optimization strategies. We have also verified the generalization ability of our method over grid environments with various sizes and its high robustness to the algorithm setting.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Linear model decision trees as surrogates in optimization of engineering applications

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

42 ENGINEERING↗
DOE OSTI2020

Optimal charging scheduling and management for a fast-charging battery electric bus system

Herein we discuss how battery electric buses (BEBs) are rapidly being embraced by public transit agencies because of their environmental and economic benefits. To address the problems of limited driving range and time-consuming charging for BEBs, manufacturers have developed rapid on-route charging technology that utilizes typical layovers at terminals to charge buses in operation using high power. With on-route fast-charging, BEBs are as capable as their diesel counterparts in terms of range and operating time. However, on-route fast-charging makes it more challenging to schedule and manage charging events for a BEB system. First, on-route fast-charging may lead to high electricity power demand charges. Second, it may increase electricity energy charges because of charging that occurs during on-peak hours. Without careful charging scheduling and management, on-route fast-charging may significantly increase fuel costs and reduce the economic attractiveness of BEBs. The present study proposes a network modeling framework to optimize the charging scheduling and management for a fast-charging BEB system, effectively minimizing total charging costs. The charging schedule determines when to charge a BEB, while the charging management strategically controls the actual charging power. Charging costs include both electricity demand charges and energy charges. The charging scheduling and management problem is first formulated as a nonlinear nonconvex program with time-continuous variables. A discretizing method and a linear reformulation technique are then adopted to reformulate the model as a linear program, which can be easily solved using off-the-shelf solvers, even for large-scale problems. Finally, the model is demonstrated with extensive numerical studies based on two real-world bus networks. The results demonstrate that the proposed model can effectively determine the optimal charging scheduling and management for a fast-charging BEB system, which carries the potential for use in large-scale real-world bus networks.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2023

A Tutorial for Generating Correlated Random Samples in the Context of Replica Cross Section Data Used in the Propagation of Uncertainty (Second Edition)

The following sample problem write-ups are designed as a tutorial for generating correlated random samples (e.g., replica multi-group cross section data) for use in propagation of uncertainty problems. These problems were set up and solved in MATLAB, but any programming environment with basic statistical functions can be used to generate similar results. Since linear sample problems were chosen, helpful comparisons to the “sandwich” rule propagation of uncertainty are available and were used.

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 OSTI2024

HHL algorithm with mapping function and enhanced sampling for model predictive control in microgrids

Here, this paper presents a refined quantum Harrow Hassidim Lloyd (HHL) algorithm for microgrid control. The first novelty of the developed method is that a mapping shift function enables the original HHL algorithm to handle general linear equations with non-singular and indefinite matrix. Second, a method of Matrix Extension for Amplifying Sampling Probabilities of Intended Solution (ME-ASPI) is proposed to design the reformulated linear algebraic equations, allowing for improved sampling efficiency of the quantum tomography in the refined HHL algorithm. Then, we applied the method to solve the model predictive control (MPC) problem in nonlinear dynamical microgrids. Specifically, with the ME-ASPI method, the refined HHL algorithm can effectively obtain the intended partial optimal control inputs for MPC. The optimization of quadratic programming problem in each time step of MPC is transformed into a linear system problem, which is addressed by the proposed quantum solver through using only partial information, with the time complexity improved from $\mathscr{O}(\mathscr{N}^{2.37286})$ classically to $\mathscr{O}(\mathscr{N}^{2} log \mathscr{N}$ x $p$ log $p)$ in quantum. Numerical examples have validated the effectiveness of the refined HHL algorithm with the proposed mapping function and the ME-ASPI method. By leveraging quantum properties, the proposed method provides a hybrid quantum–classical framework for microgrid control. This generic method can also potentially tackle many other challenges in analyzing and controlling general complex engineered systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

A bilevel multistage stochastic self-scheduling model with indivisibilities for trading in the continuous intraday electricity market

In this paper, we study the profit maximization problem of a virtual power plant trading in the continuous intraday electricity market. Our virtual power plant model is compatible with renewable, and thermal assets, covering a range of virtual power plants currently participating in energy markets. We model the trading problem as a bilevel multistage stochastic program. The upper level of the problem accounts for the profit maximization of the virtual power plant with explicit modeling of the technical constraints of the operational status of the thermal power plant including minimum start-up and shut-down times, ramp-up and ramp-down rates, and minimum generation level. The upper level also decides which continuous and indivisible (fill-or-kill) orders are submitted to the market. The lower-level problem accounts for the clearing of the continuous intraday market, i.e., matching of buy and sell orders. Because of the presence of fill-or-kill orders, the lower-level problem is mixed-integer, which prevents its direct conversion to a single-level problem using duality. In order to solve this challenging problem, we develop a convex-hull extended formulation for the lower-level problem, apply duality theory to obtain a single-level stochastic equivalent formulation, and employ McCormick envelopes to turn the problem into a multistage stochastic mixed-integer linear problem, which we solve using the stochastic dual dynamic integer programming algorithm. We conduct numerical experiments and analyze the optimal trading behavior of a virtual power plant trading in an ideal continuous market without arbitrage.

Bilevel multistage stochastic programming problem↗
DOE OSTI2021

Efficient Automated Driving Strategies Leveraging Anticipation and Optimal Control

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

Dollar, Robert Austin↗
DOE OSTI2024

Heuristic solutions to the single depot electric vehicle scheduling problem with next day operability constraints

This study focuses on the single depot electric vehicle scheduling problem (SDEVSP) within the broader context of the vehicle scheduling problem (VSP). By developing an effective scheduling model using mixed-integer linear programming, we generate bus blocks that accommodate electric vehicles (EVs), ensuring successful completion of each block while considering recharging requirements between blocks and during off-hours. Next day operability constraints are also incorporated, allowing for seamless repetition of blocks on subsequent days. The SDEVSP is known to be computationally complex, deriving optimal solutions unattainable for large-scale problems within reasonable timeframes. To address this, we propose a two-step solution approach: first solving the single depot VSP, and then addressing the block chaining problem (BCP) using the blocks generated in the first step. The BCP focuses on optimizing block combinations to facilitate recharging between consecutive blocks, considering operational constraints. Further, a case study conducted reveals that nearly 100% electrification for Chicago, IL and Austin, TX transit buses is viable yet requires 1.6 EVs at 150-mile range per diesel vehicle.

33 ADVANCED PROPULSION SYSTEMS↗
DOE OSTI2022

Robust trajectory-constrained frequency control for microgrids considering model linearization error

Grid supportive modes integrated within inverter-based resources can improve the frequency response of renewable-rich microgrids. The synthesis of grid supportive modes to guarantee frequency trajectory constraints under a predefined disturbance set is challenging but essential. To tackle this challenge, a numerical optimal control (NOC)-based control synthesis methodology is proposed. Without loss of generality, a wind-diesel fed microgrid is studied, where we aim to design grid supportive functions in the wind turbine. In the control design, linearized models are used, and the linearization-induced errors are quantitatively analyzed by reachability and interval arithmetics and represented in the form of interval uncertainties. Then, the NOC problem can be formulated into a robust mixed-integer linear program. The control structure is strategically configured into two levels to realize online deployment. The proposed control is verified on the modified 33-node microgrid with a full-order three-phase nonlinear model in Simulink. In conclusion, the simulation results show the effectiveness of the proposed control paradigm and the necessity of considering linearization-induced uncertainty.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

A Bilevel Voltage Regulation Operation for Distribution Systems With Self-Operated Microgrids

The emerging of microgrids in distribution systems has significantly enhanced the resilience of power grids. However, the operators of a distribution system and microgrids therein can be different and have accessibility to different devices. To model the operation of such a grid, this work proposes a bilevel formulation and probes into the voltage regulation operation, considering the interaction between different systems. The proposed bilevel formulation considers the cooperation of active energy resources (AER), transformer tap-changers, and capacitor banks that are controlled by different operators. To facilitate the solution time of the target bilevel optimization, the lower-level problems with different objectives are modeled using deep neural networks (DNNs) which are then converted into a set of constraints. Hence, the bilevel problem can be reformed to a single-level problem. Lastly, the proposed solution procedures are validated using a customized joint system constructed by the IEEE 123-bus system and a real distribution system in Iowa. According to the numerical validation results, the solution time of the proposed nonlinear activation function based DNN model is 69 times faster than other methods in solving voltage regulation with a bilevel structure.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Transient Efficiency Flexibility and Reliability Optimization of Coal-Fired Power Plants: Model-Predictive Control Library Development (Report)

This document pertains to the reporting requirements of DOE contract FE-0031767. The document covers the development of a model predictive control (MPC) library for implementing MPC for a general dynamic system. The library is implemented in a standardized manner in Matlab/Simulink, where core functions on model prediction, linearization and formulation and solution of a quadratic programming (QP) optimization problem is done in the core library - independent of the specific application. The user can provide the application-specific dynamic model in continuous and discrete time, to rapidly implement and test the MPC performance in a desktop simulation. The MPC optimization objective and constraints are also easily configured via an Excel file to allow iterative refinement as needed. Finally, the MPC library enables a rapid deployment to a target environment through auto C-code generation and containerization. The MPC library works seamlessly with the model based estimation (MBE) library to obtain the overall output feedback control solution. In this program, the reduced order model (ROM) of a coal-fired power plant (CFPP) is used to implement and test the MPC solution.

01 COAL, LIGNITE, AND PEAT↗
DOE OSTI2021

Substation-Level Grid Topology Optimization Using Bus Splitting

Operations of substation circuit breakers are important for maintenance needs and topology reconfiguration in power systems. Bus splitting is one type of topology change where the two bus bars at a substation can become electrically disconnected under certain actions of circuit breakers. Because these events involve detailed substation modeling, they are typically not considered in routine power system operation and control. In this paper, an improved substation-level topology optimization framework is developed by expanding traditional line switching decisions by breaker-level bus splitting, which can further reduce grid congestion and generation costs. A tight McCormick relaxation is proposed to reformulate the bilinear terms in the resultant optimization problem to linear inequality constraints. Thus, a tractable mixed-integer linear program reformulation is attained that allows for efficient solutions in real-time operations. Numerical studies on the IEEE 14-bus and 118-bus systems demonstrate the computational performance and economic benefits of the proposed topology optimization approach.

bus split↗
DOE OSTI2024

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗
DOE OSTI2023

Justice 40 Tool (J40 Tool) v1.0

The Justice 40 tool provides a quantitative framework to support decision-making around equitable energy interventions at the community level. The tool calculates the optimal portfolio of policy interventions that explicitly mitigates energy insecurity of an eligible population, by reducing its disproportionate energy burden. The place-based analysis assumes a spatial census tract-level resolution and distinguishes different sociodemographic groups within each tract. Instead of focusing on a specific technology, the underlying J40 model captures the combined effect of a set of policy interventions, currently including weatherization, rooftop solar, community solar and community wind. For each tract, the model chooses the optimal (least cost) combination of interventions to address the disproportionate burden, considering the specific population demographics and techno-economic potentials of technologies. Mathematically, this problem is formalized as an optimization model and formulated as a linear program.

Heleno, Miguel↗
DOE OSTI2023

Mitigation-Aware Bidding Strategies in Electricity Markets

Market power exercise in the electricity markets distorts market prices and diminishes social welfare. Many markets have implemented market power mitigation processes to eliminate the impact of such behavior. The design of mitigation mechanisms has a direct influence on investors' profitability and thus mid-/long-term resource adequacy. In order to evaluate the effectiveness of the existing market power mitigation mechanisms, this paper proposes a mitigation-aware strategic bidding model and studies the bidding strategies of the market participants under current practice. The proposed bidding model has a bilevel structure with strategic participant's profit maximization problem in the upper level and the dispatch problem for market operators in the lower level. In particular, the consideration of potential offer mitigation is incorporated as upper-level constraints based on the conduct and impact tests. This bilevel problem is reduced to a single-level mixed-integer linear program using the KKT optimality conditions, duality theory, and linearization. Numerical results illustrate how a strategic player can exercise market power to achieve a higher profit even under the current market power mitigation process and we analyze the social impact that the market power exercise results.

Wu, Yiqian↗
DOE OSTI2024

Shortest path network interdiction with asymmetric uncertainty

Abstract This paper considers an extension of the shortest path network interdiction problem that incorporates robustness to account for parameter uncertainty. The shortest path interdiction problem is a game of two players with conflicting agendas and capabilities: an evader, who traverses the arcs of a network from a source node to a sink node using a path of shortest length, and an interdictor, who maximizes the length of the evader's shortest path by interdicting arcs on the network. It is usually assumed that the parameters defining the network are known exactly by both players. We consider the situation where the evader assumes the nominal parameter values while the interdictor uses robust optimization techniques to account for parameter uncertainty or sensor degradation. We formulate this problem as a nonlinear mixed‐integer semi‐infinite bilevel program and show that it can be converted into a mixed‐integer linear program with a second order cone constraint. We use random geometric networks and transportation networks to perform computational studies and demonstrate the unique decision strategies that our variant produces. Solving the shortest path interdiction problem with asymmetric uncertainty protects the interdictor from investing in a strategy that hinges on key interdictions performing as promised. It also provides an alternate strategy that mitigates the risk of these worst‐case possibilities.

Punla‐Green, She'ifa Z.↗