Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs Akbalik, A.; Pochet, Y.

User activity

Share to:
View the summary of this work
Akbalik, A. ; Pochet, Y.
Appears In
European Journal of Operational Research
Algorithms; Business, general; Business, international
Academic; Trade
To link to full-text access for this article, visit this link: Byline: A. Akbalik, Y. Pochet Keywords: Integer programming; Single-item capacitated lot sizing problem; Flow cover inequalities; Cutting plane algorithm Abstract: This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods. Author Affiliation: CORE, Universite Catholique de Louvain, 34 Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium Article History: Received 7 November 2007; Accepted 29 August 2008
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users