Constitution de groupes [programmation par contrainte]

Bonjour à toutes et à tous,

Je vous expose un problème d'algorithmique dont ne ne sais par quel bout le prendre.

- J'ai un ensemble de N individus affectés d'une note. (N<150)
- j'ai un ensemble de n classes (2<n<10)


Je dois constituer les n classes en répartissant au mieux les N individus. C'est à dire de sorte que les classes comportent sensiblement le même nombre d'individus et que les classes soient globalement équivalente (disons même hétérogénéité et même moyenne).

Jusque la je sais faire.

Le problème, c'est que certains individus ont des contraintes supplémentaires.

Par exemple :

- être avec certains individus
- ne pas être avec certains individus
- appartenir à une classe précise
- ne pas appartenir à une classe précise
- appartenir à un groupe (groupe qui peut être réparti sur plusieurs classes)

C'est la où je me perds un peu, j'ai bien cherché sur la programmation par contrainte qui correspond à la deuxième partie du problème mais je ne vois pas comment faire le lien avec la première partie.

Si quelqu'un à une idée,

Cordialement, merci d'avance, en espérant avoir été suffisamment clair.

Laurent

P.S Je programme sous Delphi-pascal et je n'ai pas trouvé de bibliothèque pour la programmation par contraintes.

Je vois trois manières de faire (par importance décroissante donnée à la répartition/moyenne) :

1. tu traduis le fait que les classes doivent comporter le même nombre d’éléments/avoir la même moyenne en contraintes que tu rajoutes à ton problème.
2. tu évalues la qualité de ta solution (répartition, moyenne etc) via une fonction objectif et tu t'en sers pour faire de l'optimisation.
3. tu utilises une heuristique de choix variable/valeur qui va favoriser des solutions de la forme qui t’intéresse.

Quant à une librairie en Delphi/pascal : aucune idée.

Deux trois questions pour clarifier certaines choses :)

Citation:

---

Envoyé par lpecqueux

Le problème, c'est que certains individus ont des contraintes supplémentaires.

Par exemple :

- être avec certains individus
- ne pas être avec certains individus
- appartenir à une classe précise
- ne pas appartenir à une classe précise
- appartenir à un groupe (groupe qui peut être réparti sur plusieurs classes)

---

"Certains", c'est combien par rapport à N ~ 150 ?

Il y a un "ordre" dans les classes ? Que veut dire appartenir à une classe précise par rapport à être avec certains individus et pas avec d'autres ?
De la même manière, j'ai pas trop compris la notion de groupe. Certains individus doivent être répartis dans un certain de classes en fait, indépendamment des "couples" d'invidus (qui doivent etre ensemble ou ne pas etre ensemble) ?
Enfin, est-ce que les contraintes sont toute réalisables. Par exemple si tu ne dois former que deux classes et que trois individus ne peuvent être avec aucun des deux autres => problème !

Merrci :)

Citation:

---

Envoyé par Vakhyw

Deux trois questions pour clarifier certaines choses :)



"Certains", c'est combien par rapport à N ~ 150 ?

Il y a un "ordre" dans les classes ? Que veut dire appartenir à une classe précise par rapport à être avec certains individus et pas avec d'autres ?
De la même manière, j'ai pas trop compris la notion de groupe. Certains individus doivent être répartis dans un certain de classes en fait, indépendamment des "couples" d'invidus (qui doivent etre ensemble ou ne pas etre ensemble) ?
Enfin, est-ce que les contraintes sont toute réalisables. Par exemple si tu ne dois former que deux classes et que trois individus ne peuvent être avec aucun des deux autres => problème !

Merrci :)

---

Je vais essayer d'être un peu plus clair sur un exemple (mais ce n'est qu'un exemple)

Considérons 125 élèves de 5e à répartir sur 5 classes de 4e (A, B, C, D et E)

Parmi ces élèves

- une petite vingtaine fait de l'allemand les autres de l'espagnol
- les germanistes seront répartis sur deux classes (A et B par exemple)
- les hispanisants peuvent être dans toutes les classes

les élèves peuvent avoir des options :
- une petite vingtaine de latinistes, (faisant de l'allemand ou de l'espagnol) à répartir sur deux classes (A et C par exemple)

- environ 25 faisant option Sport ( à répartir sur deux classes B et D par exemple)

ainsi de suites pour d'autres options (Euro, Sciences)

- certains élèves ne doivent pas être dans la même classe ( des groupes de moins de 5 élèves forcément)
- certains élèves doivent être ensemble

- enfin les classes doivent être hétérogènes en terme de résultats (moyenne ou autre à définir médiane écart type...) et avoir sensiblement le même nombre d'élèves (à 1 près)

J'espère ainsi être plus clair.

Je suis conscient qu'un tel problème n'est pas évident et que certaines situations sont impossibles dans ce cas il faudrait trouver une solution optimale ou indiquer les incompatibilités.

Si quelqu'un a une piste,

Merci d'avance


Cordialement
Laurent

IL est clair selon ton exemple que
les germanistes latinistes seront en A
les sportifs ne peuvent pas faire latin,
etc
Je commencerais par faire la liste des combinaisons possibles, et qui contiennent au moins un élève. Tu en auras un nombre relativement petit que tu auras ensuite à répartir dans tes 5 classes.

Citation:

---

Envoyé par Nebulix

IL est clair selon ton exemple que
les germanistes latinistes seront en A
les sportifs ne peuvent pas faire latin,
etc
Je commencerais par faire la liste des combinaisons possibles, et qui contiennent au moins un élève. Tu en auras un nombre relativement petit que tu auras ensuite à répartir dans tes 5 classes.

---

Je dois mal comprendre ta remarque parce que juste en considérant la vingtaines de germanistes il y a environ 4*10^6 combinaisons possibles (sauf erreur de ma part) pour les répartir sur deux classes.

Cordialement,
Laurent

Si tu as environ la moitié des germanistes qui font du latin, tu les mets en A, les autres en B et tu as réduit la complexité de ton pb d'un facteur 4E6 :ccool:
En construisant des groupes par option, tu te ramènes dans un premier temps à un pb de sac-à-dos de petite dimension que tu peux gérer de façon combinatoire, et affiner dans un deuxième temps pour satisfaire les autres conditions.

Citation:

---

Envoyé par Nebulix

Si tu as environ la moitié des germanistes qui font du latin, tu les mets en A, les autres en B et tu as réduit la complexité de ton pb d'un facteur 4E6 :ccool:
En construisant des groupes par option, tu te ramènes dans un premier temps à un pb de sac-à-dos de petite dimension que tu peux gérer de façon combinatoire, et affiner dans un deuxième temps pour satisfaire les autres conditions.

---

Réponse un peu tardive
Comme je l'ai dis plus haut ceci n'est qu'un exemple. Je cherche, non pas à résoudre cet exemple, mais les situations de ce type (qui peuvent être très différentes)

Merci quand même

Cordialement
Laurent