Optimization Online


Computations with Disjunctive Cuts for Two-Stage Stochastic Mixed Integer Programs

Lewis Ntaimo (ntaimo***at***tamu.edu)
Matthew Tanner (mtanner***at***tamu.edu)

Abstract: Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.

Keywords: stochastic programming; integer

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Submitted to the Journal of Global Optimization (2007)

Download: [PDF]

Entry Submitted: 05/15/2007
Entry Accepted: 05/16/2007
Entry Last Modified: 05/24/2008

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 Programming Society