A parametric integer programming algorithm for bilevel mixed integer programs

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.

11 pages

Cited by in corpus (6)

• A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization
• A Projection-Based Reformulation and Decomposition Algorithm for Global Optimization of a Class of Mixed Integer Bilevel Linear Programs
• Rational Generating Functions and Integer Programming Games
• A Framework for Generalized Benders' Decomposition and Its Application to Multilevel Optimization
• Computing the number of numerical semigroups using generating functions
• A Bilevel Approach to Integrated Surgeon Scheduling and Surgery Planning solved via Branch-and-Price