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

Matching; Polyhedral combinatorics; procedures; Covering; Sequential tightening

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

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

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?