期刊
ANNALS OF OPERATIONS RESEARCH
卷 272, 期 1-2, 页码 99-117出版社
SPRINGER
DOI: 10.1007/s10479-017-2694-x
关键词
Bilevel optimization; Bilevel integer programming; Mixed integer linear programming
资金
- National Science Foundation [CMMI-1634835]
- Laboratory of Algorithms and Technologies for Network Analysis (LATNA)
- RSF [14-41-00039]
We consider reformulations of a class of bilevel linear integer programs as equivalent linear mixed-integer programs (linear MIPs). The most common technique to reformulate such programs as a single-level problem is to replace the lower-level linear optimization problem by Karush-Kuhn-Tucker (KKT) optimality conditions. Employing the strong duality (SD) property of linear programs is an alternative method to perform such transformations. In this note, we describe two SD-based reformulations where the key idea is to exploit the binary expansion of upper-level integer variables. We compare the performance of an off-the-shelf MIP solver with the SD-based reformulations against the KKT-based one and show that the SD-based approaches can lead to orders of magnitude reduction in computational times for certain classes of instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据