A polyhedral study of the generalized vertex packing problem

DOI10.1007/s10107-004-0504-0zbMath1134.90038OpenAlexW1965348797MaRDI QIDQ2492699

J. Cole Smith, Hanif D. Sherali

Publication date: 14 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-004-0504-0

zbMATH Keywords

integer programmingreformulation-linearization techniquevertex packingair-space managementvalid inequalities/cutting planes

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Combinatorial optimization (90C27)

Related Items

On maximum ratio clique relaxations ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ A class of web-based facets for the generalized vertex packing problem ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ Continuous cubic formulations for cluster detection problems in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Relaxations of vertex packing
• A class of facet producing graphs for vertex packing polyhedra
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• On certain polytopes associated with graphs
• Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems
• National Airspace Sector Occupancy and Conflict Analysis Models for Evaluating Scenarios under the Free-Flight Paradigm
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Vertex packings: Structural properties and algorithms
• Further facet generating procedures for vertex packing polytopes
• On the integer-valued variables in the linear vertex packing problem
• An Airspace Planning Model for Selecting Flight-plans Under Workload, Safety, and Equity Considerations
• Properties of vertex packing and independence system polyhedra
• A branch and bound algorithm for the maximum clique problem

This page was built for publication: A polyhedral study of the generalized vertex packing problem