An efficient primal simplex implementation for the continuous 2-matching problem

Abstract

The continuous 2-matching problem {RMP2) is the relaxation of the symmetric travelling salesman problem {STSP) used by Padberg & Rinaldi to develop a highly successful branch-and-cut algorithm for the STSP. They used a standard linear program solver for solving RM P2. We note that RM P2 is a generalized network problem with additional special structure and exploit this to provide an efficient implementation of the primal simplex algorithm for RM P2. Our computational experience with the implementation demonstrates that it is several or­ders of magnitude faster than a standard linear program solver, suggesting that it should be worthwhile using this implementation in the Padberg-Rinaldi algorithm.