HLPL / VerTeX Modelling Language Documentation

← lessons

Either / or via big-M

Disjunctions in linear models.

Chapter: V — Modelling tricks · lesson id either-or-bigm · practice lesson

---

Linear programmes can't natively express "either constraint A or constraint B". The classic trick: introduce a binary z and a large constant M, then write

A active when z = 0: lhs_A + M · z ≥ required B active when z = 1: lhs_B + M · [1 − z] ≥ required

When z = 0, A is binding and B is relaxed away by the huge M term; when z = 1, the opposite. The solver picks whichever side fits the objective better.

Two delivery options for the same shipment: truck (variable x₁) or ship (variable x₂). At least one must carry at least 5 units. Truck costs 3 per unit, ship costs 2. The model has to choose a single mode and minimise cost.

Note [ ] around 1 - z — the modelling language uses square brackets for algebraic grouping in expressions; parentheses are reserved for function calls.

Predict before running

Truck costs 3/unit, ship costs 2/unit. Which side does the disjunction pick?

• Truck (z = 0, x₁ = 5)
• Ship (z = 1, x₂ = 5)
• Split (some of each)

Starter code

model either_or
var 0 <= x1 <= 10      # units carried by truck
var 0 <= x2 <= 10      # units carried by ship
bin z                   # 0 = truck side, 1 = ship side
constr x1 + 100*z       >= 5   # if z = 0, truck must carry >= 5
constr x2 + 100*[1 - z] >= 5   # if z = 1, ship must carry >= 5
min 3*x1 + 2*x2
end

import elytica
def main():
  elytica.init_model("either_or")
  elytica.run_model("either_or")
  print("x1 =", elytica.get_variable_value("either_or", "x1"))
  print("x2 =", elytica.get_variable_value("either_or", "x2"))
  print("z =", elytica.get_variable_value("either_or", "z"))
  print("obj =", elytica.get_best_primal_bound("either_or"))
  return 0

Hint

Predict: ship is cheaper. The solver picks z = 1, x₁ = 0, x₂ = 5, cost 10.

What counts as correct

• no-error — Model solves
• numeric-match — Truck side stays at 0 (more expensive)
• numeric-match — Ship side carries exactly the required 5 units
• numeric-match — Selector z = 1 (ship side chosen)
• numeric-match — Cost is 10 (5 units × $2 ship)
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Mastery variant

Bus vs train this time, with a different required volume. Which mode wins?

model either_or_v
var 0 <= x1 <= 20      # units on the bus
var 0 <= x2 <= 20      # units on the train
bin z                   # 0 = bus, 1 = train
constr x1 + 200*z       >= 8
constr x2 + 200*[1 - z] >= 8
min 3*x1 + 4*x2
end

import elytica
def main():
  elytica.init_model("either_or_v")
  elytica.run_model("either_or_v")
  print("x1 =", elytica.get_variable_value("either_or_v", "x1"))
  print("x2 =", elytica.get_variable_value("either_or_v", "x2"))
  print("z =", elytica.get_variable_value("either_or_v", "z"))
  print("obj =", elytica.get_best_primal_bound("either_or_v"))
  return 0

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