Multiple Knapsack

Setup

Mix.install([
  {:exhort, git: "https://github.com/elixir-or-tools/exhort"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"}
])

use Exhort.SAT.Builder
alias VegaLite, as: Vl

Model

weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
num_items = length(weights)
bin_capacities = [100, 100, 100, 100, 100]
num_bins = length(bin_capacities)
all_items = Range.new(0, num_items - 1)
all_bins = Range.new(0, num_bins - 1)

{all_items, all_bins}

x =
  for idx <- all_items, b <- all_bins do
    {{idx, b}, Expr.def_int_var("x_#{idx}_#{b}", {0, 1})}
  end
  |> Enum.into(%{})

max_value = Enum.sum(values)

value[b] is the value of bin b when packed.

value =
  for b <- all_bins do
    {b, Expr.def_int_var("value_#{b}", {0, max_value})}
  end
  |> Enum.into(%{})

value_constraints =
  for b <- all_bins do
    Expr.new(value[b] == sum(for i <- all_items, do: x[{i, b}] * Enum.at(values, i)))
  end

Constraints

Each item can be in at most one bin.

one_bin_per_item =
  for idx <- all_items do
    Expr.new(sum(for b <- all_bins, do: x[{idx, b}]) <= 1)
  end

The amount packed in each bin cannot exceed its capacity.

max_capacity_per_item =
  for b <- all_bins do
    Expr.new(
      sum(for i <- all_items, do: x[{i, b}] * Enum.at(weights, i)) <=
        Enum.at(bin_capacities, b)
    )
  end

builder =
  Builder.new()
  |> Builder.add(Map.values(x))
  |> Builder.add(Map.values(value))
  |> Builder.add(value_constraints)
  |> Builder.add(one_bin_per_item)
  |> Builder.add(max_capacity_per_item)
  |> Builder.maximize(sum(Map.values(value)))

response =
  builder
  |> Builder.build()
  |> Model.solve()

response
|> SolverResponse.stats()

Visualize

Create a table-like data structure for VegaLite

bin_items =
  for b <- all_bins, idx <- all_items do
    {b, idx}
  end
  |> Enum.filter(fn {b, idx} ->
    SolverResponse.value(response, x[{idx, b}]) > 0
  end)
  |> Enum.map(fn {b, idx} ->
    %{
      "bin" => b,
      "item" => idx,
      "weight" => Enum.at(weights, idx),
      "value" => Enum.at(values, idx)
    }
  end)

Vl.new(width: 650, height: 500)
|> Vl.data_from_values(bin_items)
|> Vl.encode_field(:x, "bin", type: :nominal)
|> Vl.encode_field(:y, "weight", aggregate: :sum, stack: "zero")
|> Vl.layers([
  Vl.new()
  |> Vl.mark(:bar)
  |> Vl.encode(:color, field: "item"),
  Vl.new()
  |> Vl.mark(:text, baseline: "bottom", fill: "black")
  |> Vl.encode_field(:text, "weight", type: :quantitative, aggregate: :sum)
  |> Vl.encode(:color, field: "item")
])