A polyhedral study of the generalized vertex packing problem

DOI10.1007/s10107-004-0504-0zbMath1134.90038MaRDI 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 programming; reformulation-linearization technique; vertex packing; air-space management; valid inequalities/cutting planes

Mathematics Subject Classification ID

90B50: Management decision making, including multiple objectives

90C27: Combinatorial optimization

Related Items

A polyhedral study of the maximum edge subgraph problem, A branch-and-price-and-cut method for computing an optimal bramble, A class of web-based facets for the generalized vertex packing problem

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