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

Abstract

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computationalstudy of a disjunctive cutting plane method for stochastic mixed 0-1 programsthat uses lift-and-project cuts based on the extensive form of the two-stage SMIPproblem. An extension of the method based on where the data uncertainty appearsin the problem is made, and it is shown how a valid inequality derived for onescenario can be made valid for other scenarios, potentially reducing solution time.Computational results amply demonstrate the effectiveness of disjunctive cuts insolving several large-scale problem instances from the literature. The results arecompared to the computational results of disjunctive cuts based on the subproblemspace of the formulation and it is shown that the two methods are equivalentlyeffective on the test instances.