HLPL / VerTeX Modelling Language Documentation

← lessons

Assignment — extra workers

When the matching is uneven.

Chapter: VII — Assignment · lesson id assignment-unbalanced · practice lesson

---

Real assignments aren't always square. With four workers and three jobs, one worker has to sit out. The trick: relax the per-worker constraint from = 1 to ≤ 1, while keeping each job at = 1.

Worker 3 has a brutal cost row [3, 8, 9] and gets dropped. Total cost: 9.

Predict before running

Four workers, three jobs — one must sit out. Cost rows W1=[1,5,6], W2=[2,4,7], W3=[3,8,9], W4=[5,2,4]. Which worker is least useful?

• W3 — dominated on every job
• W1 — it is cheap everywhere
• Any of them. The solver picks arbitrarily

Starter code

model assign
set I = {1, 2, 3, 4}
set J = {1, 2, 3}
const c = {{1, 5, 6}, {2, 4, 7}, {3, 8, 9}, {5, 2, 4}}, forall i in I, forall j in J
bin x, forall i in I, forall j in J
constr sum_{j in J}{x_{i,j}} <= 1, forall i in I
constr sum_{i in I}{x_{i,j}} = 1, forall j in J
min sum_{i in I}{sum_{j in J}{c_{i,j} * x_{i,j}}}
end

import elytica
def main():
  elytica.init_model("assign")
  elytica.run_model("assign")
  for i in [1,2,3,4]:
    for j in [1,2,3]:
      name = "x"+str(i)+","+str(j)
      print(name, "=", elytica.get_variable_value("assign", name))
  print("obj =", elytica.get_best_primal_bound("assign"))
  return 0

Hint

sum_{j in J}{x_{i,j}} <= 1 (≤ 1, not = 1) lets a worker stay idle.

What counts as correct

• no-error — Model solves
• numeric-match — Cheapest assignment is 9 (W3 sits out)
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

Another over-supplied lineup. Which worker gets benched this time?

model assign_v
set I = {1, 2, 3, 4}
set J = {1, 2, 3}
const c = {{2, 4, 5}, {3, 1, 6}, {7, 8, 9}, {5, 4, 2}}, forall i in I, forall j in J
bin x, forall i in I, forall j in J
constr sum_{j in J}{x_{i,j}} <= 1, forall i in I
constr sum_{i in I}{x_{i,j}} = 1, forall j in J
min sum_{i in I}{sum_{j in J}{c_{i,j} * x_{i,j}}}
end

import elytica
def main():
  elytica.init_model("assign_v")
  elytica.run_model("assign_v")
  for i in [1,2,3,4]:
    for j in [1,2,3]:
      name = "x"+str(i)+","+str(j)
      print(name, "=", elytica.get_variable_value("assign_v", name))
  print("obj =", elytica.get_best_primal_bound("assign_v"))
  return 0

Read this through MCP: read with path: "lessons/assignment-unbalanced", or resource hlpl://lessons/assignment-unbalanced.