A Study of the Lot-Sizing Polytope

Alper Atamturk (atamturkieor.berkeley.edu)
Juan Carlos Munoz (juancauclink4.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.

Keywords:

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

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

Download:

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

Modify/Update this entry