Hierarchical optimization: An introduction. (English) Zbl 0751.90067

Anandalingam, G.; Friesz, T. L.

Ann. Oper. Res. 34, 1-11 (1992).

Summary: Decision problems involving multiple agents invariably lead to conflict and gaming. In recent years, multi-agent systems have been analyzed using approaches that explicitly assign to each agent a unique objective function and set of decision variables; the system is defined by a set of common constraints that affects all agents. The decisions made by each agent in these approaches affect the decisions made by the others and their objectives. When strategies are selected simultaneously, in a noncooperative manner, solutions are defined as equilibrium points, so that at optimality no player can do better by unilaterally altering his choice. There are other types of noncooperative decision problems, though, where there is a hierarchical ordering of the agents, and one set has the authority to strongly influence the preferences of the other agents. Such situations are analyzed using a concept known as a Stackelberg strategy. The hierarchical optimization problem conceptually extends the open-loop Stackelberg model to \(K\) players. In this paper, we provide a brief introduction and survey of recent work in the literature, and summarize the contributions of this volume. It should be noted that the survey is not meant to be exhaustive, but rather to place recent papers in context.

MSC:

90C30	Nonlinear programming
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
91A65	Hierarchical games (including Stackelberg games)
93A13	Hierarchical systems

Keywords:

hierarchical optimization; open-loop Stackelberg model

References:

[1]	M. Abdulaal and L.J. LeBlanc, Continuous equilibrium network design models, Transport. Res. 13B(1979)19–32. · Zbl 0398.90042
[2]	E. Aiyoshi and K. Shimizu, A solution method of the static constrained Stackelberg problem via penalty method, IEEE Trans. Auto. Control AC-29(1984)1111–1114. · Zbl 0553.90104
[3]	G. Anandalingam, A mathematical programming model of decentralized multi-level systems, J. Oper. Res. Soc. 39(1988)1021–1033. · Zbl 0657.90061
[4]	G. Anandalingam, R. Mathieu, L. Pittard and N. Sinha, Artificial intelligence based approaches for hierarchical optimization problems, in:Impact of Recent Computer Advances on Operations Research, ed. R. Sharda et al. (North-Holland, New York, 1983).
[5]	G. Anandalingam and D.J. White, A solution method for the linear static Stackelberg problem using penalty functions, IEEE Trans. Auto. Control AC-35(1990)1170–1173. · Zbl 0721.90098
[6]	G. Anandalingam and V. Aprey, Multi-level programming and conflict resolution, Eur. J. Oper. Res. 51(1991)233–247. · Zbl 0743.90127
[7]	J.F. Bard, An efficient point algorithm for a linear two-stage optimization problem, Oper. Res. 31(1983)670–684. · Zbl 0525.90086
[8]	J.F. Bard, Coordination of multidivisional firm through two levels of management, OMEGA 11(1983)457–465.
[9]	J.F. Bard, Regulating nonnuclear industrial waste by hazard classification, J. Environ. Syst. 13(1983/84)21–41.
[10]	J.F. Bard, Convex two-level optimization, Math. Progr. 40(1988)15–27. · Zbl 0655.90060
[11]	J.F. Bard and J.E. Falk, An explicit solution to the multi-level programming problem, Comput. Oper. Res. 9(1982)77–100.
[12]	J.F. Bard and J.J. Moore, A branch-and-bound algorithm for the two-level linear programming problem, SIAM J. Sci. Statist. Comput. 11(1990)281–292. · Zbl 0702.65060
[13]	T. Basar and G.J. Olsder,Dynamic Noncooperative Games (Academic Press, New York, 1982). · Zbl 0479.90085
[14]	T. Basar and H. Selbuz, Closed loop Stackelberg strategies with applications to optimal control of multi-level systems, IEEE Trans. Auto. Control AC-24(1979)166–178. · Zbl 0405.49020
[15]	O. Ben-Ayed and C.E. Blair, Computational difficulties of bilevel linear programming, Oper. Res. 38(1990)556–559. · Zbl 0708.90052
[16]	W.F. Bialas and M.H. Karwan, On two-level optimization, IEEE Trans. Auto. Control AC-27(1982)211–214. · Zbl 0487.90005
[17]	W.F. Bialas and M.H. Karwan, Two-level linear programming, Manag. Sci. 30(1984)1004–1020. · Zbl 0559.90053
[18]	J. Bracken and J.M. McGill, Mathematical programs with optimization problems in the constraints, Oper. Res. 21(1973)37–44. · Zbl 0263.90029
[19]	J. Bracken and J.M. McGill, A method for solving mathematical programs with nonlinear programs in the constraints, Oper. Res. 22(1974)1097–1101. · Zbl 0294.90070
[20]	J. Bracken, J.E. Falk and J.M. McGill, Equivalence of two mathematical programs with optimization problems in the constraints, Oper. Res. 22(1974)1102–1104. · Zbl 0294.90071
[21]	J. Bracken and J.M. McGill, Defense applications of mathematical programs with optimization problems in the constraints, Oper. Res. 22(1974)1086–1096. · Zbl 0292.90057
[22]	J. Bracken and J.M. McGill, Production and marketing decisions with multiple objectives in a competitive environment, J. Optim. Theory Appl. 24(1978)449–458. · Zbl 0351.90001
[23]	W. Candler and R. Townsley, A linear two-level programming problem, Comput. Oper. Res. 9(1982)59–76.
[24]	A.H. deSilva, Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production, D.Sc. Dissertation, George Washington University, Washington, DC (1978).
[25]	J.E. Falk, A linear min-max problem, Math. Progr. 8(1973)169–188. · Zbl 0276.90053
[26]	A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968). · Zbl 0193.18805
[27]	C.S. Fisk, A conceptual framework for optimal transportation systems planning with integrated supply and demand models, Transport. Sci. 20(1986)37–47.
[28]	J. Fortuny-Amat and B. McCarl, A representative and economic interpretation of a two-level programming problem, J. Oper. Res. Soc. 20(1981)783–792. · Zbl 0459.90067
[29]	T.L. Friesz, Transportation network equilibrium, design and aggregation, Transport. Res. 19A(1985)413–427.
[30]	T.L. Friesz and P.T. Harker, Multicriteria spatial price equilibrium network design: Theory and computational results, Transport. Res. 17B(1983)203–217.
[31]	T.L. Friesz, T. Miller and R.L. Tobin, Algorithms for spatially competitive network-facility location, Environ. Planning 15B(1988). · Zbl 0751.90045
[32]	T.L. Friesz, R.L. Tobin and T. Miller, Theory and algorithms for equilibrium network facility location, Environ. Planning 15B(1988)191–203.
[33]	T.L. Friesz, R.L. Tobin, H.J. Cho and N.J. Mehta, Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints, Math. Progr. 48B(1990)265–284. · Zbl 0723.90070
[34]	T.L. Friesz, H.J. Cho, N. Mehta, R. Tobin and G. Anandalingam, A simulated annealing approach to the network design problem with variational inequality constraints, Transport. Sci. (1991), in press. · Zbl 0764.90084
[35]	T.L. Friesz, G. Anandalingam, N.J. Mehta, K. Nam, S.J. Shah and R.L. Tobin, The multiobjective equilibrium network design problem revisited: A simulated annealing approach, Eur. J. Oper. Res (1991), to appear. · Zbl 0772.90043
[36]	T.L. Friesz and P. Harker, Multicriteria spatial price equilibrium network design: Theory and computational results, Transport. Res. 17B(1983)411–426.
[37]	G. Gallo and A. Ulkucu, Bi-linear programming: An exact algorithm, Math. Progr. 12(1977)173–194. · Zbl 0363.90086
[38]	A. Haurie, G. Savard and D.J. White, A note on: An efficient point algorithm for a linear two-stage optimization problem, Oper. Res. 38(1990)553–555. · Zbl 0708.90051
[39]	P.T. Harker and T.L. Friesz, Bounding the solution of the continuous equilibrium net design problem,Proc. 9th Int. Symp. on Transportation and Traffic Theory (VNU Science Press, 1984), pp. 233–252.
[40]	C.D. Kolstad and L.S. Lasdon, Derivative evaluation and computational experience with large bilevel mathematical programs, Faculty Working Paper No 1266, Bureau of Economic and Business Research, University of Illinois, Urbana-Champaign (1986). · Zbl 0676.90101
[41]	H. Konno, A cutting plane algorithm for solving bilinear programs, Math. Progr. 11(1976)14–27. · Zbl 0353.90069
[42]	C.F. Lemke, A survey of complementarity theory, in:Variational Inequalities and Complementarity Problems, ed. R.W. Cottle et al. (Wiley, New York, 1980).
[43]	L.J. LeBlanc, An algorithm for the discrete network design problem, Transport. Sci. 9(1975)183–199.
[44]	P. Marcotte, Network optimization with continuous control parameters, Transport. Sci. 17(1983)181–197.
[45]	P. Marcotte, Network design problem with congestion effects: A case of bilevel programming. Math. Progr. 34(1986)142–162. · Zbl 0604.90053
[46]	M. Simaan and J.B. Cruz, Jr., On the Stackelberg strategy in nonzero-sum games, J. Optim. Theory Appl. 11(1973)533–555. · Zbl 0255.90082
[47]	C. Suwansirikul, T.L. Friesz and R.L. Tobin, Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem, Transport. Sci. 21(1987)254–263. · Zbl 0638.90097
[48]	C. Suwansirikul and T.L. Friesz, A heuristic algorithm for continuous equilibrium network design: Equilibrium decomposed optimization, Transport. Sci. 24(1987)254–263. · Zbl 0638.90097
[49]	R.L. Tobin and T.L. Friesz, A new look at spatially competitive facility location models,Lecture Notes in Economics and Mathematical Systems, Vol. 249 (Springer, 1985), pp. 1–19.
[50]	R.L. Tobin and T.L. Friesz, Spatial competition facility location models, Ann. Oper. Res. 6(1986)49–74.
[51]	W.L. Zangwill and C.B. Garcia, Equilibrium programming: Path following approach and dynamics, Math. Progr. 21(1981)262–289. · Zbl 0476.90078
[52]	Aoki and Satoh, Economic dispatch with network security constraints using parametric quadratic programming, IEEE Trans. Power Apparatus and Systems, PAS-101(1982)4548–4556.
[53]	Burton and Obel, The multi-level approach to organizational issues of the firm – a critical review, Omega 5(1977)395–414.
[54]	R. Cassidy, M.J. Kirby and W.M. Raike, Efficient distribution of resources through three levels of government, Manag. Sci. 17(1971)462–473.