Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481538 | European Journal of Operational Research | 2009 | 5 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Bruno Bachelet, Christophe Duhamel,