TITRE : On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation

CONFÉRENCIÈRE : Elena Fernandez, Universitat Politècnica de Catalunya, Barcelone, Espagne

DATE et ENDROIT : 25 septembre 2002, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE : Gilbert Laporte (343-6143)

RÉSUMÉ : The Rural Postman Problem (RPP) is a classic ``edge-routing'' problem. A mathematical programming formulation of the RPP that differs fundamentally from those in the literature was introduced, but not tested computationally, by Garfinkel and Webb (1999). A rudimentary algorithm that yields lower bounds via cutting planes and upper bounds via heuristics is developed and tested for a variation of that formulation. Computational results are encouraging, especially in terms of the relatively small number of added inequalities needed to get good lower bounds, and the fact that the vast majority of these have efficient, exact separation procedures. Of particular note is that a first algorithm based on this new formulation is computationally competitive, allowing the possibility of far more efficient and complex future realizations.