The postman problem requires finding a lowest cost tour in a connected
graph that traverses each edge at least once. In this paper we first
give a brief survey of the literature on postman problems including, t
he original Chinese postman problem on undirected graphs, the windy Ch
inese postman problem on graphs where the cost of an are depends on th
e direction the are is transversed, the directed postman problem on gr
aphs with directed edges, and the mixed postman problem on graphs in w
hich there are some directed and some undirected arcs. We show how the
mixed postman problem can be solved as an integer program, using the
formulation of Gendreau, Laporte and Zhao, by a new row addition branc
h and bound algorithm, which is a modification of the column subtracti
on algorithm for set partitioning problems of Harche and Thompson. Com
putational experience shows that a ''slack variable'' heuristic is ver
y effective in finding good solutions that are frequently optimal for
these problems.