Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

DOI10.1287/opre.2019.1944zbMath1457.90094OpenAlexW3038643818MaRDI QIDQ5144791

Martine Labbé, Fränk Plein, Martin Schmidt, Thomas Kleinert

Publication date: 19 January 2021

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.2019.1944

zbMATH Keywords

hardnessbilevel optimizationmathematical programs with complementarity constraints (MPCC)big-\(M\)bounding polyhedra

Mathematics Subject Classification ID

Integer programming (90C10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

A bilevel optimization approach to decide the feasibility of bookings in the European gas market ⋮ Solving binary-constrained mixed complementarity problems using continuous reformulations ⋮ Metaheuristics for bilevel optimization: a comprehensive review ⋮ Exact solution approaches for a class of bilevel fractional programs ⋮ A decision tool based on bilevel optimization for the allocation of water resources in a hierarchical system ⋮ Coordinating harvest planning and scheduling in an agricultural supply chain through a stochastic bilevel programming ⋮ Why there is no need to use a big-\(M\) in linear bilevel optimization: a computational study of two ready-to-use approaches ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid ⋮ A general purpose exact solution method for mixed integer concave minimization problems ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ The value of shared information for allocation of drivers in ride-hailing: a proof-of-concept study ⋮ On a computationally ill-behaved bilevel problem with a continuous and nonconvex lower level ⋮ Presolving linear bilevel optimization problems ⋮ Learning lyapunov functions for hybrid systems ⋮ Detecting and solving aircraft conflicts using bilevel programming ⋮ The impact of neighboring markets on renewable locations, transmission expansion, and generation investment ⋮ Closing the gap in linear bilevel optimization: a new valid primal-dual inequality ⋮ Outer approximation for global optimization of mixed-integer quadratic bilevel problems ⋮ A robust approach for modeling limited observability in bilevel optimization ⋮ The cost of decoupling trade and transport in the European entry-exit gas market with linear physics modeling ⋮ A complementarity model for electric power transmission-distribution coordination under uncertainty ⋮ Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method ⋮ An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities ⋮ On convex lower-level black-box constraints in bilevel optimization with an application to gas market models with chance constraints ⋮ A framework for generalized Benders' decomposition and its application to multilevel optimization ⋮ Algorithms for Linear Bilevel Optimization ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transmission and generation investment in electricity markets: the effects of market splitting and network fee regimes
• The EU regulation on cross-border trade of electricity: a two-stage equilibrium model
• Some properties of the bilevel programming problem
• Descent approaches for quadratic bilevel programming
• Links between linear bilevel and mixed 0-1 programming problems
• Foundations of bilevel programming
• Nonconvex equilibrium models for gas market analysis: failure of standard techniques and alternative modeling approaches
• A study of general and security Stackelberg game formulations
• Global optimization of multilevel electricity market models including network design and graph partitioning
• A multilevel model of the European entry-exit gas market
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• Boundedness relations for linear constraint sets
• A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing
• Bilevel Knapsack with Interdiction Constraints
• A Nonparametric Approach to Multiproduct Pricing
• Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices
• A Branch and Bound Algorithm for the Bilevel Programming Problem
• A Representation and Economic Interpretation of a Two-Level Programming Problem
• New Branch-and-Bound Rules for Linear Bilevel Programming
• On the Computational Complexity of Combinatorial Problems
• Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
• Bilevel Programming Problems
• Two-Level Linear Programming
• Mathematical Programs with Optimization Problems in the Constraints
• Bilevel programming and price setting problems