HLPL / VerTeX Modelling Language Documentation

← lessons

Assignment — workers pick jobs

One row constraint at a time.

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

---

Three workers, three jobs. Each cell c[i][j] is the cost of worker i doing job j. We'll build the model up over three lessons.

First constraint: each worker takes exactly one job. We say nothing yet about whether a job can be taken by multiple workers — so they'll all pile onto whichever job they each find cheapest.

In this cost matrix every worker's cheapest job is J1, so the solver assigns all three to J1. Not realistic — we'll fix that next.

Predict before running

Only row constraints (one job per worker), no column constraint. What happens?

• Every worker picks their cheapest column
• The solver spreads them across J1, J2, J3
• The model is infeasible

Starter code

model assign
set I = {1, 2, 3}
set J = {1, 2, 3}
const c = {{1, 5, 6}, {2, 4, 7}, {3, 8, 9}}, 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
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]:
    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

Each row of the matrix has its smallest entry in column 1. All workers pick J1.

What counts as correct

• no-error — Model solves
• numeric-match — All workers pick J1 (1+2+3 = 6)
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

New cost matrix — same trap (every row minimum is in the same column).

model assign_v
set I = {1, 2, 3}
set J = {1, 2, 3}
const c = {{4, 1, 6}, {3, 1, 5}, {7, 2, 9}}, 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
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]:
    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-rows", or resource hlpl://lessons/assignment-rows.