n-Step Cycle Inequalities: Facets for Continuous n-Mixing Set and Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem

摘要

In this paper, we introduce a generalization of the well-known continuous mixing set (which we refer to as the continuous n-mixing set) Q~(m,n):= {(y,v,s) ∈ (Z × Z_+~(n-1))~m × R_+~(m+1) : ∑_(t=1)~n α_ty_t~i+ v_i + s ≥ β_i, i = 1,...,m}. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlog-ging. For each n'∈ {1,...,n}, we develop a class of valid inequalities for this set, referred to as the n'-step cycle inequalities, and show that they are facet-defining for conv(Q~(m,n)) in many cases. We also present a compact extended formulation for Q~(m,n) and an exact separation algorithm for the n'-step cycle inequalities. We then use these inequalities to generate valid inequalities for the MML problem with(out) backlogging. Our computational results show that our cuts are very effective in solving the MML instances with backlogging, resulting in substantial reduction in the integrality gap, number of nodes, and total solution time.