Paper Info
Title
Aggregation approach for the minimum binary cost tension problem
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.
Year
DOI
Venue
2009
10.1016/j.ejor.2008.07.033
European Journal of Operational Research
Keywords
Field
DocType
Minimum cost tension,Binary costs,Two-terminal series–parallel graphs
Graph,Mathematical optimization,NP-complete,Heuristic,Integer programming,Piecewise linear function,Mathematics,Agrégation,Piecewise linearization,Binary number
Journal
Volume
Issue
ISSN
197
2
0377-2217
Citations 
PageRank 
References 
2
0.40
8
Authors
2
Name
Order
Citations
PageRank
Bruno Bachelet1305.74
Christophe Duhamel225820.12