Aggregation Approach for the Minimum
Binary Cost Tension Problem
 
 
Bruno Bachelet
(LIMOS, Clermont-Ferrand, France)
 
Research Report LIMOS/RR04-08
Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
Université Blaise Pascal
Clermont-Ferrand, France
February 22, 2004
 

The aggregation technique, dedicated to two-terminal series-parallel graphs (or TTSP-graphs) and introduced lately to solve the minimum piecewise linear cost tension problem, is adapted here to solve the minimum binary cost tension problem (or BCT problem). Even on TTSP-graphs, the BCT problem has been proved to be NP-complete. As far as we know, the aggregation is the only algorithm, with mixed integer programming, proposed to solve exactly the BCT problem on TTSP-graphs. A comparison of the efficiency of both methods is presented here.

You can download the of the BCT problem that have been used for the numerical results of this article.