Title: A branch-and-cut algorithm for two-stage stochastic mixed-binary programs with continuous first-stage variables

Authors: Lewis Ntaimo, Suvrajeet Sen

Addresses: Department of Industrial and Systems Engineering, Texas A&M University, 3131 TAMU, College Station, TX 77843, USA. ' Department of Systems and Industrial Engineering, The University of Arizona, P.O. Box 210020, Tucson, Arizona 85721, USA

Abstract: This paper presents a branch-and-cut method for two stage Stochastic Mixed-Integer Programming (SMIP) problems with continuous first-stage variables. This method is derived based on disjunctive decomposition (D2) for SMIP, an approach in which disjunctive programming is used to derive valid inequalities for SMIP. The novelty of the proposed method derives from branching on the first-stage continuous domain while the branch-and-bound process is guided by the disjunction variables in the second-stage. Finite convergence of the algorithm for mixed-binary second stage is established and a numerical example to illustrate the new method is given.

Keywords: stochastic programming; disjunctive decomposition; branch-and-bound; branch-and-cut; mixed-binary programs; first-stage variables; mixed-integer programming; SMIP; MIP.

DOI: 10.1504/IJCSE.2007.017829

International Journal of Computational Science and Engineering, 2007 Vol.3 No.3, pp.232 - 241

Published online: 18 Apr 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article