Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0708.90052
Ben-Ayed, Omar; Blair, Charles E.
Computational difficulties of bilevel linear programming.
(English)
[J] Oper. Res. 38, No.3, 556-560 (1990). ISSN 0030-364X

Summary: We show, using small examples, that two algorithms previously published for the bilevel linear programming problem (BLP) [see {\it J. F. Bard}, ibid. 31, 670-684 (1983; Zbl 0525.90086); and {\it W. F. Bialas} and {\it M. H. Karwan}, Manage. Sci. 30, 1004-1020 (1984; Zbl 0559.90053)] 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.
MSC 2000:
*90C05 Linear programming
65K05 Mathematical programming (numerical methods)
90C60 Abstract computational complexity for math. programming problems
90-08 Computational methods (optimization)

Keywords: parametric complementary pivot algorithm; grid search algorithm; bilevel linear programming; heuristics; NP-hard

Citations: Zbl 0525.90086; Zbl 0559.90053

Highlights
Master Server