A branch-and-cut algorithm for the maximum benefit Chinese postman problem (Q378087): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: CPLEX / rank | |||
Normal rank |
Revision as of 07:12, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A branch-and-cut algorithm for the maximum benefit Chinese postman problem |
scientific article |
Statements
A branch-and-cut algorithm for the maximum benefit Chinese postman problem (English)
0 references
11 November 2013
0 references
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.
0 references
Chinese postman problem
0 references
maximum benefit Chinese postman problem
0 references
rural postman problem
0 references
facets
0 references
branch-and-cut
0 references