Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: zero setup case

Research output: Research - peer-reviewArticle

In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.
Original languageEnglish
Pages (from-to)86-95
Number of pages10
JournalEuropean Journal of Operational Research
Volume267
Issue number1
Early online date16 Nov 2017
DOIs
StatePublished - 16 May 2018

    Research areas

  • production, lot-sizing, integer programming, polyhedral analysis, valid inequalities

View graph of relations