A graph G = (V, E) with its edges labeled in the set {+,-} is called a signed graph. It is balanced if its set of vertices V can be partitioned into two sets V1 and V2, such that all positive edges connect nodes within V1 or V2, and all negative edges connect nodes between V1 and V2. The maximum balanced subgraph problem (MBSP) for a signed graph is the problem of finding a balanced subgraph with the maximum number of vertices. In this work, we present the first polynomial integer linear programming formulation for this problem and a matheuristic to obtain good quality solutions in a short time. The results obtained for different sets of instances show the effectiveness of the matheuristic, optimally solving several instances and finding better results than the exact method in a much shorter computational time.
Keywords: Balanced signed graph, local search, matheuristic
@article{RO_2021__55_5_3121_0,
author = {Moreno Ram{\'\i}rez, Jorge Reynaldo and de Menezes Frota, Yuri Abitbol and de Lima Martins, Simone},
title = {A matheuristic approach for the maximum balanced subgraph of a signed graph},
journal = {RAIRO. Operations Research},
pages = {3121--3140},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {5},
doi = {10.1051/ro/2021150},
mrnumber = {4328500},
zbl = {1485.90116},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021150/}
}
TY - JOUR AU - Moreno Ramírez, Jorge Reynaldo AU - de Menezes Frota, Yuri Abitbol AU - de Lima Martins, Simone TI - A matheuristic approach for the maximum balanced subgraph of a signed graph JO - RAIRO. Operations Research PY - 2021 SP - 3121 EP - 3140 VL - 55 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021150/ DO - 10.1051/ro/2021150 LA - en ID - RO_2021__55_5_3121_0 ER -
%0 Journal Article %A Moreno Ramírez, Jorge Reynaldo %A de Menezes Frota, Yuri Abitbol %A de Lima Martins, Simone %T A matheuristic approach for the maximum balanced subgraph of a signed graph %J RAIRO. Operations Research %D 2021 %P 3121-3140 %V 55 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021150/ %R 10.1051/ro/2021150 %G en %F RO_2021__55_5_3121_0
Moreno Ramírez, Jorge Reynaldo; de Menezes Frota, Yuri Abitbol; de Lima Martins, Simone. A matheuristic approach for the maximum balanced subgraph of a signed graph. RAIRO. Operations Research, Tome 55 (2021) no. 5, pp. 3121-3140. doi: 10.1051/ro/2021150
[1] , and , Ttt plots: a perl program to create time-to-target plots. Optim. Lett. 1 (2007) 355–366. | MR | Zbl | DOI
[2] and , Facets of the balanced (acyclic) induced subgraph polytope. Math. Program. 45 (1989) 21–33. | MR | Zbl | DOI
[3] , , and , F-race and iterated f-race: An overview. In: Experimental methods for the analysis of optimization algorithms. Springer (2010) 311–336. | Zbl | DOI
[4] and , Structural balance: a generalization of heider’s theory. Psychol. Rev. 63 (1956) 277. | DOI
[5] , , and , Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. Biosystems 90 (2006) 161–178. | DOI
[6] , and , Minereduce: an approach based on data mining for problem size reduction. Comput. Oper. Res. 122 (2020) 104995. | MR | Zbl | DOI
[7] and , Parallel matheuristics for the discrete unit commitment problem with minstop ramping constraints. Int. Trans. Oper. Res. 27 (2020) 219–244. | MR | Zbl | DOI
[8] and , The maximum balanced subgraph of a signed graph: Applications and solution approaches. Eur. J. Oper. Res. 236 (2014) 473–487. | MR | Zbl | DOI
[9] , and , An exact approach to the problem of extracting an embedded network matrix. Comput. Oper. Res. 38 (2011) 1483–1492. | MR | Zbl | DOI
[10] and , Matheuristics. In: Handbook of Heuristics. Springer (2018) 121–153. | DOI
[11] , , and , Extracting pure network submatrices in linear programs using signed graphs. Discrete Appl. Math. 137 (2004) 359–372. | MR | Zbl | DOI
[12] , and , Signed graphs for portfolio analysis in risk management. IMA J. Manage. Math. 13 (2002) 201–210. | Zbl
[13] , Attitudes and cognitive organization. J. Psychology 21 (1946) 107–112.
[14] , and , Separator-based data reduction for signed graph balancing. J. Comb. Optim. 20 (2010) 335–360. | MR | Zbl | DOI
[15] , , , and , The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3 (2016) 43–58. | MR
[16] and , A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem. Comput. Oper. Res. 69 (2016) 68–78. | MR | Zbl | DOI
[17] , , and , A matheuristic approach for solving the edge-disjoint paths problem. Matheuristics 2016 (2016) 25.
[18] , , , and , Making a state-of-the-art heuristic faster with data mining. Ann. Oper. Res. 263 (2018) 141–162. | MR | Zbl | DOI
[19] and , Greedy randomized adaptive search procedures: advances and extensions. In: Handbook of metaheuristics. Springer (2019) 169–220. | MR | DOI
[20] , Wolfram Research. Inc., Mathematica, Version 8 (2013) 23.
[21] , A mathematical bibliography of signed and gain graphs and allied areas. Electron. J. Comb. 1000 (2012) DS8. | MR | Zbl
Cité par Sources :
