$$n$$ n -Step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem Academic Article uri icon

abstract

  • © 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. In this paper, we introduce a generalization of the continuous mixing set, which we refer to as the continuous multi-mixing set. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We present a family of valid inequalities for the continuous multi-mixing set and identify conditions under which they are facet-defining. The cycle inequalities, $$n$$n-step MIR inequalities, and mixed $$n$$n-step MIR inequalities are special cases of these inequalities. We also present an exact separation algorithm for our inequalities. We then use these inequalities to generate valid inequalities for MML with(out) backlogging. Our computational results show that our cuts are very effective in solving the MML instances, resulting in substantial reduction in the integrality gap, number of nodes, and total solution time.

published proceedings

  • Mathematical Programming

author list (cited authors)

  • Bansal, M., & Kianfar, K.

citation count

  • 10

complete list of authors

  • Bansal, Manish||Kianfar, Kiavash

publication date

  • December 2015