Abstract
In this paper we consider heuristic algorithms for a special case of the generalized bilevel mathematical programming problem in which one of the levels is represented as a variational inequality problem. Such problems arise in network design and economic planning. We obtain derivative information needed to implement these algorithms for such bilevel problems from the theory of sensitivity analysis for variational inequalities. We provide computational results for several numerical examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Abdulaal and L.J. LeBlanc, “Continuous equilibrium network design models,”Transportation Research 13B (1979) 19–32.
D.P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,”SIAM J. Control and Optimization 20(2) (1982a) 221–246.
D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982b).
A.H. De Silva, “Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production,” Dissertation, George Washington University (Washington, D.C., 1978).
T.L. Friesz, T. Miller and R.L. Tobin, “Algorithms for spatially competitive network facility-location,”Environment and Planning B 15 (1988) 191–203.
P.T. Harker and J.-S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of the theory, algorithms and applications,”Mathematical Programming (Series B) 48 (1990) 161–220, this issue.
P.T. Harker and S.-C. Choi, “A penalty function approach for mathematical programs with variational inequality constraints,” Decision Science Working Paper 87-09-08, University of Pennsylvania (Philadelphia, PA, 1987).
J.M. Henderson and R.E. Quandt,Microeconomic Theory (McGraw-Hill, New York, 1980, 3rd ed.).
C.D. Kolstad, “A review of the literature on bi-level mathematical programming,” Los Alamos National Laboratory Report, LA-10284-MS (Los Alamos, 1985).
C.D. Kolstad and L.S. Lasdon, “Derivative evaluation and computational experience with large bi-level mathematical programs,” BEBR Faculty Working Paper No. 1266, University of Illinois (Urbana-Champaign, IL, 1986).
J. Kyparisis, “Sensitivity analysis framework for variational inequalities,”Mathematical Programming 38 (1987) 203–213.
J. Kyparisis, “Solution differentiability for variational inequalities and nonlinear programming problems,” Department of Decision Sciences and Information Systems, College of Business Administration, Florida International University (Miami, FL, 1989).
T.L. Magnanti and R.T. Wong, “Network design and transportation planning: models and algorithms,”Transportation Science 18(1) (1984) 1–55.
P. Marcotte, “Network design problem with congestion effects: a case of bilevel programming,”Mathematical Programming 34 (1986) 142–162.
J.-S. Pang, “Solution differentiability and continuation of Newton's method for variational inequality problems over polyhedral sets,” Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1988).
R.T. Rockafellar,The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions (Heldermann, Berlin, 1981).
C. Suwansirikul, T.L. Friesz and R.L. Tobin, “Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem,”Transportation Science 21(4) (1987) 254–263.
H.N. Tan, S.B. Gershwin and M. Athaus, “Hybrid optimization in urban traffic networks,” Report No. DOT-TSC-RSPA-79-7, Laboratory for Information and Decision System, M.I.T. (Cambridge, MA, 1979).
R.L. Tobin, “Sensitivity analysis for variational inequalities,”Journal of Optimization Theory and Applications 48 (1986) 191–204.
R.L. Tobin and T.L. Friesz, “Sensitivity analysis for equilibrium network flow,”Transportation Science 22(4) (1988) 242–250.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Friesz, T.L., Tobin, R.L., Cho, HJ. et al. Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Mathematical Programming 48, 265–284 (1990). https://doi.org/10.1007/BF01582259
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582259