On the complete set packing and set partitioning polytopes: Properties and rank 1 facets |
| |
| Authors: | Teobaldo Bulhões Artur Pessoa Fábio Protti Eduardo Uchoa |
| |
| Institution: | 1. Universidade Federal da Paraíba—Departamento de Computação Científica, Brazil;2. Universidade Federal Fluminense—Departamento de Engenharia de Produção, Brazil;3. Universidade Federal Fluminense—Instituto de Computação, Brazil |
| |
| Abstract: | This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary -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. |
| |
| Keywords: | Set packing Set partitioning Polyhedral combinatorics Rank 1 cuts Facets |
| 本文献已被 ScienceDirect 等数据库收录！ |
