Linear programming relaxations of the mixed postman problem
Francisco Javier Zaragoza Martínez

The mixed postman problem consists of finding a minimum cost tour of a connected mixed graph traversing all its vertices, edges, and arcs at least once. We prove in two different ways that the linear programming relaxations of two well-known integer programming formulations of this problem are equivalent. We also give some properties of the extreme points of the polyhedra defined by one of these relaxations and its linear programming dual.

[Regresar / Back]