A faster exact separation algorithm for blossom inequalities

DOI10.1007/978-3-540-25960-2_15MaRDI QIDQ5712453zbMATH OpenOpenAlexFDO

Authors Adam N. Letchford, Dirk Oliver Theis, Gerhard Reinelt

Publication date 23 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b97946

zbMATH Keywords

matchingpolyhedraseparation

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Odd Minimum Cut Sets and b-Matchings Revisited
• A Separation Algorithm for b-Matching Degree-Sequence Polyhedra
• A separation algorithm for the matchable set polytope
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• A polynomial algorithm for b-matchings: An alternative approach

Cited in

(25)

• Solving the prize-collecting rural postman problem
• A separation algorithm for the matchable set polytope
• Primal separation for 0/1 polytopes
• The separation problem of rounded capacity inequalities: some polynomial cases
• The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm
• OAR lib: an open source arc routing library
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• Exact and heuristic algorithms for capacitated vehicle routing problems with quadratic costs structure
• Engineering branch-and-cut algorithms for the equicut problem
• A branch-and-cut framework for the consistent traveling salesman problem
• A branch-and-cut algorithm for the profitable windy rural postman problem
• scientific article; zbMATH DE number 2119756 (Why is no real title available?)
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Constraint relaxation for the discrete ordered median problem
• The biobjective minimum-cost perfect matching problem and Chinese postman problem
• Branch-and-cut algorithms for the traveling salesman problem with job times
• An exact algorithm for the adjacent vertex distinguishing sum edge coloring problem
• Non delayed relax-and-cut algorithms
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Optimizing over the first Chvátal closure
• Two blossoming proofs of the Lane-Riesenfeld algorithm
• Undirected postman problems with zigzagging option: a cutting-plane approach
• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• Faster algorithms for computing Hong's bound on absolute positiveness

This page was built for publication: A faster exact separation algorithm for blossom inequalities

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