Optimisation numérique

[gabvoir]

Bonjour,

J'organise actuellement un évènement avec des étudiants de mon école.
J'ai pour cela responsabilité de créer des groupes d'élèves.
Afin de satisfaire tout le monde j'ai fait un sondage afin de savoir qui veut etre avec qui.
J'ai un petit problème afin de modéliser tout cela.

Il y a 157 étudiants, je n'ai pas de groupe limité, il faut au moins 2 personnes par groupe.
La sortie du sondage est une table de 157*157, avec des 1 quand un étudiant veut etre avec un autre.
Sachant que si étudiant A signale qu'il souhaite être avec un B, le B n'a pas obligatoirement signalé qu'il souhaitait etre avec l'élève A.

Je suis actuellement partie sur une optimisation PLNE (Programmation Linéaire en Nombre Entiers).
Entrée : la matrice des voeux
Variable d'optimisation : matrice d'affectation d'un élève à un groupe, matrice 157lignes*79colonnes (minimum de 2 personnes par groupe)
Fonction d'optimisation : c'est la que je bloque, pour le moment j'ai ca :

Code: Tout sélectionner

sum(e1 in Etudiants,e2 in Etudiants,g in Groupes)
      affectations[e1][g] * voeuxEtudiants[e1][e2] +
   sum(e1 in Etudiants,e2 in Etudiants,g in Groupes)
      affectations[e2][g] * voeuxEtudiants[e1][e2]

Contrainte d'optimisation :
- 1 étudiant n'appartient qu'a un seul groupe
- 2 étudiants mini par groupe

Je donne mon code entier, sachant que j'utilise IBM ILOG CPLEX Optimization Studio :

Code: Tout sélectionner

int nbEtudiants = 157;
int nbGroupes = 79;
range Etudiants = 1..nbEtudiants;
range Groupes = 1..nbGroupes;
int voeuxEtudiants[Etudiants][Etudiants] = ...; (peuplé avec des 1 a l'intersection des vœux, pas d’échelle de volonté)

dvar boolean affectations[Etudiants][Groupes] in 0..1;

maximise
   sum(e1 in Etudiants, e2 in Etudiants, g in Groupes)
      affectations[e1][g] * voeuxEtudiants[e1][e2] +
   sum(e1 in Etudiants, e2 in Etudiants, g in Groupes)
      affectations[e2][g] * voeuxEtudiants[e1][e2];

subject to {
   forall(e in Etudiants)
    ctChaqueEtudiantNaQuunEtUnSeulGroupe:
      sum(g in  Groupes) affectations[e][g] == 1;
     
      forall(g in Groupes)
    ctMini2EtudiantsParGroupe:         
      sum(e in Etudiants) affectations[e][g] >= 2;
}


Si quelqu'un a une idée pour modéliser ce problème qui semble pourtant simple, je serais ravis

Merci bcp !

Gabriel

[Cliffe]

Y'a un nombre max par groupe ?
Donne nous ton programme avant de te lancer sur cplex

[gabvoir]

Oui un nombre max de 7 par groupe.
Càd mon programme ? Le logiciel que j'utilise ?

[Cliffe]

Ton programme linéaire :p '(je suis mm pas sur que ça soit linéaire).

[Cliffe]

Que penses-tu de ça :

Données :
- : le nombre d'étudiants.
- : le nombre de groupes.
- La matrice binaire , où si l'étudiant souhaite être avec l'étudiant .

Variables :
- Soit la variable binaire indiquant si le -ème groupe est utiliser ou non.
- Soit la variable binaire indiquant si le -ème étudiant est dans le -ème groupe.
- La variable entière indique le nombre de satisfactions dans le groupe .

Programme non linéaire en nombre entier :

[CENTER]





[/CENTER]

[CENTER] [/CENTER]

[CENTER][/CENTER]

[CENTER]
[/CENTER]

Tu peux linéariser la dernière contrainte si tu n'a pas de solveur non linéaire.

[gabvoir]

Voila la transformation en langage IBM ILOG CPLEX.

Code: Tout sélectionner

int nbEtudiants = ...;
int nbGroupes = ...;
range Etudiants = 1..nbEtudiants;
range Groupes = 1..nbGroupes;
int voeuxEtudiants[Etudiants][Etudiants] = ...; /*(peuplé avec des 1 a l'intersection des vœux, pas d’échelle de volonté)*/

dvar boolean groupesE[Groupes] in 0..1;
dvar boolean affectations[Etudiants][Groupes] in 0..1;

maximize
   sum(g in Groupes)
        sum(e1 in Etudiants)
          sum(e2 in Etudiants)
        voeuxEtudiants[e1][e2] * affectations[e1][g] * affectations[e2][g];   
      
subject to {
   forall(e in Etudiants)
    ctChaqueEtudiantNaQuunEtUnSeulGroupe:
      sum(g in  Groupes) affectations[e][g] == 1;
   
    forall(g in Groupes)
    ctMaxi7EtudiantsParGroupe:
       sum(e in Etudiants) affectations[e][g] = 2*groupesE[g];
}


J'ai un jeu d'essai avec 12 étudiants, ca fonctionne.
Mais quand je lance avec mon jeu de 157, j'y suis depuis 3 heures, et tjs pas résolu.
Il doit y avoir un soucis kkpart ?
Qu'en penses tu ?

[Cliffe]

Donne voir ta matrice que j'essaye.

[gabvoir]

Tu trouveras sur ce lient mon fichier data.
http://cjoint.com/?DElnTDjpWa6

Merci de ton aide !

[Cliffe]

J'ai un "out of memory". Windows me bride la mémoire de mon appli. dmg :p

[gabvoir]

Erf oui moi au bout de 3h ca n'avais toujours pas trouvé.
Ne peut il pas yavoir une trop grosse contrainte, ou bien un problème de modélisation ?

[Cliffe]

J'arrive à résoudre jusqu'à 50 étudiants environ. Au delà, il me répond qu'il n'a pas assez de mémoire :mur:. Pourtant il n'utilise que 3Go de ram sur mes 16Go.

Pour les temps de calcul, c'est bien possible. Si tu regardes ta triple somme : 157 * 157 * 79 = 2 Millions de variables.

[Cliffe]

Code: Tout sélectionner

Groupe  1 = {40,42,78,109,138}
Groupe  2 = {60,65,84,89,130,136}
Groupe  3 = {11,123}
Groupe  4 = {37,85,92,101,128}
Groupe  5 = {51,105,120,131}
Groupe  6 = {5,45,48,77,112,145}
Groupe  7 = {12,32,35,46,89,146,155}
Groupe  8 = {4,6,16,21,29,118,156}
Groupe  9 = {15,19,55,62,99,104}
Groupe 10 = {22,27,34,113,133,134,142,149,151}
Groupe 11 = {26,93,143,150,157}
Groupe 12 = {7,13,31,75,119,121,148}
Groupe 13 = {65,68,73,86,95,109,115,141}
Groupe 14 = {1,38,52,70,137}
Groupe 15 = {12,24,72,75,87,97,124,125}
Groupe 16 = {28,71,80,103,126,139}
Groupe 17 = {8,32,40,63,82,106,107,116}
Groupe 18 = {2,18,25,48,57,61,79,128,153}
Groupe 19 = {49,66,93}
Groupe 20 = {17,22,37,53,54,56,81,96,98,101,152}
Groupe 21 = {42,44,58,68,110,132,140}
Groupe 22 = {9,90,114,121,146}

[gabvoir]

Salut,

Ce résultat correspond au début de l'optimisation, ou à sa totalité ?
J'imagine qu'à une partie, car certaine personnes manques et pour avoir tester sur 3 groupes au hasard, les voeux ne sont pas vraiment respectés :S

J'ai relancé l'optimisation de mon coté, cette fois en 4h tjs pas fini, et je ne sais pas comment mettre pause et visauliser l'avancé du calcul :S

Encore merci !

[Cliffe]

J'ai fait une erreur lors de la recopie des résultats :zen:

Code: Tout sélectionner

Groupe  1 = {88,108,109,119,127,150,152}
Groupe  2 = {12,26,41,67,97,114,134}
Groupe  3 = {29,38,49,61,79,126,146}
Groupe  4 = {40,58,69,83,118,130,142}
Groupe  5 = {36,93,115,116,136,140,143}
Groupe  6 = {44,65,112,122,133,141}
Groupe  7 = {17,51,52,53,59,90,98}
Groupe  8 = {34,37,43,55,111,132,148}
Groupe  9 = {11,31,73,151}
Groupe 10 = {20,24,102,125,135,144,145}
Groupe 11 = {45,64,99,103,110,138,139}
Groupe 12 = {50,68,75,92,95,100,106}
Groupe 13 = {74,113,120,131,137}
Groupe 14 = {23,25,35,56,71,86,129}
Groupe 15 = {1,14,30,63,72,94,96}
Groupe 16 = {2,62,80,87,89,107,128}
Groupe 17 = {33,81}
Groupe 18 = {28,46,48,57,77,84,147}
Groupe 19 = {5,13,70,76,117,123}
Groupe 20 = {4,6,16,153,154,155,156}
Groupe 21 = {42,47,54,60,82,104,124}
Groupe 22 = {85,101,105,149,157}
Groupe 23 = {7,39,91,121}
Groupe 24 = {66,78}
Groupe 25 = {3,8,9,15,19,21,22}
Groupe 26 = {10,18,27,32}


[fatal_error]

hello,

Ce résultat correspond au début de l'optimisation, ou à sa totalité ?

Le poste de Cliffe de 19h43 donne le résultat dans sa totalité (il y a bien les 157 nombres différents)

J'ai relancé l'optimisation de mon coté, cette fois en 4h tjs pas fini

Je suis curieux également de savoir combien de temps ca a pris et avec quel programme/solveur.

Enfin, on a maximisé le nombre de gens satisfaits, peut etre y a-t-il un moyen de s'en sortir pas trop mal avec des alternatives moins couteuses en temps... (j'y réfléchis)

[Cliffe]

Enfin, on a maximisé le nombre de gens satisfaits, peut etre y a-t-il un moyen de s'en sortir pas trop mal avec des alternatives moins couteuses en temps... (j'y réfléchis)

Sur mon modèle, je compte le nombre de satisfactions et non pas de gens satisfait.

On peut modifier le problème en ne mettant que 23 groupes et la contraintes de 7 personnes max par groupes. A priori plus ont met de personne dans un groupe et plus il y aura de satisfaits.

[Cliffe]

Avec 23 groupes :

Code: Tout sélectionner

Groupe  1 = {38,61,67,79,99,126,146}
Groupe  2 = {12,13,153,154,155,156,157}
Groupe  3 = {46,48,57,74,113,120,131}
Groupe  4 = {56,71,85,101,105,129,149}
Groupe  5 = {31,44,65,112,122,133,141}
Groupe  6 = {8,9,19,20,21,22,27}
Groupe  7 = {35,50,68,75,95,100,106}
Groupe  8 = {24,40,58,69,83,93,118}
Groupe  9 = {1,26,30,59,72,114,139}
Groupe 10 = {29,49,107,123,132,142,148}
Groupe 11 = {80,108,109,119,127,150,152}
Groupe 12 = {7,11,17,32,39,81,84}
Groupe 13 = {14,64,70,73,76,103,117}
Groupe 14 = {41,42,47,66,97,104,124}
Groupe 15 = {3,33,34,37,43,55,111}
Groupe 16 = {25,102,125,135,137,144,145}
Groupe 17 = {36,110,115,116,136,140,143}
Groupe 18 = {45,54,60,82,91,121,147}
Groupe 19 = {28,63,78,92,94,96,138}
Groupe 20 = {4,6,10,16,23,130,134}
Groupe 21 = {5,15,51,52,53,90,98}
Groupe 22 = {18,62,77,87,89,128,151}
Groupe 23 = {2,86,88}

[gabvoir]

Merci pour vos remarques.
En fait je n'ai pas vraiment de limites du nombre de groupes.
Et le nombre de 7 est un nombre max mais il est censé resté exceptionnel.
Nombre de personnes par groupe moyen : 4 / 5

J'ai lu rapidement le résultat de ton optimisation à 26 groupes.
Le groupe 24, pourquoi le 78 n'a pas été mis dans le groupe 11 avec le 110 et 138 ?
Sachant que c'est son voeux et que le 66 n'a aucun vœux, il aurait pu etre mis avec kkun d'autre non ?

Merci pour votre aide !