Artículos de revistas
An exact approach to the problem of extracting an embedded network matrix
Registro en:
Computers & Operations Research. Pergamon-elsevier Science Ltd, v. 38, n. 11, n. 1483, n. 1492, 2011.
0305-0548
WOS:000289604700003
10.1016/j.cor.2011.01.003
Autor
Figueiredo, RMV
Labbe, M
de Souza, CC
Institución
Resumen
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) We study the problem of detecting a maximum embedded network submatrix in a (-1,0,+1)-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear programming formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an optimal solution to the problem. Some computational experiments are carried out over a set of instances available in the literature as well as over a set of random instances. (C) 2011 Elsevier Ltd. All rights reserved. 38 11 1483 1492 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) CNPq [301732/2007-8, 473867/2010-9]