4 Presentations

• 
  04:45 PM - 05:07 PM

  Unboundedness in Bilevel Optimization

  • Bárbara Rodrigues, presenter, University of Edinburgh
  • Margarida Carvalho, Université de Montréal
  • Miguel F. Anjos, University of Edinburgh
  • Nagisa Sugishita, Université de Montréal

  Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel optimization by studying its computational complexity and developing algorithmic approaches to detect it. We show that deciding whether an optimistic linear bilevel problem is unbounded is strongly NP-complete. Furthermore, we extend the theoretical intractability result to the multilevel case, by showing that for each extra level added, the decision problem of checking unboundedness moves up a level in the polynomial hierarchy. Finally, we introduce two algorithmic approaches to determine whether a linear bilevel problem is unbounded and, if so, return a certificate of unboundedness. This certificate consists of a direction of unboundedness and corresponding bilevel feasible point. We present a brief computational comparison between these algorithmic approaches.

• 
  05:07 PM - 05:29 PM

  Game-theoretic based relaxations in bilevel optimization

  • Noah Weninger, presenter, University of Waterloo
  • Ricardo Fukasawa, University of Waterloo

  We introduce a framework for relaxing Stackelberg zero-sum games with perfect information, with a focus on those arising from discrete bilevel optimization. The framework consists of operators which transform games while maintaining an approximation or bound on the optimal objective value. This simplifies and generalizes our two previous works on knapsack and matroid interdiction. It also generalizes well-known techniques including the high point relaxation and the derivation of bounds by restricting/relaxing the lower level problem. To further motivate this approach, we apply it to matching interdiction, in which the objective is to interdict (i.e., remove) edges from a graph so that the maximum matching weight is minimized, subject to a knapsack constraint on the set of interdicted edges. We present a branch-and-bound algorithm for this problem which uses a new lower bound derived using our framework.

• 
  05:29 PM - 05:51 PM

  The Restricted Value Function of MILPs and its construction with SYMPHONY

  • Federico Battista, presenter, Lehigh University
  • Ted Ralphs, Lehigh University

  The solution methods of a wide class of discrete optimization problems require understanding the functional dependence of the optimal value on various components of the input.
  For multi-level problems, this manifests itself in the dependence of the followers' reactions on the leader's decision, whereas for multi-objective problems, it is captured in the trade-offs inherent in optimizing multiple objectives simultaneously. Although they may seem distinct, such dependencies can all be captured by
  the so-called restricted value function (RVF) that generalizes the definition of the standard MILP value function. In this talk, we describe how this perspective leads to the development of a class of algorithms for constructing the efficient frontier of a general multi-objective mixed integer linear optimization problem in a single branch-and-bound tree. The implementation exploits the warm-starting capabilities of the open-source solver SYMPHONY.

• 
  05:51 PM - 06:13 PM

  Latest Developments in the MibS Solver for Mixed Integer Bilevel Optimization

  • Ted Ralphs, presenter, Lehigh University
  • Sahar Tahernejad, Lindo
  • Scott DeNegre, Hospital for Special Surgery

  MibS is an open source solver for mixed integer bilevel linear optimization. Its performance has been improved substantially in recent years through a combination of new methodologies and improvements to the algorithmic control mechanisms. In this talk, we briefly review the algorithmic approach with a focus on recent improvements. A summary of the extensive computations that went into this effort will be presented.