Skip to content
Become a partner
Research · Optimisation & scheduling

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

Team rotas, technician rounds, delivery assignment, material cutting, production mix: these decisions have a best answer, and it 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

Four elements, one solver

A problem is declared with four elements: the decisions to be made and their bounds, the constraints that must be met without exception, the preferences that may be sacrificed at a weighted cost, and the objective to maximise or minimise. VVL compiles this description for the CP-SAT solver of Google OR-Tools.

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 scheduling layer adds business concepts: horizon, resources, tasks, durations, precedences, resources that cannot do two things at once. Geolocation functions supply the distances between addresses for rounds.

No call to the language model during solving.

optimize:problemVVL
[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.

Business examples

Rotas, rounds, worksites

A team rota over one week

Three people, five days, at least two present each day, at most four days each, Alice absent on Wednesday. We look for the rota that uses the fewest days in total.

Result obtained on the server: an optimal rota of 10 person-days, two people each day, Alice absent on Wednesday.

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

Assigning deliveries

Each order must be delivered once, and each courier takes at most two orders. By replacing the objective with the sum of the distances between couriers and customers, the same model becomes a round optimisation.

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

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

Technicians, vehicle, precedences

The install requires a technician and the vehicle; the test requires a technician and cannot start until the install is done. Each resource does only one thing at a time. The aim is to finish as early as possible.

060120180240300360420480MINUTES · HORIZON 0 → 480TechnicianinstalltestVaninstallwork complete: 300 min · optimal
Precedence install → test, only one task at a time per resource.
planning:problemVVL
[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: install from 0 to 240 minutes, test from 240, work complete at 300 minutes, optimal solution.

Maintenance technician rounds

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

Documented result: optimal solution in 0.04 seconds, all five visits within the technician's area. The version that minimises actual kilometres, based on the addresses, arrives at 32 km for the whole fleet.

When there is no solution

Finding the conflict, not just saying no

A production target that cannot be met with the available capacities. The solver isolates the smallest set of incompatible constraints, so that the manager knows which one to renegotiate.

00224466881010capacitiesvolumeno common pointaba + b ≥ 15requested volumea ≤ 3line A capacityb ≤ 4line B capacity[optimize:why-infeasible]the smallest conflicting set

Diagnosing the conflict

The requested volume exceeds the sum of the two capacities: no combination holds.

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

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

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, and then the solver solves it. An additional intention is added in the same way.

in natural languageVVL
[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]
Guarantees

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 remains readable and can be versioned, including 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.
Putting it into practice

Apply this work to your processes?

These tools are instructions of the VVL language: our partners deploy them for their clients, on the ProSuite platforms.

Become a partner All topics