Maximisation du cout

[Anonyme]

Bonjour

Voici mon problème :
Soit une liste de couples (i,j) triée par ordre décroissant selon la
valeur associée à chaque couple (chaque couple est unique).

Le but est de selectionner les couples (i,j) tels que la somme des
valeurs associées soit maximale.

Dans la selection, si un couple (i0, j0) est sélectionné, alors les
couples (i0, j) ne pourront l'etre, ni les couples (i, j0).
Ainis, dans la selection, on a au maximum un couple ayant même
abscisse et au maximum un couple ayant même ordonnée.

Avez-vous des idées pour résoudre ce problème ?

Merci pour votre aide
Fanny

[Anonyme]

Le Fri, 15 Oct 2004 20:01:56 +0200
fanny & michou a écrit
>Bonjour
>
>Voici mon problème :
>Soit une liste de couples (i,j) triée par ordre décroissant selon la
>valeur associée à chaque couple (chaque couple est unique).
>
>Le but est de selectionner les couples (i,j) tels que la somme des
>valeurs associées soit maximale.
>
>Dans la selection, si un couple (i0, j0) est sélectionné, alors les
>couples (i0, j) ne pourront l'etre, ni les couples (i, j0).
>Ainis, dans la selection, on a au maximum un couple ayant même
>abscisse et au maximum un couple ayant même ordonnée.
>
>Avez-vous des idées pour résoudre ce problème ?
>
>Merci pour votre aide
>Fanny

Une idée comme ça, à vérifier si ça fonctionne mais ça me parait pas
mal à priori.

Tu dois forcément choisir un nombre dans chaque ligne (ou chaque
colonne selon qu'il y a plus de colonne ou plus de lignes), choisi
celui pour lequel il n'existe pas dans la colonne correspondante de
nombre plus grand que lui.



--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

[Anonyme]

fanny & michou a écrit :
> Bonjour
>
> Voici mon problème :

Problème d'optimisation sous contraintes, ça.
Voir la littérature sur l'analyse numérique matricielle et
l'optimisation (bouquin de Ciarlet, par exemple).

[Anonyme]

Le Fri, 15 Oct 2004 20:01:56 +0200
fanny & michou a écrit
>Bonjour
>
>Voici mon problème :
>Soit une liste de couples (i,j) triée par ordre décroissant selon la
>valeur associée à chaque couple (chaque couple est unique).
>
>Le but est de selectionner les couples (i,j) tels que la somme des
>valeurs associées soit maximale.
>
>Dans la selection, si un couple (i0, j0) est sélectionné, alors les
>couples (i0, j) ne pourront l'etre, ni les couples (i, j0).
>Ainis, dans la selection, on a au maximum un couple ayant même
>abscisse et au maximum un couple ayant même ordonnée.
>
>Avez-vous des idées pour résoudre ce problème ?
>
>Merci pour votre aide
>Fanny

FU2 -> fr.comp.algorithms

Bon j'ai cherché un petit peu sur ton problème.
Voici le code source des algos que j'ai testé :

http://perso.wanadoo.fr/zwim/pub/C/maximiz.zip

Tu y trouveras un algo glouton qui prend le maximum sur chaque ligne
puis passe à la ligne suivante en ayant marqué la colonne comme non
disponible pour la suite. L'algo est mauvais quand m,n sont petits
mais donne d'assez bons résultats quand m,n augmentent (normal le
nombre de collisions est réduit), de plus il est extrèment rapide.

Il y a aussi l'algorithme exact qui prend toutes les permutations
possibles et recherche le maximum. Cet algorithme donne toujours LA
meilleure solution, mais il est extrèmement lent, utilisable en
pratique pour m,n :>>



--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

[Anonyme]

Bonjour,

> Le but est de selectionner les couples (i,j) tels que la somme des
> valeurs associées soit maximale.
>
> Dans la selection, si un couple (i0, j0) est sélectionné, alors les
> couples (i0, j) ne pourront l'etre, ni les couples (i, j0).
> Ainsi, dans la selection, on a au maximum un couple ayant même
> abscisse et au maximum un couple ayant même ordonnée.

Il s'agit d'un problème de couplage de coût maximal dans un graphe
biparti. Ce problème est bien connu et largement décrit dans les
ouvrages d'algorithmique. Il admet de bons algorithmes de résolution
et il y a sans doute de nombreux codes disponibles sur le web.

Il faut chercher
- couplage de coût minimal dans un graphe biparti
- algorithme hongrois
- algorithme de Kuhn
- algorithme primal-dual
- min-cost (bipartite) matching
- minimum weight matching
- min-cost flow

Ce problème peut être vu comme un cas particulier de flot et souvent
sa présentation dans les ouvrages suit et dépend du chapitre sur les
flots.

Des références classiques sont l'ouvrage 'graphes et algorithmes' de
Gondran et Minoux (1995, 3e edition), Digraphs (Bang-Jense, Gutin
2002), Network flows (Ahuja, Magnanti, Orlin 1993), Lawler 1976, etc.

Diego Olivier

[Anonyme]

> Il s'agit d'un problème de couplage de coût maximal dans un graphe
> biparti. Ce problème est bien connu et largement décrit dans les
> ouvrages d'algorithmique. Il admet de bons algorithmes de résolution
> et il y a sans doute de nombreux codes disponibles sur le web.
>
> Des références classiques sont l'ouvrage 'graphes et algorithmes' de
> Gondran et Minoux (1995, 3e edition), Digraphs (Bang-Jense, Gutin
> 2002), Network flows (Ahuja, Magnanti, Orlin 1993), Lawler 1976, etc.

Pfiou, avec toutes ces références, ca a l'air compliqué... Il est faux mon
algo ?

--
Vincent

[Anonyme]

Bonjour,

> Pfiou, avec toutes ces références, ca a l'air compliqué...

Normalement on apprend cet algorithme en maîtrise d'informatique (dans
un cours de type 'algorithmique', 'recherche opérationnelle' ou
'optimisation combinatoire'). En DEA il est supposé connu même si pour
certains de petites (re)visions s'imposent.

> Il est faux mon algo ?

Je n'en sais rien. C'est la première fois que j'entends parler de
résolution du couplage de coût maximal par une approche de
programmation dynamique mais sa complexité est la bonne (n^3).
L'algorithme hongrois est tellement efficace qu'il est rare que l'on
utilise autre chose.

lemmes préalables :
- On remarque qu'en soustrayant une valeur donnée à toute une ligne ou
à toute une colonne on ne change pas la solution finale
- On remarque que si l'on a une famille indépendante de n zéros (si on
mettait des tours d'échecs sur ces zéros, elles ne seraient pas
mutuellement en prise) on a une solution optimale

Algorithme :

i) soustraire autant de valeurs possibles aux lignes et au colonnes
afin de faire apparaître le plus grand nombre de zéros (tout en
gardant tous les coefficients positifs bien entendu) - il y a une
'méthode' systématique pour le faire par exemple soustraire le min
d'une ligne à toute la ligne puis d'une colonne à toute la colonne

ii) déterminer la cardinalité maximale k d'un ensemble de zéros
indépendants. Si k = n terminé, sinon, il faut couvrir tous les zéros
avec k traits (lignes ou colonnes) - techniquement parlant cette étape
construit un flot max puis détermine une coupe min.

iii) trouver la plus petite valeur non couverte

iv) soustraire cette valeur à tout le tableau et l'ajouter à toutes
les cases par lesquelles passe un 'trait' (si une case est à
l'intersection de deux traits il faut lui ajouter deux fois cette
valeur)

v) revenir en ii)

voir

http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

pour quelques figures et explications. Les étapes sont un peu
différentes car je les présente pour un déroulement 'à la main'. Je
reprends le même exemple

tableau initial

1 2 3
2 4 6
3 6 9

après i)

0 0 0
0 1 2
0 2 4

après ii)

k = 2

+ - -
| 1 2
| 2 4


iii) min = 1

après iv)

1 0 0
0 0 1
0 1 3

on a fini car on peut mettre des tours (d'échecs) sur la diagonale

. . T
. T .
T . .

sur la matrice initiale cela équivaut à un couplage de coût 10


Ces étapes peuvent paraître magiques mais elles ont une justification
théorique par la dualité en programmation linéaire et l'algorithme
primal-dual.

l'étape i) est ressemble à l'approche gloutonne
les étapes ii), iii) et iv) ont une propriété d'incrémentalité
(notamment quand on le présente sous la forme primal-dual) qui
rappelle il est vrai un peu la programmation dynamique (recherche du
second meilleur et calcul du coût réduit)


Diego Olivier