A branch-and-cut algorithm for the Undirected Rural Postman Problem

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral prope rties are investigated and a branch-and-cut algorithm is developed. Extensi ve computational results indicate that the algorithm is capable of solving much larger instances than previously reported.