Article ID: | iaor1998772 |
Country: | Netherlands |
Volume: | 79 |
Issue: | 1 |
Start Page Number: | 95 |
End Page Number: | 114 |
Publication Date: | Nov 1994 |
Journal: | European Journal of Operational Research |
Authors: | Corbern A., Sanchis J.M. |
Keywords: | networks: flow, programming: travelling salesman |
In this paper we study the polyhedron associated with the Rural Postman Problem (RPP). Because the RPP is NP-hard, we cannot expect to find a complete description of the rural postman polyhedron of a general graph, but a partial knowledge of such a description frequently proves to be useful for both theoretical and computational purposes. We have tried to characterize the facial structure of this unbounded full-dimensional polyhedron. Sets of valid inequalities inducing facets have been studied as well as their use in a cutting-plane algorithm. The application of this algorithm to a set of RPP instances taken from the literature and two instances of larger size taken from a real world graph is described. All these instances were solved to optimality.