Composition d'équipe

[Monsieur23]

Aloha,

Je dois organiser une compétition, qui comprend n épreuves (individuelles) ; j'ai p joueur sous la main (p ;) n), et le tableau des scores de chaque sportif pour chaque épreuve.

Je dois assigner à chaque épreuve un sportif, chaque sportif ne pouvant participer qu'à une seule épreuve ; évidemment, je veux que le score total soit maximum.

Ça me parait NP-complet, mais est-ce que quelqu'un a une idée d'algorithme d'approximation ?
J'ai pense branch & bound, mais je ne vois pas comment éliminer un sous-arbre…

Merci!

[joel76]

Tu as pensé à la programmation par contraintes ? Prolog fait ça très bien.

[Monsieur23]

Tu as pensé à la programmation par contraintes ? Prolog fait ça très bien.

Non, pas pensé. Je ne pensais pas que Prolog était fait pour l'optimisation… (je ne connais pas trop Prolog).

Merci

[joel76]

Prolog n'est pas réputé pour sa vitesse mais il permet parfois de résoudre simplement des problèmes complexes.
De toute façon des librairies de programmation par contraintes existent aussi dans d'autres langages (choco en java par exemple).
As-tu une idéee des valeurs maxi de n et p?
As-tu un exemple à proposer ?

[Monsieur23]

Dans mon cas (c'est vraiment un cas réel, ç'pour mon pôpa), j'ai p=18 et n=10.
Avec ces valeurs, ça doit être jouable d'y aller en bruteforce (en étant un peu fin), quitte à laisser tourner un peu ; mais du coup je me posais la question pour le cas général, je n'y connaît quasiment rien en approximation pour les problèmes NP-complets.

[joel76]

Ai-je bien compris le problème : trouver une composition de 10 participants choisis parmi 18 afin d'obtenir le meilleur score possible (en fonction d'anciens résultats) ?
J'ai simulé avec la librairie clpfd de SWI-Prolog ça marche bien avec avec peu de participants, mais avec tes chiffres c'est beaucoup trop long. Je vais fouiller un peu.

[Monsieur23]

Oui c'est bien ça, sachant que chaque participant ne peut participer qu'à une seule épreuve.

[joel76]

Bon, j'ai réussi à réduire le temps de recherche à moins de 2 minute dans les cas favorables.
Pour ce faire, j'ai enlevé des possibilités de recherche lorsque les scores des joueurs dans certaines épreuves étaient trop faibles par rapport aux autres. Ma méthode est un peu brutale et elle peut entraîner l'échec de la recherche. Il faudrait voir pour ton cas.

Voici le code qui fonctionne avec SWI-Prolog version 6.5.3.

Code: Tout sélectionner

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

% déclaration du nombre de compétiteurs
sportifs(18).
% declaration du nombre de d'épreuves
epreuves(10).

% prédicat à appeler
composition :-
   % creation des resultats de chaque participant
   sportifs(NS),
   epreuves(NE),

/* ici donner la matrice des résultats des compétiteurs dans les différentes épreuves

       Exemple pour une compétition de 5 épreuves avec 8 joueurs
   Resultat = [[16,14,3,18,13],
          [18,9,9,0,18],
          [0,10,14,10,15],
          [14,11,1,8,8],
          [15,3,4,19,11],
          [5,11,12,1,11],
          [9,6,10,0,8],
          [4,2,15,9,12]],
*/
   transpose(Resultat, TR),
        % on trie les résultats pour éliminer les mauvais scores
   maplist(\X^Y^sort(X,Y), TR, TR1),

       % création des listes de participation des joeurs aux épreuves
       length(Sportifs, NS),

        % un joeur participe à au plus une épreuve
       maplist(\X^(length(X,NE),
         X ins 0..1,
         sum(X, #=  Z = 0
         ;   true)), Scores_Tries, Resultat, Joueur).


Exemple de sortie :

?- time(composition).
Score max 184
[12,12,18,0,15,13,19,10,16,14] [0,0,0,0,0,0,1,0,0,0]
[6,0,8,18,7,7,4,0,2,18] [0,0,0,1,0,0,0,0,0,0]
[1,17,4,0,17,2,10,9,19,18] [0,0,0,0,0,0,0,0,1,0]
[12,9,13,10,6,7,2,16,17,16] [0,0,0,0,0,0,0,1,0,0]
[10,0,15,8,2,4,15,11,15,16] [0,0,0,0,0,0,0,0,0,0]
[9,19,7,10,2,16,0,1,4,10] [0,1,0,0,0,0,0,0,0,0]
[12,15,1,1,3,7,8,9,15,15] [0,0,0,0,0,0,0,0,0,0]
[15,10,15,0,6,11,18,5,3,0] [0,0,0,0,0,0,0,0,0,0]
[17,9,18,7,5,1,17,4,18,3] [0,0,1,0,0,0,0,0,0,0]
[10,10,1,15,8,19,14,2,19,11] [0,0,0,0,0,1,0,0,0,0]
[8,0,14,7,3,11,10,10,12,18] [0,0,0,0,0,0,0,0,0,0]
[11,6,8,6,16,11,18,0,17,15] [0,0,0,0,0,0,0,0,0,0]
[11,17,7,2,17,9,2,13,9,19] [0,0,0,0,0,0,0,0,0,1]
[5,16,11,2,7,16,4,9,14,5] [0,0,0,0,0,0,0,0,0,0]
[0,15,8,17,18,1,3,15,12,11] [0,0,0,0,0,0,0,0,0,0]
[4,1,16,12,11,10,1,14,5,8] [0,0,0,0,0,0,0,0,0,0]
[6,18,16,4,18,15,8,14,14,12] [0,0,0,0,1,0,0,0,0,0]
[19,12,17,9,15,9,14,12,16,18] [1,0,0,0,0,0,0,0,0,0]

[1,1,1,1,0,1,0,0,1,1,0,0,1,0,0,0,1,1]
% 978,396,521 inferences, 100.355 CPU in 100.392 seconds (100% CPU, 9749312 Lips)

[Monsieur23]

Whoo, merci, je vais regarder un peu comment marche ton code (merci pour les commentaires!).

[joel76]

Effectivement, avec la méthode du simplex c'est pratiquement instantané :
Voici mon code avec un exemple de résultat :

Code: Tout sélectionner

:- use_module(library(simplex)).
sportifs(18).
epreuves(10).

% utile car la méthode cherche le plus petit score donc il faut modifier
% les nombres de la matrice des résultat
max_score(40).

simplex :-
   % lecture des donnees de base
   sportifs(NS),
   epreuves(NE),
   max_score(MS),


/*   ici mettre la matrice effective des resultats

      Contrairement à la méthode précédente, chaque ligne de la matrice
      représente les résultats des compétiteurs à une épreuve

      Il y a NE lignes de NS nombres
     exemple
   Resultat = [[16,18,0,14,15,5,9,4],
          [14,9,10,11,3,11,6,2],
          [3,9,14,1,4,12,10,15],
          [18,0,10,8,19,1,0,9],
          [13,18,15,8,11,11,8,12]],
*/
   % on inverse les résultats, la méthode calcule le plus petit score
   maplist(\X^Y^maplist(\Z^U^(U is MS-Z), X, Y), Resultat, T1),

   % on complète la matrice avec des lignes de 0
   % il faut une matrice carree
   Nb is NS - NE ,
   length(Zero, NS),
   maplist(=(0), Zero),
   my_append(Nb, T1, Zero, T2),

   % on applique la méthode du simplex
   assignment(T2, R),

   % affichage de la matrice des résultats
   maplist(writeln, Resultat), nl,

   % Calcul du score réalisé
   foldl(\X^Y^Z^U^(nth0(Id, X, 1),
         nth0(Id, Y, V),
         U is MS + Z - V),
         R, T2, 0, TT1),

   % on corrige le résultat, les lignes de 0 ont apporté des scores maximaux
   TT is TT1 - MS * Nb,

   writeln('Score maxi' : TT), nl,

   % affichage de la composition de l'équipe
   forall(between(1, NE, I),
          (   nth1(I, R, Row),
         nth1(Id, Row, 1),
         nth1(I, Resultat, Row1),
         nth1(Id, Row1, Score),
         format('Epreuve ~w Compétiteur ~w Score ~w~n', [I, Id, Score]))).


my_append(0, T, _, T).

my_append(Nb, T1, Zero, T) :-
   append(T1, [Zero], T2),
   Nb1 is Nb - 1,
   my_append(Nb1, T2, Zero, T).



Exemple de résultat obtenu :

?- simplex.
[27,31,13,28,18,33,4,39,30,6,35,3,4,19,12,24,10,35]
[5,37,38,7,30,22,29,12,26,26,5,18,36,20,19,15,28,32]
[10,9,36,18,21,8,26,7,23,3,17,16,31,3,32,7,16,30]
[24,25,13,39,9,5,9,4,5,18,0,18,11,25,23,39,37,31]
[37,16,8,32,35,21,2,37,13,37,8,33,9,38,12,4,25,16]
[34,15,36,13,18,24,3,11,1,4,34,17,18,10,31,22,39,3]
[0,23,8,5,22,0,15,24,13,22,22,20,7,34,27,4,19,32]
[35,15,11,20,37,8,22,36,13,15,19,27,20,9,9,30,16,15]
[24,8,22,17,10,12,13,12,28,5,14,26,14,39,34,30,13,32]
[39,1,37,2,39,7,18,18,5,23,2,7,7,10,24,39,20,15]

Score maxi: 374
Epreuve 1 Compétiteur 8 Score 39
Epreuve 2 Compétiteur 2 Score 37
Epreuve 3 Compétiteur 3 Score 36
Epreuve 4 Compétiteur 4 Score 39
Epreuve 5 Compétiteur 10 Score 37
Epreuve 6 Compétiteur 17 Score 39
Epreuve 7 Compétiteur 18 Score 32
Epreuve 8 Compétiteur 5 Score 37
Epreuve 9 Compétiteur 14 Score 39
Epreuve 10 Compétiteur 1 Score 39
true .

[Ben314]

Ben t'as été plus efficace que moi : j'ai graté des tonnes de papiers pour essayer de comprendre comment allait marcher la méthode du simplexe dans ce cas (trés spécial...) sauf que ça me semble super la m... à comprendre vu que les sommets par lesquels tu passe sont forcéments "dégénérés" (et pas qu'un peu...)

Ca commence à me gonfler, mais pourtant j'aimerais bien comprendre pourquoi tout les sommets du simplexe "continue" (i.e. avec x réel positif) sont en fait à coordonnées entières...

[joel76]

Moi, pour ce problème je suis le programmeur, je ne connais rien des détails de cette méthode du simplex. Je me fie à une lib écrite en Prolog par un super développeur, Markus Triska et ça marche très très bien.