Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets
Academic Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- Other
-
- View All
-
Overview
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
author list (cited authors)
-
Sanjeevi, S., Masihabadi, S., & Kianfar, K.
citation count
complete list of authors
-
Sanjeevi, Sujeevraja||Masihabadi, Sina||Kianfar, Kiavash
publication date
publisher
published in
Research
keywords
-
Cutting Plane
-
Facet
-
Mixed Integer Cone Programming
-
Mixed Integer Knapsack Set
-
N-step Conic Mir
-
Polyhedral Conic Set
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue
Other