This is one of 48 free optimization notebooks: the problem, the model with a note on every line, Python code and its real
output. You can open it in Google Colab and press Run, with nothing to install.
The problem
Five items have values 10, 13, 7, 8, 5 and weights 5, 6, 3, 4, 2. The knapsack holds weight 10. Which items maximize total value? Let t1, ..., t5 be 1 if item 1, ..., 5 is taken and 0 if not.
The model
Each line ends with a plain-language note (after #).
maximize 10*t1 + 13*t2 + 7*t3 + 8*t4 + 5*t5
subject to
5*t1 + 6*t2 + 3*t3 + 4*t4 + 2*t5 <= 10
binary: t1, t2, t3, t4, t5
# t1 = 1 if item 1 is taken, 0 otherwise (decision)
# t2 = 1 if item 2 is taken, 0 otherwise (decision)
# t3 = 1 if item 3 is taken, 0 otherwise (decision)
# t4 = 1 if item 4 is taken, 0 otherwise (decision)
# t5 = 1 if item 5 is taken, 0 otherwise (decision)
# objective = total value of the items in the knapsack (value units)
The code (cvxpy)
import cvxpy as cp
t1 = cp.Variable(name='t1', boolean=True) # 1 if item 1 is taken, 0 otherwise (decision)
t2 = cp.Variable(name='t2', boolean=True) # 1 if item 2 is taken, 0 otherwise (decision)
t3 = cp.Variable(name='t3', boolean=True) # 1 if item 3 is taken, 0 otherwise (decision)
t4 = cp.Variable(name='t4', boolean=True) # 1 if item 4 is taken, 0 otherwise (decision)
t5 = cp.Variable(name='t5', boolean=True) # 1 if item 5 is taken, 0 otherwise (decision)
objective = cp.Maximize(10*t1 + 13*t2 + 7*t3 + 8*t4 + 5*t5)
constraints = [
5*t1 + 6*t2 + 3*t3 + 4*t4 + 2*t5 <= 10,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('t1 =', t1.value)
print('t2 =', t2.value)
print('t3 =', t3.value)
print('t4 =', t4.value)
print('t5 =', t5.value)
Output, from running exactly this code:
optimal 22.0
t1 = 1.0
t2 = 0.0
t3 = 1.0
t4 = 0.0
t5 = 1.0
The checked answer
The largest objective value is 22, at t1 = 1, t2 = 0, t3 = 1, t4 = 0, t5 = 1. The constraint is satisfied (violation ≤0e+00). Optimal within gap tolerance.
Problem class: ILP; solver: HIGHS.
Run it yourself
- Open the notebook in Google Colab (free, in your browser)
- The step-by-step walkthrough and the proof of optimality
- All 48 notebooks (code MIT, text CC BY 4.0)
This article was written with AI assistance, from a template: every number in it is the solver's, from the run shown above.
Top comments (0)