Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543746 | Operations Research Letters | 2018 | 4 Pages |
Abstract
This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary n-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Teobaldo Bulhões, Artur Pessoa, Fábio Protti, Eduardo Uchoa,