A polyhedral approach to the rural postman problem

A polyhedral approach to the rural postman problem

0.00 Avg rating0 Votes
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: ,
Keywords: networks: flow, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.