Bilevel Optimization

A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

    On Local Search in Bilevel Mixed-Integer Linear Programming

  • Eneko C. Clemente
  • Oleg A. Prokopyev
    • Categories Bilevel Optimization, Game Theory, Other Topics Tags , ,

    Two-level hierarchical decision-making problems, where a leader’s choice influences a follower’s action, arise across key business and public-sector domains, from market design and pricing to defense. These problems are typically modeled as bilevel programs and are known to be notoriously hard to solve at scale. In single-level combinatorial optimization, especially for challenging instances, local search … Read more

    Branch-and-Cut for Mixed-Integer Generalized Nash Equilibrium Problems

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Game Theory Tags , , , ,

    Generalized Nash equilibrium problems with mixed-integer variables form an important class of games in which each player solves a mixed-integer optimization problem with respect to her own variables and the strategy space of each player depends on the strategies chosen by the rival players. In this work, we introduce a branch-and-cut algorithm to compute exact … Read more

    Stability analysis for two-level value functions and application to numerically solve a pessimistic bilevel program

  • Alain Zemkoho
    • Categories Bilevel Optimization Tags , , , ,

    Some stability results are presented for a two-level value function, which is the optimal value function of a parametric optimization problem constrained by the optimal solution set of another parameteric optimization problem. It is then shown how to use these stability results to write down (and subsequently compute) stationary points for a pessimistic bilevel optimization … Read more

    Mathematical programs with complementarity constraints and application to hyperparameter tuning for nonlinear support vector machines

  • Samuel Ward
  • Alain Zemkoho
  • Selin Damla Ahipasaoglu
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Optimization in Data Science Tags , , , , ,

    We consider the Mathematical Program with Complementarity Constraints (MPCC). One of the main challenges in solving this problem is the systematic failure of standard Constraint Qualifications (CQs). Carefully accounting for the combinatorial nature of the complementarity constraints, tractable versions of the Mangasarian Fromovitz Constraint Qualification (MFCQ) have been designed and widely studied in the literature. … Read more

    Fair network design problem: an application to EV charging station capacity expansion

  • Nagisa Sugishita
  • Margarida Carvalho
    • Categories Bilevel Optimization Tags , , ,

    This study addresses the bilevel network design problem (NDP) with congestion. The upper-level decision-maker (a network designer) selects a set of arcs to add to an existing transportation network, while the lower-level decision-makers (drivers) respond by choosing routes that minimize their individual travel times, resulting in user equilibrium. In this work, we propose two novel … Read more

    On Coupling Constraints in Pessimistic Linear Bilevel Optimization

  • Dorothee Henke
  • Henri Lefebvre
  • Martin Schmidt
  • Johannes Thürauf
    • Categories Bilevel Optimization Tags , , ,

    The literature on pessimistic bilevel optimization with coupling constraints is rather scarce and it has been common sense that these problems are harder to tackle than pessimistic bilevel problems without coupling constraints. In this note, we show that this is not the case. To this end, given a pessimistic problem with coupling constraints, we derive … Read more

    A new problem qualification based on approximate KKT conditions for Lipschitzian optimization with application to bilevel programming

  • Isabella Käming
  • Andreas Fischer
  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization

    When dealing with general Lipschitzian optimization problems, there are many problem classes where even weak constraint qualications fail at local minimizers. In contrast to a constraint qualification, a problem qualification does not only rely on the constraints but also on the objective function to guarantee that a local minimizer is a Karush-Kuhn-Tucker (KKT) point. For … Read more

    Relaxation methods for pessimistic bilevel optimization

  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , ,

    We consider a smooth pessimistic bilevel optimization problem, where the lower-level problem is convex and satisfies the Slater constraint qualification. These assumptions ensure that the Karush-Kuhn-Tucker (KKT) reformulation of our problem is well-defined. We then introduce and study the (i) Scholtes, (ii) Lin and Fukushima, (iii) Kadrani, Dussault and Benchakroun, (iv) Steffensen and Ulbrich, and … Read more

    Solving Decision-Dependent Robust Problems as Bilevel Optimization Problems

  • Henri Lefebvre
  • Martin Schmidt
  • Simon Stevens
  • Johannes Thürauf
    • Categories Bilevel Optimization, Robust Optimization Tags , , ,

    Both bilevel and robust optimization are established fields of mathematical optimization and operations research. However, only until recently, the similarities in their mathematical structure has neither been studied theoretically nor exploited computationally. Based on the recent results by Goerigk et al. (2025), this paper is the first one that reformulates a given strictly robust optimization … Read more