Mathematics – Optimization and Control
Scientific paper
2009-07-07
Mathematics
Optimization and Control
11 pages
Scientific paper
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.
Köppe Matthias
Queyranne Maurice
Ryan Christopher Thomas
No associations
LandOfFree
A parametric integer programming algorithm for bilevel mixed integer programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A parametric integer programming algorithm for bilevel mixed integer programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A parametric integer programming algorithm for bilevel mixed integer programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-319462