Linear programming relaxations of the mixed postman problem
Francisco Javier Zaragoza Mart · 2005
The mixed postman problem consists ofnding 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 lin- ear programming relaxations of two well-known integer program- ming formulations of this problem are equivalent. We also give some properties of the extreme points of the polyhedra dened by one of these relaxations and its linear programming dual.