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 (2010)

  • 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 35.4 (2010): 401-414. <http://eudml.org/doc/197797>.

@article{Michelon2010,
abstract = { 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. },
author = {Michelon, Philippe, Ripeau, Stéphanie, Maculan, Nelson},
journal = {RAIRO - Operations Research},
keywords = {branch-and-bound; min cut; quadratic objective function; tabu search},
language = {fre},
month = {3},
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/197797},
volume = {35},
year = {2010},
}

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

References

top
  1. E.R. Barnes, An algorithm for partitioning the nodes of a graph. SIAM J. Algebraic Discrete Math.3 (1982) 541-550.  
  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.  
  3. R.B. Boppana, Eigenvalues and graph bissection: An average case analysis, in Proc. of the 28th annual symposium on computer sciences. IEEE London (1987) 280-285.  
  4. A. Billionnet et A. Faye, A lower bound for a constrained quadratic 0-1minimization problem. Discrete Appl. Math. (soumis).  
  5. N. Christofides et P. Brooker, The optimal partitioning of graphs. SIAM J. Appl. Math.30 (1976) 55-69.  
  6. W.E. Donath et A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Developments17 (1973) 420-425.  
  7. J. Falkner, F. Rendl et H. Wolkowicz, A computational study of graph partitioning. Math. Programming66 (1994) 211-240.  
  8. D.M. Gay, Computing optimal locally constrained steps. SIAM J. Sci. Statist. Comput.2 (1981) 186-197.  
  9. M. Held, P. Wolfe et H.D. Crowder, Validation of the subgradient optimization. Math. Programming6 (1974) 62-88.  
  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.  
  11. B.W. Kernighan et S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical J.49 (1970) 291-307.  
  12. T. Lengauer, Combinatorial algorithms for integrated circuit layout. Wiley, Chicester (1990).  
  13. J.M. Martinez, Local minimizers of quadratic functions on euclidean balls and spheres. SIAM J. Optim.4 (1994) 159-176.  
  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.  
  16. G.L. Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley, New York (1988).  
  17. C. Roucairol et P. Hansen, Problème de la bipartition minimale d'un graphe. RAIRO: Oper. Res.21 (1987) 325-348.  
  18. D.C. Sorensen, Newton's method with a model trust region modification. SIAM J. Numer. Anal.19 (1982) 406-426.  

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.