Groupe d’études et de recherche en analyse des décisions


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 properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported.

, 20 pages

Ce cahier a été révisé en août 1999