Optimization Online


Ancestral Benders' Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming

Yunwei Qi (qi.47***at***osu.edu)
Suvrajeet Sen (s.sen***at***usc.edu)

Abstract: This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second stage mixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders'-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as in many decomposition schemes, these subproblems can be solved in parallel. We also illustrate these algorithms using several variants of an SMIP example from the literature, and present preliminary evidence of the scalability of these algorithms as the number of scenarios increases.

Keywords: Two-stage Stochastic Mixed Integer Programs, Benders' Decomposition, Multi-term Disjunctive Cuts

Category 1: Stochastic Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Tech. Report, Daniel J. Epstein Dept. of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089

Download: [PDF]

Entry Submitted: 09/03/2013
Entry Accepted: 09/03/2013
Entry Last Modified: 08/30/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society