Un algorithme pour la bipartition d'un graphe en sous-graphes de cardinalité fixée
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 4, pp. 401-414.

Nous présentons une méthode de Séparation et Évaluation Progressive pour la bipartition d'un graphe en 2 sous-ensembles ayant une cardinalité fixée. À chaque nœud de l'arbre de recherche, nous calculons une borne inférieure en dualisant les contraintes d'intégralité et en approximant le domaine réalisable par un ellipsoïde. Une borne supérieure est également calculée par la méthode Tabou. Des résultats numériques sont présentés et commentés.

A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.

@article{RO_2001__35_4_401_0,
     author = {Michelon, Philippe and Ripeau, St\'ephanie and Maculan, Nelson},
     title = {Un algorithme pour la bipartition d'un graphe en sous-graphes de cardinalit\'e fix\'ee},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {401--414},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {4},
     year = {2001},
     zbl = {0999.05093},
     language = {fr},
     url = {http://www.numdam.org/item/RO_2001__35_4_401_0/}
}
TY  - JOUR
AU  - Michelon, Philippe
AU  - Ripeau, Stéphanie
AU  - Maculan, Nelson
TI  - Un algorithme pour la bipartition d'un graphe en sous-graphes de cardinalité fixée
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
DA  - 2001///
SP  - 401
EP  - 414
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_4_401_0/
UR  - https://zbmath.org/?q=an%3A0999.05093
LA  - fr
ID  - RO_2001__35_4_401_0
ER  - 
Michelon, Philippe; Ripeau, Stéphanie; Maculan, Nelson. Un algorithme pour la bipartition d'un graphe en sous-graphes de cardinalité fixée. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 4, pp. 401-414. http://www.numdam.org/item/RO_2001__35_4_401_0/

[1] E.R. Barnes, An algorithm for partitioning the nodes of a graph. SIAM J. Algebraic Discrete Math. 3 (1982) 541-550. | MR 679649 | Zbl 0505.05050

[2] E.R. Barnes, A. Vanelli et J.Q. Walker, A new heuristic for partitioning the nodes of a graph. SIAM J. Discrete Math. 1 (1988) 299-305. | MR 955646 | Zbl 0655.68089

[3] R.B. Boppana, Eigenvalues and graph bissection : An average case analysis1987) 280-285.

[4] A. Billionnet et A. Faye, A lower bound for a constrained quadratic 0-1 minimization problem. Discrete Appl. Math. (soumis). | Zbl 0879.90147

[5] N. Christofides et P. Brooker, The optimal partitioning of graphs. SIAM J. Appl. Math. 30 (1976) 55-69. | MR 405911 | Zbl 0321.05123

[6] W.E. Donath et A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Developments 17 (1973) 420-425. | MR 329965 | Zbl 0259.05112

[7] J. Falkner, F. Rendl et H. Wolkowicz, A computational study of graph partitioning. Math. Programming 66 (1994) 211-240. | MR 1297064 | Zbl 0830.90130

[8] D.M. Gay, Computing optimal locally constrained steps. SIAM J. Sci. Statist. Comput. 2 (1981) 186-197. | MR 622715 | Zbl 0467.65027

[9] M. Held, P. Wolfe et H.D. Crowder, Validation of the subgradient optimization. Math. Programming 6 (1974) 62-88. | MR 341863 | Zbl 0284.90057

[10] D.S. Johnson, C.R. Aragon, L.A. Mcgeoch et C. Schevon, Optimization by simulated annealing : An experimental evaluation, Part 1, Graph partitioning. Oper. Res. 37 (1989) 865-892. | Zbl 0698.90065

[11] B.W. Kernighan et S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical J. 49 (1970) 291-307. | Zbl 0333.05001

[12] T. Lengauer, Combinatorial algorithms for integrated circuit layout. Wiley, Chicester (1990). | MR 1071382 | Zbl 0709.68039

[13] J.M. Martinez, Local minimizers of quadratic functions on euclidean balls and spheres. SIAM J. Optim. 4 (1994) 159-176. | MR 1260413 | Zbl 0801.65057

[14] P. Michelon, N. Brossard et N. Maculan, A branch-and-bound scheme for unconstrained 0-1 quadratic programs, Rapport Technique # 960, DIRO. Université de Montréal. SIAM J. Optim. (soumis).

[15] J.J. Moré et D.C. Sorensen, Computing a trust region step. SIAM J. Sci. Statist. Comput. 4 (1983) 553-572. | MR 723110 | Zbl 0551.65042

[16] G.L. Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley, New York (1988). | MR 948455 | Zbl 0652.90067

[17] C. Roucairol et P. Hansen, Problème de la bipartition minimale d'un graphe. RAIRO : Oper. Res. 21 (1987) 325-348. | EuDML 104927 | Numdam | Zbl 0628.90049

[18] D.C. Sorensen, Newton's method with a model trust region modification. SIAM J. Numer. Anal. 19 (1982) 406-426. | Zbl 0483.65039