# Solving Linear Bilevel Problems Using Big-Ms: Not All That Glitters Is Gold

arXiv: https://arxiv.org/abs/1809.10448 · HTML: https://mlsanity.com/paper/1809.10448/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2018.

## Built on by (most cited first, 2 of 2)

- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Prescribing net demand for two-stage electricity generation scheduling](https://mlsanity.com/paper/2108.01003/) (2021)

## Abstract (arXiv)

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 problem as 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.