Parametric integer programming algorithm for bilevel mixed integer programs

Parametric integer programming algorithm for bilevel mixed integer programs

0.00 Avg rating0 Votes
Article ID: iaor20104886
Volume: 146
Issue: 1
Start Page Number: 137
End Page Number: 150
Publication Date: Jul 2010
Journal: Journal of Optimization Theory and Applications
Authors: , ,
Keywords: programming (bilevel)
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 absolute precision. For the pure integer case where the leader's variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.

Reviews

Required fields are marked *. Your email address will not be published.