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

abstract

  • In this paper, we introduce a generalization of the well-known continuous mixing set (which we refer to as the continuous n-mixing set) Qm,n := {(y, v, s) ε (Z × Z+n-1)m × R+m+1 :∑ t=1n α ty ti + vi + 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) backlogging. 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. © 2014 Springer International Publishing Switzerland.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Bansal, M., & Kianfar, K.

citation count

  • 5

complete list of authors

  • Bansal, Manish||Kianfar, Kiavash

editor list (cited editors)

  • Lee, J., & Vygen, J..

publication date

  • January 2014