HLPL / VerTeX Modelling Language Documentation

← lessons

Facility location — with capacities

Each open facility has a limit.

Chapter: XIII — Facility location · lesson id facility-capacitated · practice lesson

---

Real facilities have throughput limits. Add capacity_j to each: the number of customers a facility can serve when it's open.

With capacity = {2, 1} and three customers, neither facility alone can cover everyone — both must open (cost 11). The tight cap on facility 2 forces facility 1 to absorb the two customers it's not the cheapest match for. Best assignment: facility 1 takes C₁ and C₂, facility 2 takes C₃. Total 11 + 2 + 3 + 2 = 18.

Predict before running

Capacity {2, 1} means F2 can take only one customer. Compared to uncapacitated (13), the new total is:

• Lower. Capacities help
• Higher. Both facilities forced open + suboptimal assignments
• Same. The assignment didn't change

Starter code

model facility
set F = {1, 2}
set C = {1, 2, 3}
const f = {5, 6}, forall j in F
const t = {{2, 4}, {3, 1}, {4, 2}}, forall i in C, forall j in F
const capacity = {2, 1}, forall j in F
bin y, forall j in F
bin x, forall i in C, forall j in F
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
constr x_{i,j} <= y_{j}, forall i in C, forall j in F
# TODO: a capacity constraint per facility
min sum_{j in F}{f_{j} * y_{j}} + sum_{i in C}{sum_{j in F}{t_{i,j} * x_{i,j}}}
end

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

Hint

Add: constr sum_{i in C}{x_{i,j}} <= capacity_{j}, forall j in F

What counts as correct

• no-error — Model solves
• numeric-match — Facility 1 must open
• numeric-match — Facility 2 must open
• numeric-match — Total cost is 18
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Solution

model facility
set F = {1, 2}
set C = {1, 2, 3}
const f = {5, 6}, forall j in F
const t = {{2, 4}, {3, 1}, {4, 2}}, forall i in C, forall j in F
const capacity = {2, 1}, forall j in F
bin y, forall j in F
bin x, forall i in C, forall j in F
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
constr x_{i,j} <= y_{j}, forall i in C, forall j in F
constr sum_{i in C}{x_{i,j}} <= capacity_{j}, forall j in F
min sum_{j in F}{f_{j} * y_{j}} + sum_{i in C}{sum_{j in F}{t_{i,j} * x_{i,j}}}
end

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

Mastery variant

Fresh costs and capacities. F₂ is the cheapest setup but the tightest cap.

model facility_v
set F = {1, 2}
set C = {1, 2, 3}
const f = {5, 4}, forall j in F
const t = {{4, 3}, {2, 6}, {7, 2}}, forall i in C, forall j in F
const capacity = {2, 1}, forall j in F
bin y, forall j in F
bin x, forall i in C, forall j in F
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
constr x_{i,j} <= y_{j}, forall i in C, forall j in F
constr sum_{i in C}{x_{i,j}} <= capacity_{j}, forall j in F
min sum_{j in F}{f_{j} * y_{j}} + sum_{i in C}{sum_{j in F}{t_{i,j} * x_{i,j}}}
end

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

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