Median Cycle Problem
In the Median Cycle Problem the aim is to determine a simple cycle
containing a subset of vertices of a graph, while considering two
types of cost: routing costs associated with the cycle itself,
and the cost of assigning vertices not on the cycle to
vertices of the cycle.
Two versions of the problem are investigated. In the first, the
objective function is the sum of routing and assignment costs. In the second,
routing costs are minimized, subject to an upper bound on the total
assignment cost.
The two versions are formulated as integer linear programs.
The polyhedral structure of the first model is analyzed and the
second model is strengthened through the introduction of additional
valid inequalities. Separation procedures are developed. Heuristic
procedures and an exact branch-and-cut algorithm are described.
Computational results on benchmark instances and on randomly
generated problems confirm the efficiency of the proposed algorithms.
My contributions with M. Labbé, G. Laporte and I. Rodríguez are:
The Median Cycle Problem,
working paper University of Montreal, may 1999.