A polyhedral study of the generalized vertex packing problem

DOI10.1007/S10107-004-0504-0MaRDI QIDQ2492699zbMATH OpenOpenAlexFDO

Authors Hanif D. Sherali, J. Cole Smith

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

air-space managementinteger programmingreformulation-linearization techniquevalid inequalities/cutting planesvertex packing

Mathematics Subject Classification ID

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

Recommendations

• A class of web-based facets for the generalized vertex packing problem
• The mixed vertex packing problem.
• scientific article; zbMATH DE number 754942
• Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
• Relaxations of vertex packing

Cites work

• A branch and bound algorithm for the maximum clique problem
• 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
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An Airspace Planning Model for Selecting Flight-plans Under Workload, Safety, and Equity Considerations
• Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems
• Further facet generating procedures for vertex packing polytopes
• scientific article; zbMATH DE number 47262 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• National airspace sector occupancy and conflict analysis models for evaluating scenarios under the free-flight paradigm
• On certain polytopes associated with graphs
• On the integer-valued variables in the linear vertex packing problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Properties of vertex packing and independence system polyhedra
• Relaxations of vertex packing
• Vertex packings: Structural properties and algorithms

Cited in

(14)

• Relaxations of vertex packing
• A decomposition of 2-weak vertex-packing polytopes
• A polyhedral view to generalized multiple domination and limited packing
• 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
• Continuous cubic formulations for cluster detection problems in networks
• scientific article; zbMATH DE number 3943843 (Why is no real title available?)
• scientific article; zbMATH DE number 1960287 (Why is no real title available?)
• A polyhedral study of the maximum edge subgraph problem
• The mixed vertex packing problem.
• On maximum ratio clique relaxations
• An implicit enumeration approach for maximum ratio clique relaxations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2492699)