A branch-and-cut algorithm for the maximum benefit Chinese postman problem (Q378087)

This article studies a variation of the undirected Chinese Postman Problem which considers several benefits associated with each edge. The objective function of the problem is to find a closed walk which maximize the total benefit. The article begins with an overview of the literature associated with this problem and the mathematical formulation of the maximum benefit Chinese postman problem which is in the form of an integer program. The authors then study the associated polyhedron defined by the inequalities and several types of valid inequalities are derived and proven. A branch-and-cut algorithm is then described and the separation algorithms for the proposed cuts are provided. The article concludes with the results of the numerical experimentation which was performed using the CPLEX optimizer on test instances generated by the authors.