Optimization Online


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

Yongpei Guan (guanyp***at***isye.gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
George L. Nemhauser (nemhaus***at***isye.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

  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