×

zbMATH — the first resource for mathematics

A method for solving bilevel linear programming problems. (English) Zbl 1154.90543
Summary: This paper presents an approach for solving bilevel linear programming problems (BLPP). It is based on the result that an optimal solution to the BLPP is reachable at an extreme point of the underlying region. Consequently, we develop a pivot technique to find the global optimal solution on an expanded tableau that represents the data of the BLPP. The pivot technique allows to rank in increasing order the outer level objective function value until a value is reached with a corresponding extreme point feasible for the BLPP. This solution is then the required global solution. Numerical examples are provided. Solutions obtained through our algorithm to some problems available in the literature show that these problems were until now wrongly solved.

MSC:
90C05 Linear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alexandrov N., Department of Computational and Applied Mathematics (1994)
[2] Anandalingam G., IEEE Transactions on Automatic Control 35 pp 1170– (1990) · Zbl 0721.90098
[3] Bard J. F., JNonconvex Optimization and its Applications 30 (1998)
[4] Bard J. F., Journal of Optimization Theory and Application 68 pp 371– (1991) · Zbl 0696.90086
[5] Bard J. F., Computers and Operations Research 9 pp 77– (1982)
[6] Bard J. F., SIAM Journal on Scientific and Statistical Computing 11 (4598) pp 281– (1990) · Zbl 0702.65060
[7] Bard J. F., Mathematics of Operations Research 8 pp 260– (1983) · Zbl 0516.90061
[8] Bialas W., Management Science 30 pp 1004– (1984) · Zbl 0559.90053
[9] Bialas W., Technical Report 80–2, State University of New York at Buffalo, Operations Research Program (1980)
[10] Bialas W., IEEE Transaction on Automatic Control 27 pp 211– (1982) · Zbl 0487.90005
[11] Campelo M., European Journal of Operational Research 126 (5) pp 454– (2000)
[12] Charles A., Applied Mathematics and Computation 181 pp 351– (2006) · Zbl 1163.90641
[13] Chen Y., Optimization 32 pp 193– (1995)
[14] Chenggen S., Applied Mathematics and Computation 164 pp 843– (2005) · Zbl 1072.65085
[15] Clarke P., Naval Research Logistics 35 pp 413– (1998) · Zbl 0653.90045
[16] Clarke P., Computers and Chemical Engineering 14 pp 87– (1990)
[17] Candler W., Computers and Operations Research 9 pp 59– (1982)
[18] Dempe S., Optimization 18 pp 373– (1987) · Zbl 0634.90075
[19] Dempe S., Foundations of Bilevel Programming (2002) · Zbl 1038.90097
[20] Falks J.F., Mathematical Programming 5 pp 169– (1973) · Zbl 0276.90053
[21] Floudas C., Handbook of Test Problems in Local and Global Optimization (1999) · Zbl 0943.90001
[22] Fortuny-Amat J., Journal of the Operational Research Society 32 pp 783– (1981) · Zbl 0466.93003
[23] Harker P., Operations Research Letters 7 pp 61– (1988) · Zbl 0648.90065
[24] Hansen P., SIAM Journal on Scientific and Statistical Computing 13 pp 1194– (1992) · Zbl 0760.65063
[25] Judice J., Annals of Operations Research 34 pp 89– (1992) · Zbl 0749.90049
[26] Judice J., Investigaao Operacional 8 pp 77– (1988)
[27] Liu Y., European Journal of Operational Research 73 pp 164– (1994) · Zbl 0806.90084
[28] Lu J., Applied Mathematics and Computation (2004)
[29] Lu J., Applied Mathematics and Computation 162 pp 5163– (2005)
[30] Lu J., Applied Mathematics and Computation 16 pp 169– (2005)
[31] Marcotte P., Mathematical Programming 34 pp 142– (1986) · Zbl 0604.90053
[32] Manoel C., European Journal of Operational Research 126 pp 454– (2000) · Zbl 0970.90048
[33] Manoel C., Journal of Global Optimization pp 245– (2000)
[34] Migdalas A., Journal of Global Optimization 7 pp 381– (1995) · Zbl 0844.90050
[35] Onal H., European Journal of Operational Research 67 pp 126– (1993) · Zbl 0806.90086
[36] Omarand A. B., Operations Research 38 pp 556– (1990) · Zbl 0708.90052
[37] Onal H., Computational Experience with a Mixed Solution Method for Bilevel Linear/quadratic Programs (1992)
[38] Stackelberg H., Theory of the Market Economy (1952)
[39] Shimizu K., Nondifferentiable and Two-level Mathematical Programming (1997) · Zbl 0878.90088
[40] Tuy H., Journal of Global Optimization 3 pp 1– (1993) · Zbl 0771.90108
[41] Wayne L., Operations Research, Applications and Algorithms, 3. ed. (1994)
[42] White D. J., Journal of Global Optimization 3 pp 397– (1993) · Zbl 0791.90047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.