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:

  1. 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}
}