Discussion :

[ol9245]

Bonjour à tous,

voilà mon problème du jour.

J'ai N tuyaux à connecter dans N pots. Chaque connexion du tuyau i dans le pot j est qualifiée par un nombre de 0 à 1, de mauvaise (0) à bonne (1).

Une fois mes N connexions faites, il y e a une pire que les autres : c'est le maillon faible du système.

Je veux optimiser mon système pour que son maillon faible soit le plus fort possible.

Ma question : ce problème correspond-il à (ou est-il voisin d') un problème connu de recherche opérationnelle dont je pourrais chercher et transcrire l'algorithme ?

merci

[pseudocode]

Comme ça, sans réfléchir (comme toujours :aie), je dirais : Maximum flow

[Biribibi]

Bonjour,

Il semblerait que ce problème soit connu sous le nom "min-max matching problem",
c'est à dire trouver un couplage parfait dans un graphe biparti qui maximise le poids minimal de l'ensemble des arêtes du couplage.

On peut trouver un algorithme polynomial dans le livre
Combinatorial Optimization: Networks and Matroids de Lawler
[ame="http://www.amazon.com/Combinatorial-Optimization-Networks-Eugene-Lawler/dp/0486414531"]Amazon.com: Combinatorial Optimization: Networks and Matroids (9780486414539): Eugene Lawler: Books@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41FXBR6QPML.@@AMEPARAM@@41FXBR6QPML[/ame]

Malheureusement, je n'ai pas accès à ce livre.

Sinon un algorithme un peu naïf mais néanmoins polynomial est le suivant.

Je représente le problème par un graphe G = (A union B, E)
où A est l'ensemble des pots, B l'ensemble des tuyaux et E l'ensemble des arêtes entre A et B, c'est à dire l'ensemble des bonnes connexions.
On a aussi une fonction de poids w sur les arêtes E.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
tant qu'il existe un couplage parfait dans G
      C <- un couplage parfait de G
      retirer l'arête de plus faible poids dans G
fin tant que
renvoyer C

[ol9245]

@pseudocode : je vois pas bien comment transcrire mon problème en optimisation de flux. J'ai un problème multi-source, multi-puits et ce n'est pas le flux total que je veux maximiser, mais seulement celui de sa branche la plus faible.

@biribibi : J'ai pas tout compris !
je ne veux connecter que 1 seul trou à 1 seul bidon.
je peux commencer par une connexion non optimale (mais proche) puis rentrer dans une boucle d'optimisation.

Dans ce cas, si je débranche une arête, je dois reconnecter le trou et le bidon d'une autre manière.

sinon, je peux aussi commencer par tout connecter, puis déconnecter le pire de tous, tant que tous les bidons sont connectés et tous les trous aussi. C'est ça que tu veux dire ? Ca converge vers l'optimum ?

dans ce cas ça ferait qq chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
Matrice Cout de dimension (Trou, Bidon)
convention : 
Cout(t,b) réel : il y a connexion entre t et b et la matrice donne le cout.
cout (t,b) infini : il n'y a pas de connexion
 
calculer tous les couts
 
tant que (au moins un réel dans chaque ligne et dans chaque colonne)
    chercher le pire des couts parmi ceux qui ne sont pas seuls ni en ligne ni en colonne
    le supprimer
fin boucle
 
retourner la matrice Cout

[Biribibi]

Un couplage parfait consiste exactement associer un trou à exactement un bidon (et réciproquement).

Comme algo pour obtenir un couplage parfait, tu peux regarder par exemple
http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm qui n'est pas très dur à implémenter.

Le principe de l'algo que je proposais est de rétirer des arêtes progresssivement en partant de celle de plus faible poids et calculer un couplage parfait à chaque étape jusqu'à que l'on ne puisse plus.
Le couplage parfait ainsi trouvé correspond à ce que tu cherches ( c'est celui avec qui maximise le poids du "maillon faible").

[Biribibi]

En fait, ce problème semble être plus connu sous le nom "bottleneck assignment problem".
On trouve pas mal de référence en cherchant sur Google.
je n'ai pas encore eu le temps de trouver un algorithme, je chercherai plus tard.

Le premier algorithme est du à Edmonds et Fulkerson.
[73] J. Edmonds and D. R. Fulkerson, Bottleneck extrema, Journal of Combinatorial Theory 8, 1970, 299-306.

mais je n'ai pas encore pu me procurer l'article.

edit:

Un algorithme est proposé dans le bouquin Assignment Problems de Par Rainer E. Burkard,Mauro Dell'Amico,Silvano Martello (à partir de la page 172).
On peut le trouver partiellement en ligne ici:

http://books.google.com/books?id=nHI...derigs&f=false

[ol9245]

J'ai aussi cherché de mon côté.
est-ce que ce serait pas ça ? http://www.mathworks.com/matlabcentr...exchange/11609

[Biribibi]

L'algorithme Hongrois (dans sa version classique) sert à résoudre l'assignement
(ou couplage parfait selon le vocabulaire utilisé) de poids maximal (ou minimal, ça revient au même) ou le poids de l'assignement est la somme de chacune des arêtes choisies.

Ton problème (bottleneck assignment) est différent car tu essaie de maximiser le poids de la plus petite arête. Mais bon, il semble qu'il existe une variation de l'algorithme hongrois pour le problème du bottleneck assignment (mais je n'arrive pas à accéder à la publication). Mais cette variation ne doit pas être triviale puisqu'elle justifie une publication.

[ol9245]

L'algorithme Hongrois (dans sa version classique) sert à résoudre l'assignement
(ou couplage parfait selon le vocabulaire utilisé) de poids maximal (ou minimal, ça revient au même) ou le poids de l'assignement est la somme de chacune des arêtes choisies.

Ton problème (bottleneck assignment) est différent car tu essaie de maximiser le poids de la plus petite arête. Mais bon, il semble qu'il existe une variation de l'algorithme hongrois pour le problème du bottleneck assignment (mais je n'arrive pas à accéder à la publication). Mais cette variation ne doit pas être triviale puisqu'elle justifie une publication.

Oui, en effet, cet algo ne fonctionne pas apparemment sur mon problème...
Je vais donc essayer de le coupler avec ton "algo trivial" en l'utilisant pour simplement vérifier l'existence d'un couplage parfait.

[Biribibi]

Si tu cherches une bonne bibliothèque pour traiter les problèmes combinatoires, je te conseille LEDA, tu trouveras pas mal d'algorithmes pour des problèmes classiques (couplage parfait, arbre de poids minimal, ...) et cette bibliothèque est connue pour être particulièrement optimisée.
Par contre, il ne semble y avoir rien pour le bottleneck assignment problem mais il y a un algorithme pour le couplage parfait (perfect matching) qui pourra t'être utile.

le site est ici: http://www.algorithmic-solutions.com/leda/
et le manuel: http://www.algorithmic-solutions.inf...al/MANUAL.html

[Biribibi]

Bonjour,

Après coup, j'ai trouvé une amélioration possible de l'algorithme.

Finalement le but est de trouver le poids maximal tel que si on seuille les arêtes plus petites que ce poids, il existe encore un couplage parfait.

La première approche que j'ai proposé est de supprimer les arêtes une par une de celle au plus faible fort à celle au plus fort poids et de vérifier à chaque étape de l'itération si un couplage parfait existe.
Ca donne un algorithme en O( m C(n, m)) où n est le nombre de sommets, m le nombre d'arêtes et C(n,m) est la complexité de l'algorithme utilisé pour calculer un couplage parfait.

En fait, on peut faire mieux en triant dans un premier temps les arêtes par ordre de poids croissant et ensuite en faisant une recherche par dichotomie pour ce seuil.

Ca donne un algorithme en O( log(m) C(n, m)) ce qui est, je pense, assez efficace en pratique, si on utilise une bonne implémentation pour un algorithme de couplage parfait.

[ol9245]

Bonjour,

Après coup, j'ai trouvé une amélioration possible de l'algorithme.

Finalement le but est de trouver le poids maximal tel que si on seuille les arêtes plus petites que ce poids, il existe encore un couplage parfait.

La première approche que j'ai proposé est de supprimer les arêtes une par une de celle au plus faible fort à celle au plus fort poids et de vérifier à chaque étape de l'itération si un couplage parfait existe.
Ca donne un algorithme en O( m C(n, m)) où n est le nombre de sommets, m le nombre d'arêtes et C(n,m) est la complexité de l'algorithme utilisé pour calculer un couplage parfait.

En fait, on peut faire mieux en triant dans un premier temps les arêtes par ordre de poids croissant et ensuite en faisant une recherche par dichotomie pour ce seuil.

Ca donne un algorithme en O( log(m) C(n, m)) ce qui est, je pense, assez efficace en pratique, si on utilise une bonne implémentation pour un algorithme de couplage parfait.

C'est très joli !
J'avais déja pendé au tri évidemment pour ne pas rechercher le minimum à chaque fois, mais je n'avais pas pendé à l'exploration dichotomique.

Ca me fait vraiment plaisir de découvrir ce genre de subtilité

Je ne suis pas certain de l'implémenter pour ce coup-ci car mon problème n'est pas gros (52x52) mais je retiens. merci merci

sinon, tu fais quoi toi, pour être si calé en théorie des graphes / recherche opérationnelle ? Moi je suis loin de ça : je fais de la recherche en science du sol et le problème que j'ai est très pratique. Il s'agit de concevoir un appareil expérimental que je vais utiliser en juillet pour une manip.