A Branch-and-Cut Algorithm for the Stochastic Uncapacitated Lot-Sizing Problem

Yongpei Guan (guanypisye.gatech.edu)
Shabbir Ahmed (sahmedisye.gatech.edu)
George L. Nemhauser (nemhausisye.gatech.edu)

Abstract: This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l,S) inequalities to a general class of valid inequalities, called the (Q,S_Q) inequalities, and we establish necessary and sufficient conditions which guarantee that the (Q,S_Q) inequalities are facet-defining. A separation heuristic for (Q,S_Q) inequalities is developed and incorporated into a branch and cut algorithm. A computational study verifies the usefulness of the (Q,S_Q) inequalities as cuts.

Keywords: Stochastic Lot-Sizing -- Multi-stage Stochastic Integer Programming -- Polyhedral Study -- Branch and Cut

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Stochastic Programming

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

Citation: Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, 2004.

Download: [PDF]

Entry Submitted: 01/22/2004
Entry Accepted: 01/22/2004
Entry Last Modified: 02/09/2004

Modify/Update this entry