Dynamic Slope Scaling Procedure for Stochastic Integer Programming Problem

Authors: Takayuki Shiina

Abstract:

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.

Keywords: stochastic programming problem with recourse, simple integer recourse, dynamic slope scaling procedure

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333262

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.