HLPL / VerTeX Modelling Language Documentation

← lessons

Knapsack — variables and objective

Start with the decisions.

Chapter: VI — Knapsack · lesson id knapsack-vars · practice lesson

---

The knapsack problem: you have items, each with a value and a weight. Your bag holds a fixed amount of weight. Pick items to maximise value.

We'll build it in three lessons. First step: just the variables and the objective. Each item gets a binary decision x_i — do we pick it or not? — and the objective sums values.

Run it. Without a capacity constraint, the solver picks everything.

Predict before running

Five binaries, no capacity, max 6*x1 + 4*x2 + 5*x3 + 3*x4 + 2*x5. What's the optimum?

• All five picked (obj = 20)
• Only the heavy hitters (obj = 11)
• None picked (obj = 0)

Starter code

model knap
bin x1
bin x2
bin x3
bin x4
bin x5
max 6*x1 + 4*x2 + 5*x3 + 3*x4 + 2*x5
end

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

Hint

Predict: with no constraint, what's the optimum? (Every item, sum of all values.)

What counts as correct

• no-error — Model solves
• numeric-match — Solver picks everything (obj = 6+4+5+3+2 = 20)
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

Six items, different values. Same trick: no capacity, all positive values pick.

model knap_v
bin x1
bin x2
bin x3
bin x4
bin x5
bin x6
max 7*x1 + 3*x2 + 8*x3 + 5*x4 + 2*x5 + 4*x6
end

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

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