Optimization Online


The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity

Mariana Escalante (mariana***at***fceia.unr.edu.ar)
Javier Marenco (jmarenco***at***ungs.edu.ar)
María del Carmen Varaldo (mvaraldo***at***fceia.unr.edu.ar)

Abstract: In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard (discrete) start-up considered in previous models, thus motivating a polyhedral study of this problem. In this work we explore a natural integer programming formulation for this problem. We state some general properties, study the facetness properties of the model constraints, and present an exponentially-sized family of valid inequalities. We analyze the structure of the extreme points of the convex hull of its feasible region, their adjacency and bounds for the polytope diameter. Finally, we study the particular case when the demands are high enough in order to require production in all the periods. We provide a complete description of the convex hull of feasible solutions in this case and show that all the inequalities in this description are separable in polynomial time, thus proving its polynomial time solvability.

Keywords: lot-sizing, continuous start-up, polyhedral combinatorics

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

Citation: Annals of Operations Research, in press


Entry Submitted: 10/03/2014
Entry Accepted: 10/03/2014
Entry Last Modified: 06/03/2015

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 Optimization Society