Computational Difficulties of Bilevel Linear Programming

Omar Ben-Ayed and Charles E. Blair
Additional contact information
Omar Ben-Ayed: University of Illinois, Champaign, Illinois
Charles E. Blair: University of Illinois, Champaign, Illinois

Operations Research, 1990, vol. 38, issue 3, 556-560

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.

Keywords: analysis of algorithms; computational complexity: bilevel linear programming is NP-hard; games/group decisions; noncooperative: algorithms for solving Stackelberg games; programming; multiple criteria: bilevel linear programming (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.3.556 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:3:p:556-560

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().