4 présentations

• 
  08h30 - 08h52

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

  • Vasquez Sebastian, prés., Carnegie Mellon University
  • Lozano Leonardo, University of Cincinnati
  • van Hoeve Willem-Jan, Carnegie Mellon University

  Integer bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. This work introduces 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. Additionally, we explain how to derive dual bounds from restricted decision diagrams, reduce the size of the resulting reformulation, and address the pessimistic version of the problem. Finally, we compare our method against state-of-the-art bilevel programming solvers, demonstrating competitive performance, particularly for problem instances where the follower’s problem exhibits a combinatorial structure suitable for decision diagrams.

• 
  08h52 - 09h14

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

  • Arie Koster, prés., RWTH Aachen University
  • Vladimir Stadnichuk, RWTH Aachen University

  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 branch-and-cut decomposition method that starts by solving the first level and then iteratively generates second-level feasibility and optimality cuts that are obtained by solving a slightly adjusted second-level problem. Compared to many other existing solution methods, we do not rely on solving the High Point Relaxation of the bilevel problem but fully project out the second level, resulting in significant computational advantages when the second-level problem is very large or possesses a weak LP relaxation. Also, our approach can be fully automated within a MIP solver, making it very easy to apply for those who do not want to design problem-tailored algorithms for their bilevel problem. Computational results for a bilevel network design problem demonstrate that our approach efficiently solves instances with hundreds of subproblems in a few minutes, significantly outperforming the Benders-like decomposition from the literature on challenging instances.

• 
  09h14 - 09h36

  Integer robust optimization problems with integer decision-dependent uncertainty sets

  • Leonardo Lozano, prés., University of Cincinnati
  • Borrero Juan, University of South Florida

  We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an uncertainty set that has a functional dependence on the decisions of the planner. We propose three
  methods to reformulate and solve these problems: the first is based on a single-level semi-infinite reformulation; the second is based on a single-follower bilevel reformulation; and the third one is a multiple-follower bilevel reformulation where each robust constraint is associated with a follower. The multiple-follower bilevel formulation is further transformed into a multicommodity flow single-level mixed-integer problem by exploiting recent advancements in decision diagrams. We perform numerical experiments that show that the column and constraint generation algorithm can solve small- and medium-scale instances within a few minutes. This method is outperformed by the multicommodity flow formulation when dealing with problems with a single robust constraint.

• 
  09h36 - 09h58

  Bilevel Problems with Gamma-Robust Followers: Exact and Heuristic Approaches

  • Ivana Ljubic, prés., ESSEC
  • Yasmine Beck, ESSEC Business School
  • Martin Schmidt, University of Trier

  We study bilevel combinatorial optimization problems in which the follower uses Gamma-robustness to hedge against uncertainty in the coefficients of the objective function.
  Two branch-and-cut variants are proposed, along with a new iterative heuristic approach that solves a polynomial number of deterministic bilevel counterparts. This heuristic also provides valid dual bounds, and on the set of tested benchmark instances, it even closes the optimality gap faster and for a larger number of instances than the two exact approaches.