Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/RO_2001__35_4_401_0/