Lift and project relaxations for the matching and related polytopes

DOI10.1016/S0166-218X(03)00337-8zbMath1032.05106MaRDI QIDQ1421469

Graciela L. Nasini, Silvia M. Bianchi, Néstor E. Aguilera

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

MatchingPolyhedral combinatoricsproceduresCoveringSequential tightening

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (8)

Integrality gaps for colorful matchings ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ On the commutativity of antiblocker diagrams under lift-and-project operators ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ Unnamed Item

Cites Work

• Unnamed Item
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On a Representation of the Matching Polytope Via Semidefinite Liftings
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Maximum matching and a polyhedron with 0,1-vertices
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

This page was built for publication: Lift and project relaxations for the matching and related polytopes