no. 4
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
SP  - 401
EP  - 414
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_4_401_0/
LA  - fr
ID  - RO_2001__35_4_401_0
ER  - 
%0 Journal Article
%A Michelon, Philippe
%A Ripeau, Stéphanie
%A Maculan, Nelson
%T Un algorithme pour la bipartition d'un graphe en sous-graphes de cardinalité fixée
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 401-414
%V 35
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/RO_2001__35_4_401_0/
%G fr
%F RO_2001__35_4_401_0
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 | Zbl

[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 | Zbl

[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

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

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

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

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

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

[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

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

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

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

[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 | Zbl

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

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

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