A staged primal–dual algorithm for perfect b-matching with edge capacities

We describe an algorithm for finding a minimum cost perfect b-matching in a weighted undirected graph G = (V, E), with arbitrary edge capacities. The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. The most significant step involves a primal–dual tree growth procedure that selectively activates and deactivates facet inducing blossom constraints. The algorithm progressively eliminates half-integral values from the primal solution without creating any new fractional values. We introduce the concept of frozen supervertices to address previously unknown complications that arise due to the presence of non-unit capacity edges. We discuss the relationship of the algorithm to previously published cutting plane methods. The algorithm is guaranteed to terminate in O(|V|²|E|) steps, although computational results suggest that much less effort is typically required. Computational results show the algorithm to be effective on problems derived from TSPLIB ranging in size from 532 to 3795 vertices for various b values.