Partial objective inequalities for the multi-item capacitated lot-sizing problem

Esra Büyüktahtakın, J. Cole Smith, Joseph C. Hartman

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

In this paper, we study a mixed-integer programming model of the single-level multi-item capacitated lot-sizing problem (MCLSP), which incorporates shared capacity on the production of items for each period throughout a planning horizon. We derive valid bounds on the partial objective function of the MCLSP formulation by solving the first t periods of the problem over a subset of all items, using dynamic programming and integer programming techniques. We also develop algorithms for strengthening these valid inequalities by back-lifting techniques. These inequalities can be utilized within a cutting-plane algorithm, in which we perturb the partial objective function coefficients to identify violated inequalities to the MCLSP polytope. Our computational results show that the envelope inequalities are very effective for the MCLSP instances with different capacity and cost characteristics, when compared to the (l, S) inequalities.

Original languageEnglish (US)
Pages (from-to)132-144
Number of pages13
JournalComputers and Operations Research
Volume91
DOIs
StatePublished - Mar 2018
Externally publishedYes

Keywords

  • (l, S) inequalities
  • Branch-and-cut
  • Capacitated lot-sizing
  • Cutting planes
  • Dynamic programming
  • Mixed-integer programming
  • Multi-item
  • Partial objective cuts
  • Polyhedral study
  • Production planning
  • Valid inequalities

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Partial objective inequalities for the multi-item capacitated lot-sizing problem'. Together they form a unique fingerprint.

  • Cite this