An exact approach to the problem of extracting an embedded network matrix

被引：8
作者：
Figueiredo, Rosa M. V. [1 ,2 ]
Labbe, Martine [3 ]
de Souza, Cid C. [4 ]
机构：
[1] Univ Aveiro, Dept Math, P-3810193 Aveiro, Portugal
[2] Univ Estado Rio De Janeiro, Inst Math & Stat, BR-20550900 Rio De Janeiro, Brazil
[3] Univ Libre Bruxelles, Dept Comp Sci, B-1050 Brussels, Belgium
[4] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP, Brazil
来源：
COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 11期
关键词：
Network matrix; Signed graph; Facets of polyhedra; Branch-and-cut; LINEAR-PROGRAMS; SIGNED GRAPHS; ALGORITHM; POLYTOPE; PACKING; ROWS;
D O I：
10.1016/j.cor.2011.01.003
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
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.
引用
收藏
页码：1483 / 1492
页数：10
相关论文
共 17 条
12