A branch-and-cut algorithm for the maximum benefit Chinese postman problem (Q378087): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Angel Corberán / rank | |||
Normal rank | |||
Property / author | |||
Property / author: José María Sanchis / rank | |||
Normal rank |
Revision as of 20:31, 10 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