Aggregation approach for the minimum binary cost tension problem |
| |
Authors: | Bruno Bachelet Christophe Duhamel |
| |
Affiliation: | LIMOS, UMR 6158-CNRS, Université Blaise Pascal, BP 10125, 63173 Aubière, France |
| |
Abstract: | The aggregation technique, dedicated to two-terminal series–parallel graphs (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 (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 (MIP), proposed to solve exactly the BCT problem on TTSP-graphs. A comparison of the efficiency of both methods and a heuristic is presented. |
| |
Keywords: | Minimum cost tension Binary costs Two-terminal series&ndash parallel graphs |
本文献已被 ScienceDirect 等数据库收录! |
|