New facets for the set packing polytope

DOI10.1016/S0167-6377(00)00056-0zbMath1096.90548OpenAlexW1986218927MaRDI QIDQ5929145

Alfredo Marín, Lázaro Cánovas, Mercedes Landete

Publication date: 2000

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(00)00056-0

zbMATH Keywords

Discrete locationFacetsPackingPolyhedral combinatoric

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (17)

New formulations for the uncapacitated multiple allocation hub location problem ⋮ Solving the set packing problem via a maximum weighted independent set heuristic ⋮ New facets for the two-stage uncapacitated facility location polytope ⋮ Alternative formulations for the set packing problem and their application to the winner determination problem ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ New variants of the simple plant location problem and applications ⋮ The rank pricing problem: models and branch-and-cut algorithms ⋮ Adding incompatibilities to the simple plant location problem: formulation, facets and computational experience ⋮ New valid inequalities and facets for the simple plant location problem ⋮ Adapting polyhedral properties from facility to hub location problems ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ A polyhedral study on 0-1 knapsack problems with set packing constraints ⋮ A fast approximation algorithm for solving the complete set packing problem ⋮ A new lifting theorem for vertex packing ⋮ On the facets of the simple plant location packing polytope ⋮ Dynamic node packing

Cites Work

• A class of facet producing graphs for vertex packing polyhedra
• Wheel inequalities for stable set polytopes
• On certain polytopes associated with graphs
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• Some facets of the simple plant location polytope
• Technical Note—A Note on Zero-One Programming
• Further facet generating procedures for vertex packing polytopes
• Compositions of Graphs and Polyhedra II: Stable Sets
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• Facet Obtaining Procedures for Set Packing Problems
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• Unnamed Item
• Unnamed Item

This page was built for publication: New facets for the set packing polytope