Optimization Online


On Solving General Two-Stage Stochastic Programs

Manish Bansal (manish.bansal***at***northwestern.edu)
Sanjay Mehrotra (mehrotra***at***northwestern.edu)

Abstract: We study general two-stage stochastic programs and present conditions under which the second stage programs can be convexified. This allows us to relax the restrictions, such as integrality, binary, semi-continuity, and many others, on the second stage variables in certain situations. Next, we introduce two-stage stochastic disjunctive programs (TSS-DPs) and extend Balas's linear programming equivalent for deterministic disjunctive programs to TSS-DPs. In addition, we develop a finitely convergent algorithm, which utilizes the sequential convexification approach of Balas within L-shaped method, to solve various classes of TSS-DPs. We formulate a semi-continuous program (SCP) as a DP and use our results for TSS-DPs to solve two-stage stochastic SCPs (TSS-SCPs). In particular, we provide linear programming equivalent for the second stage of the TSS-SCPs and showcase how our convexification approach can be utilized to solve a TSS-SCP having semi-continuous inflow set in the second stage.

Keywords: two-stage stochastic program; tight formulations; disjunctive programs; sequential convexification; semi-continuous programs; lift-and-project; cutting planes; convex hull

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report MBSM1, Department of Industrial Engineering & Management Sciences, Northwestern University, October 2015


Entry Submitted: 10/15/2015
Entry Accepted: 10/15/2015
Entry Last Modified: 02/15/2016

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