We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal–dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V|2|E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problems ranging in size from 17 to 11,849 vertices.
