{"title":"Dynamic Slope Scaling Procedure for Stochastic Integer Programming Problem","authors":"Takayuki Shiina","volume":65,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":525,"pagesEnd":531,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/7142","abstract":"Mathematical programming has been applied to various\nproblems. For many actual problems, the assumption that the parameters\ninvolved are deterministic known data is often unjustified. In\nsuch cases, these data contain uncertainty and are thus represented\nas random variables, since they represent information about the\nfuture. Decision-making under uncertainty involves potential risk.\nStochastic programming is a commonly used method for optimization\nunder uncertainty. A stochastic programming problem with recourse\nis referred to as a two-stage stochastic problem. In this study, we\nconsider a stochastic programming problem with simple integer\nrecourse in which the value of the recourse variable is restricted to a\nmultiple of a nonnegative integer. The algorithm of a dynamic slope\nscaling procedure for solving this problem is developed by using a\nproperty of the expected recourse function. Numerical experiments\ndemonstrate that the proposed algorithm is quite efficient. The\nstochastic programming model defined in this paper is quite useful\nfor a variety of design and operational problems.","references":"[1] S. Ahmed, M. Tawarmalani, and N. V. Sahinidis, A finite branch-andbound\nalgorithm for two-stage stochastic integer programs, Mathematical\nProgramming, Vol. 100, pp.355-377, 2005.\n[2] J. F. Benders, Partitioning procedures for solving mixed variables programming\nproblems. Numerische Mathematik, 4(1962), 238-252.\n[3] J. R. Birge, Stochastic programming computation and applications. INFORMS\nJournal on Computing, Vol. 9, pp. 111-133, 1997.\n[4] J. R. Birge and F. V. Louveaux, Introduction to Stochastic Programming,\nSpringer-Verlag, 1997.\n[5] P. Kall and S.W. Wallace, Stochastic Programming, John Wiley & Sons,\n1994.\n[6] D. Kim and P. Pardalos, A solution approach to fixed charge network flow\nproblem useing a dynamic slope scaling procedure, Operations Research\nLetters, Vol. 24, pp.195-203, 1999.\n[7] D. Kim and P. Pardalos, A dynamic domain constraction algorithm for\nnonconvex piecewise linear network flow problems, Journal of Global\noptimization, Vol. 17, pp.225-234, 2000.\n[8] G. Laporte and F. V. Louveaux: The integer L-shaped method for\nstochastic integer programs with complete recourse. Operations Research\nLetters, 13(1993) 133-142.\n[9] F. V. Louveaux and M. H. van der Vlerk, Stochastic programming with\nsimple integer recourse, Mathematical Programming, Vol. 61, pp. 301-\n325, 1993.\n[10] F. V. Louveaux and R. Schulz, Stochastic integer programming, in\nStochastic Programming (Handbooks in Operations Research and management\nScience, A. Ruszczy'nski and A. Shapiro, eds.), Elsevier, pp.\n213-266, 2003.\n[11] T. Shiina: L-shaped decomposition method for multi-stage stochastic\nconcentrator location problem. Journal of the Operations Research Society\nof Japan, 43(2000) 317-332.\n[12] T. Shiina: Stochastic programming model for the design of computer\nnetwork (in Japanese). Transactions of the Japan Society for Industrial\nand Applied Mathematics, 10(2000) 37-50.\n[13] R. Van Slyke and R. J.-B. Wets: L-shaped linear programs with applications\nto optimal control and stochastic linear programs. SIAM Journal\non Applied Mathematics, 17(1969) 638-663.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 65, 2012"}