Solving Stochastic Mathematical Programs with Complementarity Constraints Using Simulation
Authors:
- 1 November 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 31 (4) , 739-760
Abstract
We consider stochastic mathematical programs with complementarity constraints in which both the objective and constraints involve limit functions that need to be approximated. Such programs can be used for modeling “average” (expected) or steady-state behavior of complex stochastic systems. We first describe these stochastic mathematical programs with complementarity constraints and compare them with different stochastic mathematical programs with equilibrium constraints from the literature. This explicit discussion may facilitate selecting an appropriate stochastic model. We then describe a simulation-based method called sample-path optimization for solving these problems and provide sufficient conditions under which appropriate approximating problems will have solutions converging to a solution of the original problem almost surely. We illustrate an application on toll pricing in transportation networks. We explain how uncertainty can be incorporated and the approximating problems are solved using an off-the-shelf solver. These developments enable solving certain stochastic bilevel optimization problems and Stackelberg games using simulation.Keywords
This publication has 30 references indexed in Scilit:
- Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimization2005
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002
- Generalized semi-infinite programming: Theory and methodsEuropean Journal of Operational Research, 1999
- Stochastic mathematical programs with equilibrium constraintsOperations Research Letters, 1999
- Sample-path solution of stochastic variational inequalitiesMathematical Programming, 1999
- Engineering and Economic Applications of Complementarity ProblemsSIAM Review, 1997
- Chapter 6 Network equilibrium models and algorithms1995
- Generalized equations and their solutions, Part I: Basic theory1979
- CORRESPONDENCE. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952
- ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952