Preprocessing Steiner problems from VLSI layout

VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely to reduce, significantly, such VLSI i...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2002-08, Vol.40 (1), p.38-50
Main Authors: Uchoa, Eduardo, Poggi de Aragão, Marcus, Ribeiro, Celso C.
Format: Article
Language:English
Subjects:
Applied sciences
branch and cut
combinatorial preprocessing
Exact sciences and technology
Flows in networks. Combinatorial problems
instance reduction
integer programming
Operational research and scientific management
Operational research. Management science
Steiner problem
VLSI problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely to reduce, significantly, such VLSI instances. We propose a new preprocessing procedure, extending earlier ideas from the literature and improving their application, so as to make them effective for VLSI problems. We report significant reductions within reasonable computational times, obtained with the application of this procedure to 116 instances of the SteinLib. These reductions allowed a branch and cut to solve 28 of 32 open instances of the SteinLib, some with more than 10,000 vertices and 20,000 edges. © 2002 Wiley Periodicals, Inc.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.10035