A class of stochastic programs withdecision dependent random elements
Tóm tắt
In the “standard” formulation of a stochastic program with recourse, the distribution ofthe random parameters is independent of the decisions. When this is not the case, the problemis significantly more difficult to solve. This paper identifies a class of problems that are“manageable” and proposes an algorithmic procedure for solving problems of this type. Wegive bounds and algorithms for the case where the distributions and the variables controllinginformation discovery are discrete. Computational experience is reported.
Tài liệu tham khảo
Z. Artstein and R.J-B Wets, Sensors and information in optimization under stochastic uncertainty, Mathematics of Operations Research 28(1993)523 – 547.
I.L. Averbakh, An additive method for optimization of two-stage stochastic systems with discrete variables, Soviet Journal of Computer and System Sciences 28(1990)161 – 165.
J.R. Birge and R.J-B Wets, Computing bounds for stochastic programming problems by means of a generalized moment problem, Mathematics of Operations Research 12(1987)149 – 162.
S. Bjørnestad, Å. Hallefjord and K. Jörnsten, Discrete optimization under uncertainty: The scenario and policy aggregation technique, Working Paper 89/06, Chr. Michelsen Institute, Bergen, Norway, 1989.
H. Bjørstad, Å. Hallefjord and T. Hefting, Decision trees with coupling constraints, Report Ref. CMI-No.30151-2, Chr. Michelsen Institute, Bergen, Norway, 1988.
C.C. Carøe and R. Schultz, Dual decomposition in stochastic integer programming, Technical Report, Institute of Mathematics, Universitetsparken 5, DK-2100, Copenhagen, Denmark, 1996.
CPLEX Optimization, Inc., Using the CPLEX Callable Library, Suite 279, 930 Tahoe Blvd. Building 802, Incline Village, NV 89451-9436, 1994.
A. Gaivoronski, Linearization methods for optimization of functionals which depend on probability measures, Mathematical Programming Study 28(1986)157– 181.
A. Gaivoronski, Stochastic optimization techniques for finding optimal submeasures, in: Stochastic Optimization, eds. V.I. Arkin, A. Shiraev and R. Wets, Lecture Notes in Control and Information Sciences 81, Springer, 1986, pp. 351 – 363.
Y.-C. Ho and X.-R. Cao, Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academic, Boston, 1991.
S. Jorjani, C.H. Scott and D.L. Woodruff, Optimal selection of a subset of sizes, Working Paper, GSM, UC Davis, Davis, CA 95616, 1996.
G. Laporte and F.V. Louveaux, The integer L-shaped method for stochastic integer programs with complete recourse, OR Letters 13(1993)133–142.
A. Løkketangen and D.L. Woodruff, Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming, Journal of Heuristics 2(1996)111 – 128.
G.Ch. Pflug, On-line optimization of simulated Markovian processes, Mathematics of Operations Research 15(1990)381–395.
A. Prékopa, Stochastic Programming, Kluwer Academic, Dordrecht, 1995.
R.Y. Rubinstein and A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function, Wiley, New York, 1993.
R. Schultz, L. Stougie and M.H. van der Vlerk, Solving stochastic programs with complete integer recourse: A framework using Gröbner bases, Discussion Paper 9562, CORE, Louvain-la-Neuve, Belgium, 1995.
L. Stougie and M.H. van der Vlerk, Stochastic integer programming, in: Annotated Bibliographies in Combinatorial Optimization, eds. M. Dell'Amico, F. Maffioli and S. Martello, Wiley, 1997, chap. 9, pp. 127 – 141.
S. Takriti, J.R. Birge and E. Long, Lagrangian solution techniques and bounds for loosely-coupled mixed-integer stochastic programs, Technical Report, Department of IEOR, University of Michigan, Ann Arbor, MI, USA, 1994.
S.R. Tayur, R.R. Thomas and N.R. Natraj, An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands, Mathematical Programming 69(1995)369 – 401.