bilevel optimization

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

    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

    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

    An Oracle-based Approach for Price-setting Problems in Logistics

  • Nele Pommerening
  • Maja Hügging
  • Dorothee Henke
  • Christoph Buchheim
  • Uwe Clausen
    • Categories Integer Programming, Transportation Tags , , ,

    We study a bilevel hub location problem where on the upper level, a shipment service provider –the leader–builds a transportation network and sets the prices of shipments on each possible transportation relation. Here, the leader has to take into account the customers’ reaction — the follower — who will only purchase transport services depending on … Read more

    A Single-Level Reformulation of Integer Bilevel Programs using Decision Diagrams

  • Sebastian Vasquez
  • Leonardo Lozano
  • Willem-Jan van Hoeve
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    Integer bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable … Read more

    Two-Stage Distributionally Robust Optimization: Intuitive Understanding and Algorithm Development from the Primal Perspective

  • Zhengsong Lu
  • Bo Zeng
    • Categories Robust Optimization, Semi-infinite Programming Tags , ,

    In this paper, we study the two-stage distributionally robust optimization (DRO) problem from the primal perspective. Unlike existing approaches, this perspective allows us to build a deeper and more intuitive understanding on DRO, to leverage classical and well established solution methods and to develop a general and fast decomposition algorithm (and its variants), and to … Read more

    Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables

  • Vladimir Stadnichuk
  • Arie M.C.A. Koster
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Network Optimization Tags , , , ,

    We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more

    Computing Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method

  • Henri Lefebvre
  • Martin Schmidt
    • Categories Energy, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    Explainable artificial intelligence is one of the most important trends in modern machine-learning research. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems as an automated … Read more

    Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

  • Immanuel M. Bomze
  • Martin Schmidt
  • Horländer Andreas
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , ,

    We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of … Read more

    Closest Assignment Constraints for Hub Disruption Problems

  • Saikat Mukherjee
  • Prasanna Ramamoorthy
    • Categories Integer Programming Tags , , ,

    Supply chains and logistics can be well represented with hub networks. Operations of these hubs can be disrupted due to unanticipated occurrences or attacks. This study includes Closest assignment Constraints related to hub disruption problems, which can be used in single-level reformulation of the bilevel model. In this study, We propose new sets of constraints … Read more