COMPUTATIONAL DIFFICULTIES OF BILEVEL LINEAR-PROGRAMMING

被引：274

作者：

BENAYED, O ^{[1
]}

BLAIR, CE ^{[1
]}

机构：

[1] UNIV ILLINOIS,DEPT BUSINESS ADM,CHAMPAIGN,IL 61820

来源：

OPERATIONS RESEARCH | 1990年 / 38卷 / 03期

关键词：

D O I：

10.1287/opre.38.3.556

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：556 / 560

页数：5

共 17 条

[1] AN EXPLICIT SOLUTION TO THE MULTILEVEL PROGRAMMING PROBLEM
BARD, JF
FALK, JE
[J]. COMPUTERS & OPERATIONS RESEARCH, 1982, 9 (01) : 77 - 100
[2] AN EFFICIENT POINT ALGORITHM FOR A LINEAR 2-STAGE OPTIMIZATION PROBLEM
BARD, JF
[J]. OPERATIONS RESEARCH, 1983, 31 (04) : 670 - 684
[3] BARD JF, 1987, BRANCH BOUND ALGORIT
[4] Ben-Ayed O., 1988, THESIS U ILLINOIS UR
[5] BIALAS W, 1980, 802 STAT U NEW YORK
[6] ON 2-LEVEL OPTIMIZATION
BIALAS, WF
KARWAN, MH
[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1982, 27 (01) : 211 - 214
[7] 2-LEVEL LINEAR-PROGRAMMING
BIALAS, WF
KARWAN, MH
[J]. MANAGEMENT SCIENCE, 1984, 30 (08) : 1004 - 1020
[8] INTEGRATION OF SUPPLY-AND-DEMAND MODELS IN TRANSPORTATION AND LOCATION - PROBLEM FORMULATIONS AND RESEARCH QUESTIONS
BOYCE, DE
[J]. ENVIRONMENT AND PLANNING A, 1986, 18 (04) : 485 - 489
[9] A LINEAR 2-LEVEL PROGRAMMING PROBLEM
CANDLER, W
TOWNSLEY, R
[J]. COMPUTERS & OPERATIONS RESEARCH, 1982, 9 (01) : 59 - 76
[10] Falk J. E., 1973, Mathematical Programming, V5, P169, DOI 10.1007/BF01580119

← 1 2 →