Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée

Philippe Michelon; Stéphanie Ripeau; Nelson Maculan

RAIRO - Operations Research - Recherche Opérationnelle (2001)

  • Volume: 35, Issue: 4, page 401-414
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Michelon, Philippe, Ripeau, Stéphanie, and Maculan, Nelson. "Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée." RAIRO - Operations Research - Recherche Opérationnelle 35.4 (2001): 401-414. <http://eudml.org/doc/105254>.

@article{Michelon2001,
abstract = {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.},
author = {Michelon, Philippe, Ripeau, Stéphanie, Maculan, Nelson},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {branch-and-bound; min cut; quadratic objective function; tabu search},
language = {fre},
number = {4},
pages = {401-414},
publisher = {EDP-Sciences},
title = {Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée},
url = {http://eudml.org/doc/105254},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 4
SP - 401
EP - 414
AB - 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.
LA - fre
KW - branch-and-bound; min cut; quadratic objective function; tabu search
UR - http://eudml.org/doc/105254
ER -

References

top
  1. [1] E.R. Barnes, An algorithm for partitioning the nodes of a graph. SIAM J. Algebraic Discrete Math. 3 (1982) 541-550. Zbl0505.05050MR679649
  2. [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. Zbl0655.68089MR955646
  3. [3] R.B. Boppana, Eigenvalues and graph bissection : An average case analysis, in Proc. of the 28 t h annual symposium on computer sciences. IEEE London (1987) 280-285. 
  4. [4] A. Billionnet et A. Faye, A lower bound for a constrained quadratic 0 - 1 minimization problem. Discrete Appl. Math. (soumis). Zbl0879.90147
  5. [5] N. Christofides et P. Brooker, The optimal partitioning of graphs. SIAM J. Appl. Math. 30 (1976) 55-69. Zbl0321.05123MR405911
  6. [6] W.E. Donath et A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Developments 17 (1973) 420-425. Zbl0259.05112MR329965
  7. [7] J. Falkner, F. Rendl et H. Wolkowicz, A computational study of graph partitioning. Math. Programming 66 (1994) 211-240. Zbl0830.90130MR1297064
  8. [8] D.M. Gay, Computing optimal locally constrained steps. SIAM J. Sci. Statist. Comput. 2 (1981) 186-197. Zbl0467.65027MR622715
  9. [9] M. Held, P. Wolfe et H.D. Crowder, Validation of the subgradient optimization. Math. Programming 6 (1974) 62-88. Zbl0284.90057MR341863
  10. [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. Zbl0698.90065
  11. [11] B.W. Kernighan et S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical J. 49 (1970) 291-307. Zbl0333.05001
  12. [12] T. Lengauer, Combinatorial algorithms for integrated circuit layout. Wiley, Chicester (1990). Zbl0709.68039MR1071382
  13. [13] J.M. Martinez, Local minimizers of quadratic functions on euclidean balls and spheres. SIAM J. Optim. 4 (1994) 159-176. Zbl0801.65057MR1260413
  14. [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. [15] J.J. Moré et D.C. Sorensen, Computing a trust region step. SIAM J. Sci. Statist. Comput. 4 (1983) 553-572. Zbl0551.65042MR723110
  16. [16] G.L. Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley, New York (1988). Zbl0652.90067MR948455
  17. [17] C. Roucairol et P. Hansen, Problème de la bipartition minimale d’un graphe. RAIRO : Oper. Res. 21 (1987) 325-348. Zbl0628.90049
  18. [18] D.C. Sorensen, Newton’s method with a model trust region modification. SIAM J. Numer. Anal. 19 (1982) 406-426. Zbl0483.65039

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.