Considérons une problématique tout à fait actuelle :
Il faut un algorithme qui associe les personnes infectées et les hôpitaux en fonction de plusieurs critères tels que la gravité de la maladie, l’âge et l’emplacement du patient, la capacité et l’équipement des hôpitaux, etc.
Fig. 1. Carte de la pandémie, réduite à 4 paramètres : localisation et gravité des patients, localisation et capacité des hôpitaux.
Il est possible de penser qu’un réseau de neurones conviendrait parfaitement à ce problème: des configurations différentes sur beaucoup de paramètres qui doivent être réduits à une solution unique et optimale.
Cependant, certains inconvénients compromettent une telle approche:
En revanche, en formulant le problème sous forme de satisfiabilité booléenne, la situation n’aurait aucun des inconvénients susmentionnés tout en donnant une solution sous-optimale en temps polynomial et non déterministe (problème NP-complet), et sans la nécessité de devoir regroupes un jeu de données historiques.
La carte de la pandémie (1) illustre les résultats de notre algorithme qui associera les personnes infectées aux hôpitaux. Il existe plusieurs frameworks pour la résolution des contraintes. Google Optimization Tools (a.k.a., OR-Tools) est une suite logicielle open source pour résoudre les problèmes d’optimisation combinatoire. Notre problème sera modélisé en utilisant ce framework en Python.
from ortools.sat.python import cp_model
Un notebook complet pour ce prolbème peut-être trouvé ici.
Pour le moment, simplifions le problème à 4 paramètres:
Définissions ces paramètres en python:
# Number of hospitals
n_hospitals = 3
# Number of infected people
n_patients = 200
# Number of beds in every hospital
n_beds_in_hospitals = [30,50,20]
# Location of infected people -- random integer tuple (x,y)
patients_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_patients)]
# Location of hospitals -- random integer tuple (x,y)
hospitals_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_hospitals)]
# Illness severity -- 1 = mild -> 5 = severe
patients_severity = [randint(1, 5) for _ in range(n_patients)]
Un problème de satisfaction des contraintes consiste en un ensemble de variables auxquelles des valeurs doivent être affectées de manière à ce qu’un ensemble de contraintes soit satisfait.
Nous pouvons définir notre série de variables:
Si dans l’hôpital i, le lit j est pris par la personne k alors xᵢⱼₖ = 1.
Nous pouvons ajouter ces variables à notre modèle:
model = cp_model.CpModel()
x = {}
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
x[(i,j,k)] = model.NewBoolVar("x(%d,%d,%d)" % (i,j,k))
Concentrons-nous sur la première contrainte. Pour chaque lit j dans chaque hôpital i :
Par conséquent, la contrainte est exprimable de la façon suivante:
Notre solveur fait de l’optimisation combinatoire, il ne peut traiter que des contraintes sur des nombres entiers. Par conséquent, l’expression de la contrainte doit être formulée de la façon suivante :
Cette inégalité peut être ajoutée à notre modèle.
# Each bed must host at most one person
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
model.Add(sum(x[(i,j,k)] for k in range(n_patients)) <= 1)
Ensuite, traitons la seconde contrainte pour chaque patient k:
De la même façon, cette contrainte est exprimable sous la forme d’une inéquation :
Finalement, il est possible de l’ajouter au modèle.
# Each person must be placed in at most one bed
for k in range(n_patients):
inner_sum = []
for i in range(n_hospitals):
inner_sum.append(sum(x[(i,j,k)] for j in range(n_beds_in_hospitals[i])))
model.Add(sum(inner_sum) <= 1)
Viennent ensuite les contraintes douces. Notre solution doit essayer de les satisfaire au maximum, mais elles ne sont pas indispensables pour trouver une solution:
Alors que les contraintes dures sont modélisées comme des égalités ou des inégalités, les contraintes souples sont des expressions à minimiser ou maximiser.
Soit Ω l’ensemble de toutes les solutions qui satisfont aux contraintes dures.“Chaque personne malade doit être placée dans un lit” peut être traduit en “maximiser le nombre de lits occupés”.
“Chaque personne doit être prise en charge par l’hôpital le plus proche” peut être traduit en “minimiser la distance entre chaque patient et l’hôpital qui lui est affecté”.
“Les personnes malades dans un état grave doivent être traitées en premier lorsqu’il n’y a pas suffisamment de lits” peut être traduit en “maximiser la gravité totale de tous les patients pris en charge”. En désignant sev (k) la gravité du patient k :
Nous pouvons réduire toutes ces contraintes en un seul objectif :
Il faut alors être prudent: ces contraintes souples n’ont pas toutes le même domaine de définition.
Étant donné que toutes ces contraintes partagent la même priorité, nous devons définir des facteurs de pénalité pour équilibrer les différentes contraintes.
Voici le code correspondant:
# Integer distance function
idist = lambda xy1, xy2: int(((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5)# Gain factors (1/penalty factors)
gain_max_patients = 140
gain_severity = int(140/5)
gain_distance = -1# Maximization objective
soft_csts = []
for i in range(n_hospitals):
for j in range(n_beds_in_hospitals[i]):
for k in range(n_patients):
factor = \
gain_max_patients \
+ gain_distance * idist(hospitals_loc[i], patients_loc[k]) \
+ gain_severity * patients_severity[k]
soft_csts.append(factor * x[(i,j,k)])model.Maximize(sum(soft_csts))
Nous pouvons maintenant lancer le solveur. Il essaiera de trouver la solution optimale dans un délai spécifié. S’il ne parvient pas à trouver la solution optimale, il renverra la solution sous-optimale la plus proche.
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60.0
status = solver.Solve(model)
Dans notre cas, le solveur renvoie une solution optimale en 2,5 secondes (2).
Cette solution ne demande pas beaucoup de temps afin d’être conçue et implémentée.
Pour une solution équivalente en Deep Learning, le temps de conception est au moins multiplié par 10 avec le tri des données, le choix de l’architecture et l’entraînement du modèle.
De plus, un modèle CP-SAT tel que celui-ci est très robuste s’il est bien modélisé. Voici les résultats avec différents paramètres de simulation (3). Les résultats sont toujours cohérents dans de nombreux cas différents, et en augmentannt les paramètres de simulation (3000 patients, 1000 lits), l’inférence d’une solution a pris un peu moins de 3 minutes.
Fig. 3: Différents paramètres de simulation
Bien sûr, les solveurs de contraintes ne s’appliquent guère à des sujets comme la vision par ordinateur et le traîtement du langage, dans lesquels le Deep Learning est souvent la meilleure approche. Cependant, en matière de logistique, d’ordonnancement et de planification, ces solveurs restent dans la plupart des cas la voie à suivre.