On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables |
| |
Authors: | Hanif D Sherali Xiaomei Zhu |
| |
Affiliation: | (1) Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, 24061, VA, USA |
| |
Abstract: | In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders'
decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the
first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution
space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization
Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems
by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular
partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over
a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable
solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions.
We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are
presented to demonstrate the efficacy of this approach. |
| |
Keywords: | Two-stage stochastic mixed-integer programs Benders' decomposition Convexification Reformulation-Linearization Technique (RLT) |
本文献已被 SpringerLink 等数据库收录! |