Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming |
| |
Authors: | Suvrajeet Sen Hanif D Sherali |
| |
Institution: | (1) Department of System and Industrial Engineering, University of Arizona, PO Box 210020, Tucson, AZ 85721, USA;(2) Grado Department of ISE, Virginia Polytechnic Institute and State University Blacksburg, VA 24061, USA |
| |
Abstract: | Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those
arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been
applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies
on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which
the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s)
is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the
second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition
scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller
MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage
stochastic mixed-integer programs. |
| |
Keywords: | Stochastic Programming Decomposition Branch-and-Cut Mixed-Integer Programming |
本文献已被 SpringerLink 等数据库收录! |
|