Най-доброто решение при ограничения и обяснението, когато такова няма

График на екип за една седмица

Трима души, пет дни, поне двама присъстващи всеки ден, най-много четири дни за всеки, Алис отсъства в сряда. Търсим графика, който използва най-малко дни общо.

$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]

Резултат, получен на сървъра: оптимален график от 10 човекодни, двама души всеки ден, Алис отсъства в сряда.

Разпределение на доставките

Всяка поръчка трябва да бъде доставена веднъж, всеки куриер поема най-много две поръчки. Като заменим целта със сумата от разстоянията между куриери и клиенти, същият модел се превръща в оптимизация на маршрути.

$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}")]]]

Резултат, получен на сървъра: четирите поръчки са разпределени, никой куриер не надхвърля две, статус OPTIMAL.

Работа на обект: техници и превозно средство

Монтажът изисква техник и превозното средство, изпитването изисква техник и може да започне само след монтажа. Всеки ресурс върши само едно нещо в даден момент. Искаме да приключим възможно най-рано.

[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]

Резултат, получен на сървъра: монтаж от 0 до 240 минути, изпитване от 240-ата, край на работата на 300-ата минута, оптимално решение.

Когато няма решение: откриване на конфликта

Производствена цел, която не може да бъде постигната с наличния капацитет. Решателят не просто казва не: той изолира най-малкия набор от несъвместими ограничения, за да знае ръководителят кое да предоговори.

[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]

Резултат, получен на сървъра: конфликт между три ограничения, поискания обем и двата капацитета; премахването на което и да е от тях прави задачата решима.

Маршрути на техници по поддръжка

Казус от поддръжката на котли: пет посещения, които трябва да се разпределят между техници според квалификацията им, часовите им интервали и района им. Моделът съдържа 20 решения, 13 строги ограничения и 3 претеглени предпочитания.

[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]]
  ...]

Документиран резултат: оптимално решение за 0,04 секунди, всичките пет посещения в района на техника. Версията, която минимизира реалните километри по адресите, достига 32 км за целия автопарк.

Описване на задачата на обикновен език

За първа чернова задачата може да бъде описана на естествен език. Езиковият модел пише модела, който може да бъде прегледан, а след това решателят го решава. Допълнително намерение се добавя по същия начин.

[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]