Title of article :
Dual Heuristics on the Exact Solution of Large Steiner Problems
Author/Authors :
de Aragمo، نويسنده , , Marcus Poggi and Uchoa، نويسنده , , Eduardo and Werneck، نويسنده , , Renato F.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2001
Pages :
4
From page :
150
To page :
153
Abstract :
We present dual heuristics for the directed cut formulation of the Steiner problem in graphs. These heuristics usually give tight lower and upper bounds, and are enough to quickly solve two thirds of the instances from the literature. For harder instances, we propose two exact algorithms using those heuristics: branch-and-ascent, an implicit enumeration without LP solving; and a branch-and-cut that starts from bases provided by dual heuristics, which may be called afterwards to improve convergence. These algorithms have a good practical performance and solved several open instances, including the 1320 series and very large and degenerated problems from VLSI layout.
Keywords :
dual ascent , branch-and-ascent , Branch-and-cut , Steiner problem , VLSI layout
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2001
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1453127
Link To Document :
بازگشت