HLPL / VerTeX Modelling Language Documentation

← lessons

Assignment — one-to-one

Both directions of the matching.

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

---

Add the symmetric constraint: each job is taken by exactly one worker. Now the solver has to spread the workers across jobs — a proper assignment.

With the same cost matrix as before, the optimum jumps from 6 to 13 because no two workers can share a job.

Predict before running

Add column constraints too. Each job goes to exactly one worker. Cost?

• Higher than the row-only optimum (some workers forced off their cheapest)
• Same as row-only
• Lower (more constraints help)

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
# TODO: add a constraint forcing each job to exactly one worker
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

Add: constr sum_{i in I}{x_{i,j}} = 1, forall j in J

What counts as correct

• no-error — Model solves
• numeric-match — Cheapest one-to-one assignment costs 13
• code-contains — Reads the objective from the solver (no hardcoding)

Solution

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

Mastery variant

A different matrix where the diagonal is cheap. The optimum is the perfect diagonal.

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