Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets Academic Article uri icon

abstract

  • © 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. 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 Atamtürk 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.

published proceedings

  • Mathematical Programming

author list (cited authors)

  • Sanjeevi, S., Masihabadi, S., & Kianfar, K.

citation count

  • 2

complete list of authors

  • Sanjeevi, Sujeevraja||Masihabadi, Sina||Kianfar, Kiavash

publication date

  • September 2016