La meilleure décision sous contraintes, et l'explication quand il n'y en a pas

Planning d'équipe sur une semaine

Trois personnes, cinq jours, au moins deux présents chaque jour, au plus quatre jours chacun, Alice absente le mercredi. On cherche le planning qui mobilise le moins de jours au total.

$jours  = [list "lun" "mar" "mer" "jeu" "ven"]
$equipe = [list "alice" "bob" "carol"]
[optimize:problem Roulement
  [for $e $equipe [for $j $jours
    [decision "w_${e}_${j}" Integer [min 0] [max 1]]]]
  [for $j $jours
    [assert ([sum $e $equipe "w_${e}_${j}"] >= 2)]]     # au moins deux présents
  [for $e $equipe
    [assert ([sum $j $jours "w_${e}_${j}"] <= 4)]]     # quatre jours au plus
  [assert ($w_alice_mer == 0)]                         # Alice absente mercredi
  [minimize [sum $e $equipe [sum $j $jours "w_${e}_${j}"]]]]
[optimize:solve Roulement]

Résultat obtenu sur le serveur : planning optimal de 10 jours-personnes, deux personnes chaque jour, Alice absente le mercredi.

Affectation des livraisons

Chaque commande doit être livrée une fois, chaque livreur prend au plus deux commandes. En remplaçant l'objectif par la somme des distances entre livreurs et clients, le même modèle devient une optimisation de tournée.

$livreurs  = [list "L1" "L2" "L3"]
$commandes = [list "C1" "C2" "C3" "C4"]
[optimize:problem Tournees
  [for $l $livreurs [for $c $commandes
    [decision "x_${l}_${c}" Integer [min 0] [max 1]]]]
  [for $c $commandes
    [assert ([sum $l $livreurs "x_${l}_${c}"] == 1)]]   # chaque commande servie une fois
  [for $l $livreurs
    [assert ([sum $c $commandes "x_${l}_${c}"] <= 2)]]  # capacité par livreur
  [minimize [sum $l $livreurs [sum $c $commandes "x_${l}_${c}"]]]]
[optimize:solve Tournees]

# variante tournée : minimiser les kilomètres
# [minimize [sum $l $livreurs [sum $c $commandes
#     ([geo:distance "${l}" "${c}"] * "x_${l}_${c}")]]]

Résultat obtenu sur le serveur : les quatre commandes affectées, aucun livreur au-delà de deux, statut OPTIMAL.

Intervention de chantier : techniciens et véhicule

La pose demande un technicien et le véhicule, le test demande un technicien et ne peut commencer qu'après la pose. Chaque ressource ne fait qu'une chose à la fois. On cherche à terminer au plus tôt.

[planning:problem Chantier
  [horizon 0 480]
  [resource "tech_thomas" [kind "technician"]]
  [resource "tech_sarah"  [kind "technician"]]
  [resource "utilitaire"  [kind "vehicle"]]
  [task "pose" [duration 240]]
  [task "test" [duration 60]]
  [on-resource-group "pose" "installer" [resources "tech_thomas" "tech_sarah"]]
  [on-resource-group "pose" "vehicle"   [resources "utilitaire"]]
  [on-resource-group "test" "installer" [resources "tech_thomas" "tech_sarah"]]
  [no-overlap-resource "tech_thomas"]
  [no-overlap-resource "tech_sarah"]
  [no-overlap-resource "utilitaire"]
  [precedence "pose" "test"]
  [objective minimize-makespan]]
[optimize:solve Chantier]

Résultat obtenu sur le serveur : pose de 0 à 240 minutes, test à partir de 240, fin des travaux à 300 minutes, solution optimale.

Quand il n'y a pas de solution : trouver le conflit

Un objectif de production impossible à tenir avec les capacités disponibles. Le solveur ne se contente pas de dire non : il isole le plus petit ensemble de contraintes incompatibles, pour que le responsable sache laquelle renégocier.

[optimize:problem Objectif
  [decision $a Integer [min 0] [max 10]]
  [decision $b Integer [min 0] [max 10]]
  [assert (($a + $b) >= 15)]     # volume demandé
  [assert ($a <= 3)]              # capacité de la ligne A
  [assert ($b <= 4)]              # capacité de la ligne B
  [maximize ($a + $b)]]
[optimize:solve Objectif]           # no solution (status=INFEASIBLE)
[optimize:why-infeasible Objectif]

Résultat obtenu sur le serveur : conflit entre trois contraintes, le volume demandé et les deux capacités ; en retirer une seule rend le problème faisable.

Tournées de techniciens de maintenance

Cas d'étude de maintenance de chaudières : cinq visites à répartir entre techniciens selon leurs qualifications, leurs créneaux et leur zone. Le modèle compte 20 décisions, 13 contraintes strictes et 3 préférences pondérées.

[optimize:problem HeatRoute
  [decision $A_c1_s1 Integer [min 0] [max 1]]    # visite c1, technicien A, créneau s1
  [assert (($A_c1_s1 + $A_c1_s2 + $B_c1_s1 + $B_c1_s2) == 1)]
  [assert (($A_c1_s1 + $A_c3_s1) <= 1)]           # A ne fait qu'une visite par créneau
  [maximize ((10 * $A_c1_s1) + (10 * $A_c1_s2) ...)]
  [soft (($A_c1_s1 + $A_c3_s1) >= 1) [weight 0.3]]
  ...]

Résultat documenté : solution optimale en 0,04 seconde, les cinq visites dans la zone du technicien. La version qui minimise les kilomètres réels, à partir des adresses, aboutit à 32 km pour toute la flotte.

Décrire le problème en français

Pour un premier jet, le problème peut être décrit en langage naturel. Le modèle de langage écrit le modèle, que l'on peut relire, puis le solveur le résout. Une intention supplémentaire s'ajoute de la même façon.

[optimize "Une équipe de trois personnes, Alice, Bob et Carol, doit assurer la présence pendant deux jours. Chaque jour il faut au moins deux personnes au poste. Alice ne peut travailler qu'un seul jour. On veut minimiser le nombre total de jours travaillés." "Planning"]
[print [optimize:code Planning]]                           # le modèle généré, lisible
$sol = [optimize:solve Planning]
[intent "Alice doit travailler au moins un jour" "Planning"]
$sol2 = [optimize:solve Planning]