Bilevel linear programming. (English) Zbl 0783.90068
Summary: This paper gives a review of the features of Bilevel Linear Programming (BLP) by presenting prior results as well as providing new results, including the capability of the problem to formulate any piecewise linear function and its connection to other optimization problems. The paper also surveys the applications and the algorithms of BLP; the NP-hardness of BLP did not prevent the success of several applications of the model to real world problems. Certain confusing representations in the literature are clarified.
References:
| [1] | Keeney, R. L.; Raiffa, H., Decisions with Multiple Objectives: Preferences and Value Trade-Offs (1976), Wiley: Wiley New York · Zbl 0488.90001 |
| [2] | Zeleny, M., Multiple Criteria Decision Making (1982), McGraw-Hill: McGraw-Hill New York · Zbl 0588.90019 |
| [3] | Falk, J. E.; Fiacco, A. V., The use of mathematical programming: who let the man out?, Computers Ops Res., 9, 3-5 (1982) |
| [4] | (Sefarini, P., Mathematics of Multi-Objective Optimization CISM 289 (1985), Springer: Springer New York) |
| [5] | Candler, W.; Townsley, R., A linear two-level programming problem, Computers Ops Res., 9, 59-76 (1982) |
| [6] | Bialas, W. F.; Karwan, M. H., On two-level optimization, IEEE Trans. Auto. Cont., AC-27, 211-214 (1982) · Zbl 0487.90005 |
| [7] | Bialas, W. F.; Karwan, M. H., Two-level linear programming, Mgmt Sci., 30, 1004-1020 (1984) · Zbl 0559.90053 |
| [8] | Bard, J. F., Optimality conditions for the bilevel programming problem, Nav. Res. Logist. Q., 31, 13-26 (1984) · Zbl 0537.90087 |
| [9] | Bard, J. F., Convex two-level optimization, Math. Programm., 40, 15-27 (1988) · Zbl 0655.90060 |
| [10] | Anandalingam, G., An analysis of incentives in bilevel programming, (IEEE Proc. Int. Conf. Cybern. Soc. (1985)), 825-929 |
| [11] | Moore, J. T.; Bard, J. F., An Algorithm for the Zero-One Bilevel Programming Problem (1987), U.S. Air Force, Strategic Air Command Headquarters: U.S. Air Force, Strategic Air Command Headquarters Offut Air Force Base, Omaha |
| [12] | Wen, U. P.; Yang, Y. H., Algorithms for solving the mixed integer two-level linear programming problem, Computers Ops Res., 17, 133-142 (1990) · Zbl 0683.90055 |
| [13] | Falk, J. E., A linear max-min problem, Math. Orogram., 5, 169-188 (1973) · Zbl 0276.90053 |
| [14] | Gallo, G.; Ülkücü, A., Bilinear programming: an exact algorithm, Math. Program., 12, 173-194 (1977) · Zbl 0363.90086 |
| [15] | Wen, U. P., Mathematical methods for multilevel linear programming, (Ph.D. thesis (1981), State University of New York: State University of New York Buffalo) |
| [16] | Dantzig, G. B.; Wolfe, P., Decomposition principles for linear pgorams, Ops Res., 8, 101-111 (1960) · Zbl 0093.32806 |
| [17] | Baumol, W. J.; Fabian, T., Decomposition, pricing for decentralization and external economies, Mgmt Sci., 11, 1-32 (1964) |
| [18] | Hass, J. E., Transfer pricing in a decentralized firm, Mgmt Sci., 14, B310-B331 (1968) |
| [19] | Ruefli, T. W., Behavioral externalities in decentralized optimization, Mgmt Sci., 17, B649-B657 (1971) |
| [20] | Burton, R. M.; Obel, B., The multilevel approach to organizational issues of the firm: a critical review, OMEGA, Int. J. Mgmt Sci., 5, 395-414 (1977) |
| [21] | Glassey, C. R., Nested decomposition and multi-stage linear programs, Mgmt Sci., 20, 282-292 (1971) · Zbl 0313.90037 |
| [22] | Freeland, J. R.; Baker, N. R., Goal partitioning in a hierarchical organization, OMEGA, Int. J. Mgmt Sci., 3, 673-688 (1975) |
| [23] | Dirickx, Y. M.I.; Jennergren, L. P., Systems Analysis by Multilevel Methods: With Applications to Economics and Management (1979), Wiley: Wiley New York · Zbl 0517.90024 |
| [24] | Fortuny-Amat, J.; McCarl, B., A representation and economic interpretation of a two-level programming problem, J. Opnl Res. Soc., 32, 783-792 (1981) · Zbl 0459.90067 |
| [25] | Stackelberg, H. V., The Theory of the Market Economy (1952), Oxford University Press: Oxford University Press Oxford, (Original version appeared in 1934.) |
| [26] | Basar, T.; Olsder, G. J., Dynamic Noncooperative Game Theory (1982), Academic Press: Academic Press London · Zbl 0479.90085 |
| [27] | Simaan, M.; Cruz, J. B., On the Stackelberg strategy in nonzero-sum games, J. Optimiz. Theory Applic., 11, 544-555 (1973) · Zbl 0243.90056 |
| [28] | Basar, T.; Selbuz, H., Closed-loop Stackelberg strategies with applications in the optimal control of multilevel systems, IEEE Trans. Auto. Cont., AC-24, 166-179 (1979) · Zbl 0405.49020 |
| [29] | Papavassilopoulos, G. P.; Cruz, J. B., Non classical control problems and Stackelberg games, IEEE Trans. Auto. Cont., AC-24, 155-166 (1979) · Zbl 0406.49008 |
| [30] | Tolwinski, B., Closed-loop Stackelberg solution to multi-stage linear-quadratic game, J. Optimiz. Theory Applic., 34, 485-501 (1981) · Zbl 0431.90097 |
| [31] | Chang, T. S.; Luh, P. B., Derivation of necessary and sufficient conditions for single-stage Stackelberg games via the inducible region concept, IEEE Trans. Auto. Control, AC-29, 63-66 (1984) · Zbl 0536.90097 |
| [32] | Evans, J. P.; Steuer, R. E., A revised simplex method for linear multiple objective programs, Math. Program., 5, 54-72 (1973) · Zbl 0281.90045 |
| [33] | Rosinger, E. E., Aids for decision making with conflicting objectives, (Serafini, P., Mathematics of Multi-Objective Optimization (1985), Springer: Springer New York), 275-315 · Zbl 0503.90055 |
| [34] | Hartley, R., Linear multiple objective programming, (Serafini, P., Mathematics of Multi-Objective Optimization (1985), Springer: Springer New York), 157-177 |
| [35] | Jahn, J., Scalarization in multi objective optimization, (Serafini, P., Mathematics of Multi-Objective Optimization (1985), Springer: Springer New York), 45-88 |
| [36] | Wen, U. P.; Hsu, S. T., A note on a linear bilevel programming algorithm based on bicriteria programming, Computers Ops Res., 16, 79-83 (1989) · Zbl 0659.90080 |
| [37] | Ben-Ayed, O.; Blair, C. E., Computational difficulties of bilevel linear programming, Ops Res., 38, 556-560 (1990) · Zbl 0708.90052 |
| [38] | Cassidy, R. G.; Kirby, M. J.L.; Raike, W. M., Efficient distribution of resources through three-levels of government, Mgmt Sci., 17, B462-B473 (1971) |
| [39] | Bracken, J.; McGill, J. T., Mathematical programs with optimization problems in the constraints, Ops Res., 21, 37-45 (1973) · Zbl 0263.90029 |
| [40] | Bracken, J.; McGill, J. T., Defense applications of mathematical programs with optimization problems in the constraints, Ops Res., 22, 1086-1096 (1974) · Zbl 0292.90057 |
| [41] | Bracken, J.; McGill, J. T., A method for solving mathematical programs with nonlinear programs in the constraints, Ops Res., 22, 1097-1101 (1974) · Zbl 0294.90070 |
| [42] | Shere, K.; Wingate, J., Allocation of resources to offensive strategic weapon systems, Nav. Res. Logist. Q., 23, 85-93 (1976) · Zbl 0328.90086 |
| [43] | Falk, J. E., A nonconvex max-min problem, Nav. Res. Logist. Q., 24, 441-450 (1977) · Zbl 0379.90091 |
| [44] | Candler, W.; Norton, R., Multilevel programming and development policy, (World bank staff working paper 258 (1977), IBRD: IBRD Washington D.C) |
| [45] | DeSilva, A. H., Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of U.S. crude oil production, (D.Sci. thesis (1978), George Washington University: George Washington University Washington D.C) |
| [46] | Bialas, W. F.; Karwan, M. H.; Shaw, J. P., A parametric complementary pivot approach for two-level linear programming, (Research report No. 80-2. Operation Research Program (1980), Department of Industrial Engineering, State University of Buffalo) |
| [47] | Falk, J. E.; McCormick, G. P., Mathematical structure of the international coal trade model, U.S. Department of Energy report DOE/NBB-0025 (1982), Washington D.C. |
| [48] | Candler, W.; Townsley, R., Optimizing subsidy payments in linear programming, (IEEE Proc. Int. Conf. Cybern. Soc. (1985)), 930-934 |
| [49] | Anandalingam, G.; Apprey, V., Multi-level programming and conflict resolution, Europ. J. Ops Res., 51, 233-247 (1991) · Zbl 0743.90127 |
| [50] | Leblanc, L. J.; Boyce, D. E., A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows, Transport. Res., 20B, 259-265 (1986) |
| [51] | Marcotte, P., Network design problem with congestion effects: a case of bilevel programming, Math. Program., 34, 142-162 (1986) · Zbl 0604.90053 |
| [52] | Ben-Ayed, O., Bilevel linear programming: analysis and applications to the network design problem, (Ph.D. thesis (1988), Department of Business Administration, University of Illinois: Department of Business Administration, University of Illinois Urbana-Champaign) |
| [53] | Ben-Ayed, O.; Boyce, D. E.; Blair, C. E., A general bilevel linear programming formulation of the network design problem, Transport. Res., B22, 311-318 (1988) |
| [54] | Ben-Ayed, O., A bilevel linear programming model applied to the Tunisian inter-regional network design problem, Rev. Tunis. Écon. Gestion, 5, 235-279 (1990) |
| [55] | Ben-Ayed, O.; Blair, C. E.; Boyce, D. E.; Leblanc, L. J., Construction of a real world bilevel linear program of the highway network design problem, Ann. Ops Res., 34, 219-254 (1992) · Zbl 0729.91035 |
| [56] | Ben-Ayed, O.; Blair, C. E.; Boyce, D. E., Solving a highway network design problem formulated as a bilevel linear program, Rev. Tunis. Écon. Gestion, 7, 2 (1992) |
| [57] | Papavassilopoulos, G. P., Algorithms for static Stackelberg games with linear costs and polyhedra constraints, (Proc. 21st IEEE Conf. Decis. Contr., 2 and 3 (1982)), 647-652 |
| [58] | Bard, J. F.; Moore, J. T., A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Statist. Comput., 11, 281-292 (1990) · Zbl 0702.65060 |
| [59] | Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 382-398 (1959) · Zbl 0103.37603 |
| [60] | Schenk, G., A multilevel programming model for determining regional effluent charges, (M.S. thesis (1980), State University of New York: State University of New York N.Y) |
| [61] | Bard, J. F., An efficient point algorithm for a linear two-stage optimization problem, Ops Res., 31, 670-684 (1983) · Zbl 0525.90086 |
| [62] | Bard, J. F.; Falk, J. E., An explicit solution to the multi-level programming problem, Computers Ops Res., 9, 77-100 (1982) |
| [63] | Narula, S. C.; Nwosu, A. D., An algorithm to solve a two-level resource control pre-emptive hierarchical programming problem, (Serafini, P., Mathematics of Multi-Objective Optimization (1985), Springer: Springer New York), 353-373 |
| [64] | Ünlü, G., A linear bilevel programming algorithm based on bicriteria programming, Computers Ops Res., 14, 173-179 (1987) · Zbl 0626.90086 |
| [65] | Nwosu, A. D., Pre-emptive hierarchical programming problem: a decentralized decision model, (Ph.D. thesis (1983), Rensselaer Polytechnic Institute: Rensselaer Polytechnic Institute Troy, N.Y) |
| [66] | Narula, S. C.; Nwosu, A. D., Two-level hierarchical programming problem, (Hansen, P., Multiple Criteria Decision Making: Theory and Applications (1983), Springer: Springer New York), 290-299 · Zbl 0558.90056 |
| [67] | S. C. Narula, Personal correspondence (1987).; S. C. Narula, Personal correspondence (1987). |
| [68] | Júdice, J. J.; Faustino, A. M., The solution of the linear bilevel programming problem by using the linear complementary problem, Invest. Opnl, 8, 75-95 (1988) · Zbl 0647.90095 |
| [69] | Al-Khayyal, F. A., An implicit enumeration procedure for the general linear complementary problem, Math. Program. Stud., 39, 1-20 (1987) · Zbl 0623.90079 |
| [70] | Anandalingam, G.; White, D. J., A solution method for the linear Stackelberg problem, IEEE Trans. Auto. Contr., AC-35, 1170-1175 (1990) · Zbl 0721.90098 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
