A cutting plane algorithm for minimum perfect 2-matchings

DOI10.1007/BF02239975zbMath0617.05053MaRDI QIDQ1821798

Martin Grötschel, Olaf Holland

Publication date: 1987

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

polyhedral combinatorics; cutting plane algorithm; minimum weight perfect 2-matching problem; perfect 2-matching polytope

Mathematics Subject Classification ID

90C10: Integer programming

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

05C45: Eulerian and Hamiltonian graphs

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

Classical cuts for mixed-integer programming and branch-and-cut, Solution of large-scale symmetric travelling salesman problems, Facet identification for the symmetric traveling salesman polytope, Undirected postman problems with zigzagging option: a cutting-plane approach, Exploiting planarity in separation routines for the symmetric traveling salesman problem, A polynomial-time solution to Papadimitriou and Steiglitz's ``traps, Euclidean semi-matchings of random samples, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies

Cites Work

• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• A primal simplex variant for the maximum-flow problem
• Solving matching problems with linear programming
• Multi-Terminal Network Flows
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Odd Minimum Cut-Sets and b-Matchings
• Maximum matching and a polyhedron with 0,1-vertices