In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n'-step cycle inequalities, n' = 1,..., n, and show that in many cases they are facet-defining for convex hull of this set. The cycle inequalities of Van Vyve (Math of OR 30:441-452, 2005), the n-step MIR inequalities of Kianfar and Fathi (Math Progam 120:313-346, 2009), and the mixed n-step MIR inequalities of Sanjeevi and Kianfar (Discrete Optimization 9:216-235, 2012) form special cases of the n-step cycle inequalities. We also present a compact extended formulation for the continuous n-mixing set and an exact separation algorithm over the set of all n'-step cycle inequalities for any given n'. We then use these inequalities to generate valid inequalities for the MML problem with(out) backlogging, referred to as the n'-step (k,l,S,C) cycle inequalities for n'=1,…,n. Our computational results show that our cuts are very effective in solving the MML instances with(out) backlogging with two capacity modules (n=2), resulting in substantial reduction in the integrality gap (86% in average) and number of nodes (81 times in average). Also, the total time (which also includes the cut generation time) taken to solve an instance is in average 34 times smaller than the time taken by CPLEX with default settings (except for very easy instances). More interestingly, in these instances adding 2-step (k,l,S,C) cycle cuts over 1-step (k,l,S,C) cycle cuts has improved the closed gap (15% in average), the number of nodes (29 times in average), and the total solution time (11 times in average).
Citation
M. Bansal, K. Kianfar, "n-step cycle inequalities: facets for the continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem," Mathematical Programming, 154 (1), 113-144, 2015.