| Article ID: | iaor1995325 |
| Country: | Netherlands |
| Volume: | 14 |
| Issue: | 3 |
| Start Page Number: | 123 |
| End Page Number: | 127 |
| Publication Date: | Oct 1993 |
| Journal: | Operations Research Letters |
| Authors: | Ralphs T.K. |
| Keywords: | postman problem |
The mixed Chinese postman problem is a version of the well-known Chinese postman problem in which the underlying graph consists of both directed and undirected edges. The paper gives an integer linear programming formulation for this problem and then shows that the extreme points of its linear relaxation polyhedron are all half-integral.