Solving Linear Bilevel Problems Using Big-Ms: Not All That Glitters Is Gold¶
This is a summary of the work that can be found in [1]. Open Access pdf is available at [2].
Abstract¶
The most common procedure to solve a linear bilevel problem in the PES community is, by far, to transform it into an equivalent single-level problem by replacing the lower level with its KKT optimality conditions. Then, the complementarity conditions are reformulated using additional binary variables and large enough constants (big-Ms) to cast the single-level problemas a mixed-integer linear program that can be solved using optimization software. In most cases, such large constants are tuned by trial and error. We show, through a counterexample, that this widely used trial-and-error approach may lead to highly suboptimal solutions. Then, further research is required to properly select big-M values to solve linear bilevel problems.
Citation¶
If you would like to cite this work, please use the following citation:
Pineda and J. M. Morales, Solving Linear Bilevel Problems Using Big-Ms: Not All That Glitters Is Gold, IEEE Transactions on Power Systems, vol. 34, no. 3, pp. 2469–2471, May 2019.
You can use this bibtex entry:
@article{pineda2019solving,
title={Solving linear bilevel problems using big-Ms: not all that glitters is gold},
author={Pineda, Salvador and Morales, Juan Miguel},
journal={IEEE Transactions on Power Systems},
volume={34},
number={3},
pages={2469--2471},
year={2019},
publisher={IEEE}
}