期刊
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
卷 146, 期 1, 页码 137-150出版社
SPRINGER/PLENUM PUBLISHERS
DOI: 10.1007/s10957-010-9668-3
关键词
Bilevel mixed integer linear programming; Parametric integer linear programming; Computational complexity; Binary search
资金
- Natural Sciences and Engineering Research Council (NSERC) of Canada
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据