Résoudre un problème complexe à l’aide d’un engin de résolution mathématique

Parmi les nombreux projets sur lesquels nous avons eu à travailler cette année, il y a eu l’optimisation des affectations de stages des étudiants d’une faculté de pharmacie.

Problème

Plusieurs centaines d’étudiants inscrits aux cours ont besoin de ces périodes d’études pratiques. Ils doivent ainsi faire des stages dans des établissements où ils sont supervisés par un pharmacien.

Les requis pour l’affectation

• La liste des étudiants.
• Les cours auxquels les étudiants sont inscrits.
• Les périodes (dans notre cas, une période, c’est une semaine).
• Les villes où se tient le stage, avec leur distance par rapport à l’université.
• Les préférences de régions des étudiants.
• Les différents types d’établissements.
• Les pharmaciens disponibles (des disponibilités par cours, par période et par trimestre).
• Les semaines de congé.
• Les conflits et les parcours non traditionnels.

Règles à respecter

En plus des requis, il y a certaines règles à respecter :

• Si un étudiant est en conflit avec un établissement, il ne peut y être assigné.
• Si un étudiant est en conflit avec un superviseur, il ne peut ni être avec ce superviseur ni dans aucun des établissements où il y travaille.
• Un superviseur ne peut avoir plus d’un stagiaire à la fois, sachant que ce superviseur peut être dans plus d’un établissement.
• Un étudiant ne peut être assigné au même établissement qu’un certain nombre de fois.
• Si un stage est déjà assigné manuellement, il faut en tenir compte.
• Un étudiant ne peut être assigné plus d’un certain nombre de fois à l’extérieur de la ville, à moins que ses préférences stipulent le contraire.
• Et autres contraintes spécifiques.

Le but de l’optimisation

Résoudre mathématiquement l’affectation des stages avec pour scénario 600 étudiants de plusieurs cohortes inscrits à plusieurs cours à la fois, avec un choix de 1 000 établissements auxquels des pharmaciens sont associés. Ce travail était fait par au moins une personne à temps plein, sans qu’on puisse garantir le respect de toutes les règles ni l’assurance d’une assignation optimale, d’où l’utilité de recourir à une solution de résolution mathématique qui permette de :

1. Placer le maximum d’étudiants possible, en respectant toutes les règles.
2. Proposer les meilleures solutions aux étudiants (plus optimales).

Solution

1. Modélisation des variables

On modélise le problème sous forme d’une matrice à plusieurs dimensions que « l’engin de résolution mathématique » est capable de lire, le nombre de variables de cette matrice pouvant se chiffrer en millions (chaque cellule de la matrice représente une variable dans le modèle).

Dans notre matrice, chacun des éléments suivants représente une dimension :

• Les étudiants.
• Les établissements et les pharmaciens.
• Les cours.
• Les semaines.

2. Modélisation des règles à respecter

Pour ce faire, on met en place un système où une valeur de « pénalité » est calculée pour chaque stage. Un stage dont les paramètres sont parfaits/idéaux a une valeur de 0, sinon, une pénalité plus ou moins élevée est appliquée, selon la qualité de l’affectation. Assigner un stage à un étudiant dans une ville hors de ses préférences est moins « grave » que d’avoir un stage non assigné.

Exemple : Placer un étudiant à sa 4e préférence occasionnerait une certaine pénalité. Le placer hors de ses préférences coûterait encore plus cher en pénalités, et ne pas le placer du tout, c’est ce qui coûte le plus. C’est pour ça qu’il faut toujours avantager d’abord le placement de tous les étudiants.

3. Prise en charge du modèle par l’engin de résolution

• L’engin commence par éliminer les combinaisons impossibles et sans intérêt pour réduire la taille du modèle.
• Il entame sa recherche de la solution optimale : il trouve plusieurs solutions, puis il recherche la meilleure option, celle qui donne un meilleur total de pénalités, jusqu’à l’obtention d’un taux de pénalité acceptable.

Il faut noter que le défi du programmeur est d’avoir un modèle facile à comprendre, le plus léger possible, afin de permettre de résoudre le plus rapidement possible le casse-tête des affectations.

Conclusion

Un modèle bien pensé avec le bon engin a permis au personnel de la faculté d’assigner plus de 1 000 stages en quelques heures, ce qui leur a également permis de faire des essais de placement et d’avoir le temps de s’ajuster où la disponibilité de stage venait à manquer, de pouvoir concentrer leurs efforts vers la gestion des cas particuliers et de passer plus de temps pour le suivi des stages.

—

[Illustration Ivan T, licence CC by 2.0.]