  


nstep cycle inequalities: facets for continuous nmixing set and strong cuts for multimodule capacitated lotsizing problem
Manish Bansal (bansalvt.edu) Abstract: In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous nmixing set). This set is closely related to the feasible set of the multimodule capacitated lotsizing (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 facetdefining for convex hull of this set. The cycle inequalities of Van Vyve (Math of OR 30:441452, 2005), the nstep MIR inequalities of Kianfar and Fathi (Math Progam 120:313346, 2009), and the mixed nstep MIR inequalities of Sanjeevi and Kianfar (Discrete Optimization 9:216235, 2012) form special cases of the nstep cycle inequalities. We also present a compact extended formulation for the continuous nmixing 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 2step (k,l,S,C) cycle cuts over 1step (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). Keywords: nstep cycle inequalities, nstep MIR, continuous nmixing, multimodule capacitated lotsizing with backlogging, mixed integer programming, cutting planes Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Category 3: Applications  OR and Management Sciences (Production and Logistics ) Citation: M. Bansal, K. Kianfar, "nstep cycle inequalities: facets for the continuous multimixing set and strong cuts for multimodule capacitated lotsizing problem," Mathematical Programming, 154 (1), 113144, 2015. Download: Entry Submitted: 07/02/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  