A parametric integer programming algorithm for bilevel mixed integer programs
Skip to main content
eScholarship
Open Access Publications from the University of California

A parametric integer programming algorithm for bilevel mixed integer programs

  • Author(s): Köppe, Matthias
  • Queyranne, Maurice
  • Ryan, Christopher Thomas
  • et al.

Published Web Location

https://arxiv.org/pdf/0907.1298.pdf
No data is associated with this publication.
Abstract

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader's variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case it yields a ``better than fully polynomial time'' approximation scheme with running time polynomial in the logarithm of the relative precision. For the pure integer case where the leader's variables are integer, and hence optimal solutions are guaranteed to exist, we present two algorithms which run in polynomial time when the total number of variables is fixed.

Item not freely available? Link broken?
Report a problem accessing this item