Paper Info
Title
On the complete set packing and set partitioning polytopes: Properties and rank 1 facets.
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.
Year
DOI
Venue
2018
10.1016/j.orl.2018.04.006
Operations Research Letters
Keywords
Field
DocType
Set packing,Set partitioning,Polyhedral combinatorics,Rank 1 cuts,Facets
Vehicle routing problem,Combinatorics,Clique,Row vector,Polytope,Set packing,Mathematics,Binary number
Journal
Volume
Issue
ISSN
46
4
0167-6377
Citations 
PageRank 
References 
0
0.34
18
Authors
4
Name
Order
Citations
PageRank
Teobaldo Bulhões100.34
Artur Alves Pessoa227024.30
Fábio Protti335746.14
Eduardo Uchoa489151.71