In this paper, we investigate the two-period subproblems proposed by Akartunal{\i} et al. (2014) for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds for these problems. In particular, we study the polyhedral structure of the mixed integer sets related to two relaxations of these subproblems for the special case of zero setup times, derive several families of valid inequalities and present their facet-defining conditions. Then we discuss the separation problems associated with these valid inequalities and propose exact separation algorithms. Finally, we investigate the computational strength of these cuts when they are integrated into a cutting plane framework. Our computational experiments indicate they can be indeed very effective improving lower bounds substantially.
Citation
Published as: Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case. European Journal of Operational Research 267(1):86-95, 2018. The final publication is available as Open Access at Science Direct via doi:10.1016/j.ejor.2017.11.014