Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets

• 成果类型: Article
• 署名作者: Sanjeevi, Sujeevraja; Masihabadi, Sina; Kianfar, Kiavash
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0959-1
• 发表日期: 2016
• 页码: 571-583
• 关键词: inequalities facets

摘要

Based on a bijective mapping between two mixed integer sets, we introduce a new perspective on developing cuts for the mixed integer polyhedral conic (MIPC) set by establishing a one-to-one correspondence between the cuts for this set and those for a related mixed integer knapsack (MIK) set. The face/facet-defining properties of the corresponding cuts are identical for their respective sets. We further show that the cut generation approach for the MIPC set resulting from this new perspective always produces cuts that dominate those generated based on any of the two individual MIK constraints corresponding to the MIPC constraint. Our computational results show this dominance can be quite significant. As a special case of this new perspective, the conic MIR inequality of Atamturk and Narayanan for the MIPC set and its properties can be directly derived from the MIR inequality for the MIK set and its properties. We also generalize these cuts to the n-step conic MIR inequalities, which are directly derived form the n-step MIR inequalities for the MIK set.