bilevel optimization

A Computational Study for 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 provides an extensive computational study for … 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 Binary Bilevel Programs using Decision Diagrams

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

    Binary 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 Weak 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 , , , ,

    In recent years, significant attention has been devoted to the issue of explainability in automated decision-making tools. 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 … 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

    Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms

  • Victor Bucarey
  • Sophia Calderón
  • Gonzalo Muñoz
  • Frédéric Semet
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Other Topics Tags ,

    Dealing with uncertainty in optimization parameters is an important and longstanding challenge. Typically, uncertain parameters are predicted accurately, and then a deterministic optimization problem is solved. However, the decisions produced by this so-called {\it predict-then-optimize} procedure can be highly sensitive to uncertain parameters. In this work, we contribute to recent efforts in producing {\it decision-focused} … Read more

    A Branch-and-Price-and-Cut Algorithm for Discrete Network Design Problems Under Traffic Equilibrium

  • David Rey
  • Michael Levin
    • Categories (Mixed) Integer Nonlinear Programming, Bilevel Optimization, Transportation Tags , , , ,

    This study addresses discrete network design problems under traffic equilibrium conditions or DNDPs. Given a network and a budget, DNDPs aim to model all-or-nothing decisions such as link addition to minimize network congestion effects. Congestion is measured using traffic equilibrium theory where link travel times are modeled as convex flow-dependent functions and where users make … Read more