PROSuite

Research · Optimization & planning

The best decision under constraints, and the explanation when there is none

Staff schedules, technician routes, delivery assignment, material cutting, production mix: these decisions have a best answer, which can be computed. VVL lets you describe them in a few lines and hands them to a constraint solver. The language model can help write the model, but the solution is computed, not guessed.

How it works

A problem is declared with four elements: the decisions to make and their bounds, the constraints that must be met, the preferences that can be traded off with a weight, and the objective to maximise or minimise. VVL compiles this description for Google OR-Tools' CP-SAT solver.

[optimize:problem "prod"
  [decision $x Integer [min 0] [max 10]]
  [decision $y Integer [min 0] [max 10]]
  [assert (($x + $y) <= 12)]          # capacité totale de l'atelier
  [maximize ((3 * $x) + (5 * $y))]]   # marge à maximiser

[optimize:solve "prod" [time_limit 5] [backend "cp-sat"]]

Result obtained on the server: x = 2, y = 10, status OPTIMAL, margin 56.

The language provides tools around the solver: model validation, explanation, code generation, a natural-language report and, above all, a diagnosis when the problem has no solution. A planning layer adds business notions: horizon, resources, tasks, durations, precedences, resources that cannot do two things at once. Geolocation functions provide distances between addresses for routing.

No language-model call is made during solving. The model only comes in if you choose to describe the problem in plain language, or to add an intention in natural language, and its output is cached.

Business examples

A week's staff schedule

Three people, five days, at least two present each day, at most four days each, Alice away on Wednesday. We look for the schedule that uses the fewest days in 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]

Result obtained on the server: an optimal schedule of 10 person-days, two people every day, Alice away on Wednesday.

Delivery assignment

Each order must be delivered once, each driver takes at most two orders. By replacing the objective with the sum of distances between drivers and customers, the same model becomes a route optimization.

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

Result obtained on the server: all four orders assigned, no driver above two, status OPTIMAL.

Site job: technicians and a vehicle

Installation needs a technician and the vehicle; testing needs a technician and can only start after installation. Each resource does one thing at a time. We want to finish as early as possible.

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

Result obtained on the server: installation from 0 to 240 minutes, testing from 240, work finished at 300 minutes, optimal solution.

When there is no solution: finding the conflict

A production target that cannot be met with the available capacity. The solver does not just say no: it isolates the smallest set of incompatible constraints, so that the manager knows which one to renegotiate.

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

Result obtained on the server: a conflict between three constraints, the requested volume and the two capacities; removing any one of them makes the problem feasible.

Maintenance technician routes

A boiler-maintenance case study: five visits to distribute among technicians according to their skills, their time slots and their area. The model has 20 decisions, 13 hard constraints and 3 weighted preferences.

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

Documented result: optimal solution in 0.04 seconds, all five visits in the technician's area. The version that minimises real kilometres, from the addresses, reaches 32 km for the whole fleet.

Describing the problem in plain language

For a first draft, the problem can be described in natural language. The language model writes the model, which you can review, then the solver solves it. An additional intention is added the same way.

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

What it guarantees, and its limits

  • A solution reported as optimal is optimal for the model described: it is a proof from the solver, not an estimate.
  • An infeasibility is explained by the minimal set of conflicting constraints.
  • The model stays readable and versionable, even when it was written by the language model.
  • Models are linear: products of two decisions, divisions and powers are not accepted, and a typo in a keyword is reported rather than ignored.

Apply this work to your processes?

The diagnosis starts from how you actually work and identifies the decisions that can be entrusted to AI.

Get my assessment