Re: Programme Lineaire en Nombre Entier

Pour ton problème, par exemple, je verrais bien déjà au moins 2 inconnues :

xij : variables binaires: l'étudiant i est dans le projet j.
pj : variable binaire: le projet j est ouvert

On peut déjà commencer à exprimer quelques relations avec ça :

xi1 + xi2 + ... + xn = 1 (un étudiant est dans un et un seul projet)

xij <= pj (un étudiant est dans un projet seulement si il est ouvert, ça se transforme trivialement en xij - pj <= 0)
x1j + x2j + ... + xnj <= 5 (pas plus de 5 étudiant dans un projet)
On peut déjà factoriser ces deux contraintes en une seule :
x1j + x2j + ... + xnj <= 5pj (si pj est égal à 0, ça force tout les xij à 0, sinon, ils doivent être inférieur à 5)

Pour forcer le nombre d'étudiant par groupe à être supérieur à 3, il faut une contrainte du même type:
x1j + x2j + ... + xnj >= 3pj (si le groupe est ouvert, il doit y avoir 3 étudiants dedans)

(En pratique, pour transformer ces deux relations en égalités, il faudra ajouter des inconnues. On pourrai très bien utiliser ces inconnues et mettre des pénalités pour les groupes de 3 ou 5 ou limiter leur nombre)

Il reste plus qu'a choisir l'objectif. Par exemple, tu peux donner une insatisfaction de 1 si l'étudiant est dans son 2 ième choix, 2 si il est dans son troisième choix ... ect. et minimiser la somme des insatisfactions. Tu pourrai être aussi plus fin en cherchant à maximiser la satisfaction et en demandant aux étudiants de noter chaque projet, ça leur permet d'exprimer des opinions plus fines comme "je veux ce projet, tout le reste est indifféremment nul" "j'aime bien ces trois projets, au pire celui là il est bien, mais pas ceux là" "j'en ai rien à foutre".

Pour les groupes, ou bien tu refait les contraintes pour prendre en compte les groupes, ou bien tu fait ça de manière crade, en rajoutant une contrainte "tout ces étudiants font le même projet" et en laissant le solveur simplifier le problème pour toi (ou pas). l'avantage (ou le désavantage) c'est qu'il peut aussi compléter des groupes de 2,3 ou 4 personnes.

Après, pour utiliser ça en python, je sais pas si il existe des bonnes bibliothèques pour ça, mais au pire tu peux lancer lp_solve depuis un programme python et lui donner ton problème en entrée, et parser sa sortie.

(un truc bien avec lp_solve, c'est que sa bibliothèque est une dépendance du solveur d'openoffice/libreoffice, donc il est déjà installé sur pas mal de systèmes)