×

Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty. (English) Zbl 1163.90034

This paper deals with the expected residual minimization (ERM) formulation for the stochastic nonlinear complementarity problem (SNCP). The solution set of ERM formulation for the SNCP is studied in this paper. The authors define stochastic \(R_{0}\) function and show that the involved function is a stochastic \(R_{0}\) function if and only if the objective function in the ERM formulation is coercive under a mild assumption. Finally, the traffic equilibrium problem (TEP) under uncertainty is modeled as SNCP and it is shown that the objective function in the ERM formulation is a stochastic \(R_{0}\) function. See also [X. Chen and M. Fukushima, Math. Oper. Res. 30, No. 4, 1022–1038 (2005; Zbl 1162.90527)] and [G. Gürkan, A. Y. Özge and S. M. Robinson, Math. Program. 84, No. 2 (A), 313–333 (1999; Zbl 0972.90079)]. Numerical experimental results of the ERM formulation and the Expected Value (EV) formulation for TEP under uncertainty are also reported.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C15 Stochastic programming
90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
[2] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problem, I and II. Springer, New York (2003) · Zbl 1062.90002
[3] Lin, G.H., Fukushima, M.: New reformulations for stochastic nonlinear complementarity problems. Optim. Methods Softw. 21, 551–564 (2006) · Zbl 1113.90110 · doi:10.1080/10556780600627610
[4] Chen, X., Fukushima, M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022–1038 (2005) · Zbl 1162.90527 · doi:10.1287/moor.1050.0160
[5] Chen, X., Zhang, C., Fukushima, M.: Robust solution of monotone stochastic linear complementarity problems. Math. Program. (2007) online · Zbl 1165.90012
[6] Fang, H., Chen, X., Fukushima, M.: Stochastic R 0 matrix linear complementarity problems. SIAM J. Optim. 18, 482–506 (2007) · Zbl 1151.90052 · doi:10.1137/050630805
[7] Gürkan, G., Özge, A.Y., Robinson, S.M.: Sample-path solution of stochastic variational inequalities. Math. Program. 84, 313–333 (1999) · Zbl 0972.90079 · doi:10.1007/s101070050024
[8] Tseng, P.: Growth behavior of a class of merit functions for the nonlinear complementarity problem. J. Optim. Theory Appl. 89, 17–37 (1996) · Zbl 0866.90127 · doi:10.1007/BF02192639
[9] Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. ICE Part II 1, 325–378 (1952)
[10] Aashtiant, H.Z., Magnanti, T.L.: Equilibria on a congested transportation network. SIAM J. Algebr. Discrete Methods 2, 213–226 (1981) · Zbl 0501.90033 · doi:10.1137/0602024
[11] Daffermos, S.: Traffic equilibrium and variational inequalities. Transp. Sci. 14, 42–54 (1980) · doi:10.1287/trsc.14.1.42
[12] Fukushima, M.: The primal Douglas-Rachford splitting algorithm for a class of monotone mapping with application to the traffic equilibrium problem. Math. Program. 72, 1–15 (1996) · Zbl 0851.90138
[13] Fernando, O., Nichlàs, E.S.: Robust Wardrop equilibrium. Technical Report (2006). See website http://illposed.usc.edu./\(\sim\)fordon/docs/rwe.pdf · Zbl 1181.91045
[14] Ruszcynski, A., Shapiro, A. (eds.): Stochastic Programming. Handbooks in OR & MS, vol. 10. North-Holland, Amsterdam (2003)
[15] Lin, G.H., Chen, X., Fukushima, M.: New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC. Optimization 15, 641–653 (2007) · Zbl 1172.90455 · doi:10.1080/02331930701617320
[16] Chen, B.: Error bounds for R 0-type and monotone nonlinear complementarity problems. J. Optim. Theory Appl. 108, 297–316 (2001) · Zbl 1041.90055 · doi:10.1023/A:1026434200384
[17] Chung, K.L.: A Course in Probability Theory, 2nd edn. Academic Press, New York (1974) · Zbl 0345.60003
[18] Patriksson, M.: Traffic Assignment Problems–Models and Methods. VSP, Utrecht (1994) · Zbl 0828.90127
[19] Gabriel, S.A., Bernstein, D.: The traffic equilibrium problem with nonadditive path costs. Trans. Sci. 31, 337–348 (1997) · Zbl 0920.90058 · doi:10.1287/trsc.31.4.337
[20] Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, New York (1994)
[21] Jahn, O., Möhring, R.H., Schulz, A.S., Stier-Moses, N.E.: System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53, 600–616 (2005) · Zbl 1165.90499 · doi:10.1287/opre.1040.0197
[22] Yin, Y.F., Madanat, S.M., Lu, X.Y., Kuhn, K.D.: Robust improvement schemes for road networks under demand uncertainty. In: Proceedings of TRB 84th Annual Meeting, Washington (2005)
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.