Dynamic Slope Scaling Procedure for Stochastic Integer Programming Problem

Mathematical programming has been applied to various problems. For many actual problems, the assumption that the parameters involved are deterministic known data is often unjustified. In such cases, these data contain uncertainty and are thus represented as random variables, since they represent information about the future. Decision-making under uncertainty involves potential risk. Stochastic programming is a commonly used method for optimization under uncertainty. A stochastic programming problem with recourse is referred to as a two-stage stochastic problem. In this study, we consider a stochastic programming problem with simple integer recourse in which the value of the recourse variable is restricted to a multiple of a nonnegative integer. The algorithm of a dynamic slope scaling procedure for solving this problem is developed by using a property of the expected recourse function. Numerical experiments demonstrate that the proposed algorithm is quite efficient. The stochastic programming model defined in this paper is quite useful for a variety of design and operational problems.

Authors:

• Takayuki Shiina

Keywords:

• stochastic programming problem with recourse
• simple integer recourse
• dynamic slope scaling procedure

References:

[1] S. Ahmed, M. Tawarmalani, and N. V. Sahinidis, A finite branch-andbound
algorithm for two-stage stochastic integer programs, Mathematical
Programming, Vol. 100, pp.355-377, 2005.
[2] J. F. Benders, Partitioning procedures for solving mixed variables programming
problems. Numerische Mathematik, 4(1962), 238-252.
[3] J. R. Birge, Stochastic programming computation and applications. INFORMS
Journal on Computing, Vol. 9, pp. 111-133, 1997.
[4] J. R. Birge and F. V. Louveaux, Introduction to Stochastic Programming,
Springer-Verlag, 1997.
[5] P. Kall and S.W. Wallace, Stochastic Programming, John Wiley & Sons,
1994.
[6] D. Kim and P. Pardalos, A solution approach to fixed charge network flow
problem useing a dynamic slope scaling procedure, Operations Research
Letters, Vol. 24, pp.195-203, 1999.
[7] D. Kim and P. Pardalos, A dynamic domain constraction algorithm for
nonconvex piecewise linear network flow problems, Journal of Global
optimization, Vol. 17, pp.225-234, 2000.
[8] G. Laporte and F. V. Louveaux: The integer L-shaped method for
stochastic integer programs with complete recourse. Operations Research
Letters, 13(1993) 133-142.
[9] F. V. Louveaux and M. H. van der Vlerk, Stochastic programming with
simple integer recourse, Mathematical Programming, Vol. 61, pp. 301-
325, 1993.
[10] F. V. Louveaux and R. Schulz, Stochastic integer programming, in
Stochastic Programming (Handbooks in Operations Research and management
Science, A. Ruszczy'nski and A. Shapiro, eds.), Elsevier, pp.
213-266, 2003.
[11] T. Shiina: L-shaped decomposition method for multi-stage stochastic
concentrator location problem. Journal of the Operations Research Society
of Japan, 43(2000) 317-332.
[12] T. Shiina: Stochastic programming model for the design of computer
network (in Japanese). Transactions of the Japan Society for Industrial
and Applied Mathematics, 10(2000) 37-50.
[13] R. Van Slyke and R. J.-B. Wets: L-shaped linear programs with applications
to optimal control and stochastic linear programs. SIAM Journal
on Applied Mathematics, 17(1969) 638-663.