Computational Difficulties of Bilevel Linear Programming
Published Online:1 Jun 1990https://doi.org/10.1287/opre.38.3.556
Abstract
We show, using small examples, that two algorithms previously published for the Bilevel Linear Programming problem (BLP) may fail to find the optimal solution and thus must be considered to be heuristics. A proof is given that solving BLP problems is NP-hard, which makes it unlikely that there is a good, exact algorithm.
