Journal
ANNALS OF OPERATIONS RESEARCH
Volume 272, Issue 1-2, Pages 99-117Publisher
SPRINGER
DOI: 10.1007/s10479-017-2694-x
Keywords
Bilevel optimization; Bilevel integer programming; Mixed integer linear programming
Categories
Funding
- National Science Foundation [CMMI-1634835]
- Laboratory of Algorithms and Technologies for Network Analysis (LATNA)
- RSF [14-41-00039]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available