The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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.
En este trabajo proponemos un algoritmo de O(nmlogU) para resolver el problema de biflujo máximo simétrico en una red no dirigida. Para resolver este problema se introduce un cambio de variable que permite dividir el problema original en dos problemas de flujo máximo. De esta manera se obtiene un algoritmo sencillo y eficiente donde se utilizan las herramientas computacionales propias de la resolución del clásico problema de maximizar un único flujo.
Currently displaying 1 –
5 of
5