Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/72643
Type: Artigo de periódico
Title: The vertex separator problem: algorithms and computations
Author: de Souza, C
Balas, E
Abstract: This is a companion paper to our polyhedral study [1] of the Vertex Separator (VS) Problem. Given an undirected graph G, the VS problem consists in identifying a minimum-weight vertex set whose removal disconnects G, subject to bounds on the size of the resulting components. In this paper, we describe versions of a branch-and-cut algorithm based on the results of that polyhedral study. It uses two families of cuts, symmetric and asymmetric, for which we develop polynomial-time greedy separation routines. A heuristic to generate feasible separators is also used. A computational experiment on several data sets from the literature compares the performance of three versions of our algorithm to that of the commercial MIP solver XPRESS. This experiment throws a sharp light on the role of cut density, known to software developers but never before documented in the literature. It convincingly shows that the practical usefulness of cuts in integer programming depends not only on their strength, but also on their sparsity: everything else being equal, the smaller the cut support, the better. The power of the inequalities proposed here is well illustrated by the computational tests on dense graphs. This is in accordance with the previous observation, since the support of these cuts tends to decrease with graph density.
Country: EUA
Editor: Springer
Rights: fechado
Identifier DOI: 10.1007/s10107-005-0573-8
Date Issue: 2005
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000229940200010.pdf249.63 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.