Optimization Online


A Study of the Lot-Sizing Polytope

Alper Atamturk (atamturk***at***ieor.berkeley.edu)
Juan Carlos Munoz (juanca***at***uclink4.berkeley.edu)

Abstract: The lot-sizing polytope is a fundamental structure contained in many practical production planning problems. Here we study this polytope and identify facet-defining inequalities that cut off all fractional extreme points of its linear programming relaxation, as well as liftings from those facets. We give a polynomial-time combinatorial separation algorithm for the inequalities when capacities are constant. We also report on an extensive computational study on solving the lot-sizing problem for instances up to 365 time periods with varying cost and capacity characteristics.


Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Citation: Mathematical Programming 99, 443-465, 2004.


Entry Submitted: 02/27/2003
Entry Accepted: 02/27/2003
Entry Last Modified: 03/01/2005

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