The knapsack problem
Formulate and solve a simple knapsack problem:
max sum(p_j x_j)
st sum(w_j x_j) <= C
x binary
using JuMP
import HiGHS
import Test
function example_knapsack(; verbose = true)
profit = [5, 3, 2, 7, 4]
weight = [2, 8, 4, 2, 5]
capacity = 10
model = Model(HiGHS.Optimizer)
@variable(model, x[1:5], Bin)
# Objective: maximize profit
@objective(model, Max, profit' * x)
# Constraint: can carry all
@constraint(model, weight' * x <= capacity)
# Solve problem using MIP solver
optimize!(model)
if verbose
println("Objective is: ", objective_value(model))
println("Solution is:")
for i in 1:5
print("x[$i] = ", value(x[i]))
println(", p[$i]/w[$i] = ", profit[i] / weight[i])
end
end
Test.@test termination_status(model) == OPTIMAL
Test.@test primal_status(model) == FEASIBLE_POINT
Test.@test objective_value(model) == 16.0
return
end
example_knapsack()
Presolving model
1 rows, 5 cols, 5 nonzeros
1 rows, 4 cols, 4 nonzeros
Objective function is integral with scale 1
Solving MIP model with:
1 rows
4 cols (4 binary, 0 integer, 0 implied int., 0 continuous)
4 nonzeros
( 0.0s) Starting symmetry detection
( 0.0s) No symmetry present
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 18 -inf inf 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound 16
Dual bound 16
Gap 0% (tolerance: 0.01%)
Solution status feasible
16 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 1 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
Objective is: 16.0
Solution is:
x[1] = 1.0, p[1]/w[1] = 2.5
x[2] = 0.0, p[2]/w[2] = 0.375
x[3] = -0.0, p[3]/w[3] = 0.5
x[4] = 1.0, p[4]/w[4] = 3.5
x[5] = 1.0, p[5]/w[5] = 0.8
This tutorial was generated using Literate.jl. View the source .jl
file on GitHub.