Knapsack

The Knapsack Problem is a classic combinatorial optimization problem that has been extensively studied in computer science and operations research.

We start with some instances of the discrete Knapsack Problem whose standard formulation is

\[\begin{array}{r l} \max & \mathbf{c}\, \mathbf{x} \\ \text{s.t.} & \mathbf{w}\, \mathbf{x} \le C \\ ~ & \mathbf{x} \in \mathbb{B}^{n} \end{array}\]

First, consider the following items

to be carried in a knapsack with capacity $C = 1.6$.

Writing down the data above as a linear program, we have

\[\begin{array}{r l} \max & x_{1} + 2 x_{2} + 3 x_{3} \\ \text{s.t.} & 0.3 x_{1} + 0.5 x_{2} + x_{3} \le 1.6 \\ ~ & \mathbf{x} \in \mathbb{B}^{3} \end{array}\]

Simple JuMP Model

Writing this in JuMP we end up with

using JuMP
using ToQUBO
using PySA

model = Model(() -> ToQUBO.Optimizer(PySA.Optimizer))

@variable(model, x[1:3], Bin)
@objective(model, Max, x[1] + 2 * x[2] + 3 * x[3])
@constraint(model, 0.3 * x[1] + 0.5 * x[2] + x[3] ≤ 1.6)

optimize!(model)

solution_summary(model)

solution_summary(; result = 1, verbose = false)
├ solver_name          : Virtual QUBO Model
├ Termination
│ ├ termination_status : LOCALLY_SOLVED
│ ├ result_count       : 3
│ └ raw_status         : 
├ Solution (result = 1)
│ ├ primal_status        : FEASIBLE_POINT
│ ├ dual_status          : NO_SOLUTION
│ └ objective_value      : 5.00000e+00
└ Work counters
  └ solve_time (sec)   : 3.33592e-03

The final decision is to take items $2$ and $3$, i.e., $x_{1} = 0, x_{2} = 1, x_{3} = 1$.

value.(x)

3-element Vector{Float64}:
 0.0
 1.0
 1.0

Using DataFrames

Now, lets fill a few more knapsacks. First, we generate uniform random costs $\mathbf{c}$ and weights $\mathbf{w}$ then set the knapsack's capacity $C$ to be a fraction of the total available weight i.e. $80\%$.

This example was inspired by D-Wave's knapsack example repository.

using CSV
using DataFrames

df = CSV.read("knapsack.csv", DataFrame)

using JuMP
using ToQUBO
using PySA

model = Model(() -> ToQUBO.Optimizer(PySA.Optimizer))

n = size(df, 1)
c = collect(Float64, df[!, :cost])
w = collect(Float64, df[!, :weight])
C = round(0.8 * sum(w))

@variable(model, x[1:n], Bin)
@objective(model, Max, c' * x)
@constraint(model, w' * x <= C)

optimize!(model)

# Add Results as a new column
df[:,:select] = map(xi -> ifelse(xi > 0, "✅", "❌"), value.(x))

df

Checking Capacity

println("Total weight : $(w' * value.(x)) / $(C)")

Total weight : 356.0 / 362.0