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

Doostmohammadi, Mahdi and Akartunali, Kerem (2018) Valid inequalities for two-period relaxations of big-bucket lot-sizing problems : zero setup case. European Journal of Operational Research, 267 (1). pp. 86-95. ISSN 0377-2217 (https://doi.org/10.1016/j.ejor.2017.11.014)

[thumbnail of Doostmohammadi-Akartunali-EJOR-2017-Valid-inequalities-for-two-period-relaxations-of-big-bucket]
Preview
 Text. Filename: Doostmohammadi_Akartunali_EJOR_2017_Valid_inequalities_for_two_period_relaxations_of_big_bucket.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (465kB)| Preview

Abstract

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.

ORCID iDs

Doostmohammadi, Mahdi ORCID logoORCID: https://orcid.org/0000-0002-6865-8058 and Akartunali, Kerem ORCID logoORCID: https://orcid.org/0000-0003-0169-3833;
CORE (COnnecting REpositories)