-Step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem

• 成果类型: Article
• 署名作者: Bansal, Manish; Kianfar, Kiavash
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0906-1
• 发表日期: 2015
• 页码: 113-144
• 关键词: negative-cycle

摘要

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, -step MIR inequalities, and mixed -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.