Search NASA⌕ Search

SEARCH · Search NASA

Results for “Bilevel 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 19 records
All sourcesNASA NTRSDOE OSTI
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 OSTI2021

A stochastic biomass blending problem in decentralized supply chains

Blending biomass materials of different physical or chemical properties provides an opportunity to adjust the quality of the feedstock to meet the specifications of the conversion platform. We propose a model which identifies the right mix of biomass to optimize the performance of the thermochemical conversion process at the mini-mum cost. This is a chance-constraint programming (CCP) model which takes into account the stochastic nature of biomass quality. The proposed CCP model ensures that process requirements, which are impacted by physical and chemical properties of biomass, are met most of the time. We consider two problem settings, a centralized and a decentralized supply chain. We propose a mixed-integer linear program to model the blending problem in the centralized setting and a bilevel program to model the blending problem in the decentralized setting. We use the sample average approximation method to approximate the chance constraints, and propose solution algorithms to solve this approximation. We develop a case study for South Carolina using data provided by the Billion Ton Study. Based on our results, the blends identified consist mainly of pine and softwood residues. The blends identified and the suppliers selected by both models are different. The cost of the centralized supply chain is 2%–6% lower. The implications of these results are twofold. First, these results could lead to improved collaborations in the supply chain. Second, these results provide an estimate of the approximation error from assuming centralized decision making in the supply chain.

09 BIOMASS FUELS↗
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.↗
DOE OSTI2020

Solving the duck curve in a smart grid environment using a non-cooperative game theory and dynamic pricing profiles

With the intermittency that comes with electricity generation from renewables, utilizing dynamic pricing will encourage the demand-side to respond in a smart way that would minimize the electricity costs and flatten the net electricity demand curve. Determining the optimal dynamic pricing profile that would leverage distributed storage to flatten the curve is a novel idea that needs to be studied. Moreover, the economic feasibility of utilizing distributed electrical energy storage is still not given in the literature. Therefore, in this paper, a novel way of solving a citywide dynamic model using a bilevel programming algorithm is introduced. The problem is developed as a novel non-cooperative Stackelberg game that utilizes air-conditioning systems and electrical storage through the end-users to determine the optimal dynamic pricing profile. The results show that the combined effect of utilizing demand-side air-conditioning systems and distributed storage together can flatten the curve while employing the optimal dynamic pricing profile. An economic study is performed to determine the economic feasibility of 20 different cases with different battery designs and the level of solar penetration. Three metrics were used to evaluate the economic performance of each case: the levelized cost of storage, the levelized cost of energy, and the simple payback period. Most cases had levelized cost of storage values lower than 0.457 $/kWh, which is the lower bound available in the literature. Seven out of 16 cases have a simple payback period shorter than the lifetime of the system (25 years). The case with a 100 MW PV power plant and a battery storage of size 597 MWh, was found to be the most promising case with a simple payback period of 12.71 years for the photovoltaic plant and 19.86 years for the demand-side investments.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2019

PAO

PAO supports the formulation and analysis of mathematical models for complex optimization applications. This capability is commonly associated with algebraic modeling languages (AMLs), which support the description and analysis of mathematical models with a high-level language. PAO is derived from the Pyomo subpackage pyomo.bilevel, which has been deprecated. PAO supports the formulation and solution of optimization models that explicitly represent adversarial behavior. This includes variances of bilevel programming, including methods that represent challenging problems with discrete decisions and uncertain model parameters.

Hart, William↗
DOE OSTI2020

Techno-economic analysis of the impact of dynamic electricity prices on solar penetration in a smart grid environment with distributed energy storage

This study investigates the technical and economic feasibility of using high levels of solar energy penetration up to 400 MW into a smart grid system of 60,000 smart houses. A novel non-cooperative Stackelberg game is introduced that incorporates the profitability of the supply-side and helps in solving problems related to overgeneration and photovoltaic curtailment. The non-cooperative game is intended to find the optimal dynamic prices that would leverage distributed storage through the demand-side to stabilize the power grid operation. Ten cases are studied with five photovoltaic plant sizes and two battery designs. Here, a novel quantitative analysis of high levels of solar penetration as a percentage of the total electricity demand is introduced to evaluate the technical feasibility of the studied cases. To evaluate the economic viability of the proposed smart grid system, four metrics were used: the levelized cost of energy, the levelized cost of storage, the payback period, and the net present value. Two out of ten studied cases were concluded to be the most promising cases, one with a solar photovoltaic plant size of 200 MW and the other with 300 MW. The case with 300 MW solar plant is preferred as it paves the way for more solar energy deployment with a solar penetration percentage up to 67.78%. This case had a payback period of 10.72 years and a net present value of $\$51.44$ M for the solar plant and a payback period of 12.06 years and a net present value of $\$40.75$ M for the demand-side.

14 SOLAR ENERGY↗
DOE OSTI2019

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

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

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

Stochastic Strategic Participation of Active Distribution Networks With High-Penetration DERs in Wholesale Electricity Markets

With the increasing penetration of distributed energy resources (DERs), traditional distribution networks as load-serving entities in wholesale electricity markets, now evolve towards active distribution networks (ADNs) which can proactively participate in wholesale markets by optimally controlling the DERs in their networks. A stochastic bilevel optimization model is proposed in this paper for the strategic participation of ADNs and DERs to provide energy and grid services in wholesale electricity markets. The bilevel optimization model can capture the interactions between the ADN and the wholesale energy and ancillary service markets, considering the uncertainties of DERs in the ADN. In the upper-level model, the ADN makes optimal decisions on energy and reserve bidding considering the availability, uncertainties, and flexibility of DERs. The joint energy and reserve market-clearing of the independent system operator (ISO) is modeled as the lower-level problem. Using strong duality theory and Karush-Kuhn Tucker (KKT) conditions, the proposed bilevel optimization problem is reformulated as mathematical programming with equilibrium constraints (MPEC) problem and further converted into a computationally-solvable mixed-integer second-order-cone programming (MISOCP) model. The simulation results demonstrate the effectiveness of the model and the interactions between an ADN and wholesale electricity markets.

active distribution network↗
DOE OSTI2021

Modeling the Strategic Behavior of an Active Distribution Network in the ISO Markets

With increasing integration of distributed energy resources (DERs), active distribution networks (ADNs) can actively participate in the electricity markets by dispatching their DERs, which can change the existing electricity market paradigm. It is essential to investigate the strategic behaviors of ADNs and their DER dispatch when they participate in the wholesale market as price-makers. This paper proposes a bi-level optimization model to study the strategic behavior of an ADN in both energy and reserve markets. The optimal scheduling of DERs in the ADN is modeled as the upper level problem and the joint energy and reserve market-clearing of the ISO is modeled as the lower-level problem. The two-level optimization models exchange bidding information and energy/reserve prices with each other. The proposed bi-Ievel optimization problem is converted to a mathematical programming with equilibrium constraints (MPEC) by using Karush-Kuhn Tucker (KKT) conditions and strong duality theory. Further, the MPEC problem is reformulated as a computationally-solvable mixed integer second order cone programming (MISOCP) model. The simulation results on an illustrative case demonstrate the impact of the strategic bidding of the ADN on the day-ahead energy and reserve market prices.

active distribution network↗
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 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 OSTI2024

Distributionally Robust Bilevel Optimization Model for Distribution Network With Demand Response Under Uncertain Renewables Using Wasserstein Metrics

Here, we consider a distribution network integrating demand response (DR) participants in the presence of uncertain renewable suppliers and outdoor temperatures. A bilevel optimization model is proposed to capture the intricate dynamics between price-incentivized DR participants and distribution system operations, including energy procurement and active/reactive power flows. The model is formulated as a distributional robust bilevel optimization using Wasserstein metrics. We show favorable data-driven properties including out-of-sample guarantee and asymptotic consistency. Furthermore, we present a tractable mixed-integer linear programming reformulation and characterize the worst-case distribution. Computational experiments are conducted on a modified 33-bus system. Our findings underscore the efficacy of the pricing strategies derived from the proposed bilevel optimization model. These strategies not only effectively manage DR participants' behavior but also bring equity considerations among households with various characteristics to light. The results contribute to a deeper understanding of the interplay between distribution system operators and DR participants.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems

We address the bilevel optimization problem of identifying the most critical attacks to an alternating current (AC) power flow network. The upper-level binary maximization problem consists of choosing an attack that is treated as a parameter in the lower-level defender minimization problem. Instances of the lower-level global minimization problem by themselves are NP-hard due to the nonconvex AC power flow constraints, and bilevel solution approaches commonly apply a convex relaxation or approximation to allow for tractable bilevel reformulations at the cost of underestimating some power system vulnerabilities. Our main contribution is to provide an alternative branch-and-bound algorithm whose upper bounding mechanism (in a maximization context) is based on a reformulation that avoids relaxation of the AC power flow constraints in the lower-level defender problem. Lower bounding is provided with semidefinite programming (SDP) relaxed solutions to the lower-level problem. We establish finite termination with guarantees of either a globally optimal solution to the original bilevel problem, or a globally optimal solution to the SDP-relaxed bilevel problem which is included in a vetted list of upper-level attack solutions, at least one of which is a globally optimal solution to the bilevel problem. We demonstrate through computational experiments applied to IEEE case instances both the relevance of our contribution, and the effectiveness of our contributed algorithm for identifying power system vulnerabilities without resorting to convex relaxations of the lower-level problem. We conclude with a discussion of future extensions and improvements.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Disjunctive optimization model and algorithm for long-term capacity expansion planning of reliable power generation systems

This paper proposes a new optimization model and algorithm for long-term capacity expansion planning of reliable power generation systems. The model optimizes both investment decisions (e.g., size, location, and time to install, retire and decommission facilities) and operation decisions (e.g., on/off status, operating capacity, and expected power output). It is also able to optimize reserve systems (or backup systems), as well as the main systems, to improve power systems reliability. An impact of operational strategies of generators (i.e., participating in electricity production vs. remaining as idle units during operation) on power systems reliability is considered. Probability of equipment failures and capacity failure states are used to rigorously estimate the power systems reliability depending on design and operation strategies. The optimization model is formulated with Generalized Disjunctive Programming (GDP), which is reformulated as a mixed-integer linear programming (MILP) model using the Hull relaxation. Two reliability-related penalties, such as downtime penalty and unmet demand penalty, are included in the objective function to maximize reliability while minimizing the total net present cost. Furthermore, a bilevel decomposition with tailored cuts is developed to reduce computational times of the multi-scale optimization model. The effectiveness of the proposed model is shown by comparing the results with the results obtained from the expansion planning models that do not explicitly consider reliability. In conclusion, we also show that the proposed bilevel decomposition is computationally efficient for solving large scale problems through 5-years and 10-years planning case studies.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2022

Hierarchical Transactive Control of Flexible Building Loads Under Distribution LMP

With grid modernization efforts, future distribution networks, which consist of various distributed generators and flexible loads, will be more flexible and active. All new network components of distributed energy resources (DERs) drive and enable the transition towards a market-based distribution net-work that seeks the optimal allocation of all DERs. To address challenges associated with DERs, one promising solution is to utilize demand-side flexibility of building loads facilitated by demand response (DR) programs and provide ancillary grid services through distribution-level markets. Under this new paradigm, this paper proposes an efficient DR management strategy incorporating emerging price signals of distribution markets, i.e., distribution locational marginal price (DLMP), based on a hierarchical transactive control approach. The proposed approach establishes a two-layer decision-making framework; the upper layer formulates a bilevel model to obtain an optimal demand response (ODR) under DLMP, and the lower layer employs model-free control to dispatch the (aggregated) ODR to individual end users. Numerical case studies using a modified IEEE 33 test network are performed to verify the effectiveness of the proposed approach; load shifting and peak shaving for the distribution system operator and payments’ reduction for end users while maintaining their comfort.

Park, Byungkwon↗
DOE OSTI2022

A Trilevel Model for Segmentation of the Power Transmission Grid Cyber Network

Network segmentation of a power grid's communication system can make the grid more resilient to cyberattacks. Here we develop a novel trilevel programming model to optimally segment a grid communication system, taking into account the actions of an information technology (IT) administrator, attacker, and grid operator. The IT administrator is allowed to segment existing networks, and the attacker is given a budget to inflict damage on the grid by attacking the segmented communication system. Finally, the grid operator can redispatch the grid after the attack to minimize damage. The resulting problem is a trilevel interdiction problem that we solve using a branch and bound algorithm for bilevel problems. We demonstrate the benefits of optimal network segmentation through case studies on the 9-bus Western System Coordinating Council (WSCC) system and the 30-bus IEEE system. These examples illustrate that network segmentation can significantly reduce the threat posed by a cyberattacker.

24 POWER TRANSMISSION AND DISTRIBUTION↗