defmodule CPSolver.Examples.BinPacking do
@moduledoc """
Bin Packing Problem Example
Given:
- n: items, each with weights w[i]
- b: max. bin capacity
The goal is to assign each item to a bin such that:
Sum of item weights in each bin <= capacity and the
number of bins used is minimized.
"""
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Model
alias CPSolver.Constraint.Sum
alias CPSolver.Constraint.{LessOrEqual, Channel}
import CPSolver.Variable.View.Factory
alias CPSolver.Objective
alias CPSolver.Examples.BinPacking.{Search, UpperBound}
require Logger
def solve(weights, capacity, opts \\ []) do
upper_bound =
Keyword.get(opts, :upper_bound, UpperBound.first_fit_decreasing(weights, capacity))
model = model(weights, capacity, upper_bound)
opts =
Keyword.merge(
[
search: model.search,
solution_handler: solution_handler(),
timeout: :timer.seconds(30),
upper_bound: upper_bound
],
opts
)
Logger.warning("Started")
Logger.warning("Upper bound: #{opts[:upper_bound]}")
CPSolver.solve(model, opts)
|> tap(fn {:ok, res} ->
if res.status not in [:unknown, :unsatisfiable] do
(check_solution(res, weights, capacity) && Logger.warning("Solution is valid")) ||
throw({:error, :invalid_solution})
else
Logger.error("No solution found")
end
end)
end
def minimization_model(item_weights, capacity, upper_bound \\ nil) do
item_weights = Enum.sort(item_weights, :desc)
min_weight = List.last(item_weights)
num_items = length(item_weights)
num_items_over_half_capacity = Enum.count(item_weights, fn w -> 2 * w > capacity end)
num_bins = upper_bound || num_items
lower_bound = max(num_items_over_half_capacity, ceil(Enum.sum(item_weights) / capacity))
# x[i][j] item i assigned to bin j
indicators =
for i <- 1..num_items do
item_over_half_capacity? = i <= num_items_over_half_capacity
for j <- 1..num_bins do
domain =
if item_over_half_capacity? do
(i == j && 1) || 0
else
0..1
end
Variable.new(domain, name: "item_#{i}_in_bin_#{j}")
end
end
total_bins_used =
Variable.new(lower_bound..num_bins,
name: "total_bins_used"
)
# indicators for bin: bin[i] is used iff bin_used[i] = 1
bin_used =
for i <- 1..num_bins do
## First `lower_bound` bins are to be used
##
d = (i <= lower_bound && 1) || 0..1
Variable.new(d, name: "bin_#{i}_used")
end
# total weight in bin i
bin_load =
for i <- 1..num_bins do
lb_cap = (i <= lower_bound && min_weight) || 0
Variable.new(lb_cap..capacity, name: "bin_load_#{i}")
end
###################
### Constraints ###
###################
upper_bound_constraint = LessOrEqual.new(total_bins_used, num_bins)
# item_indicator_constraints =
# Enum.map(indicators, fn inds ->
# Sum.new(1, inds)
# end)
x = Enum.map(1..num_items, fn idx -> Variable.new(1..num_bins, name: "x_#{idx}") end)
item_assignment_constraints =
for i <- 0..(num_items - 1) do
x_i = Enum.at(x, i)
bin_indicators = Enum.at(indicators, i)
## x[i] = j iff ind[i, j] = 1
Channel.new(x_i, bin_indicators)
end
bin_load_constraints =
Enum.with_index(bin_load)
|> Enum.map(fn {load_var, j} ->
views =
Enum.with_index(indicators)
|> Enum.map(fn {inds_for_item, i} ->
mul(Enum.at(inds_for_item, j), Enum.at(item_weights, i))
end)
Sum.new(load_var, views)
end)
capacity_constraints =
Enum.zip(bin_load, bin_used)
|> Enum.map(fn {load, used} ->
LessOrEqual.new(load, mul(used, capacity))
end)
total_bins_constraint =
Sum.new(total_bins_used, bin_used)
bin_load_sum_constraint = Sum.new(Enum.sum(item_weights), bin_load)
#####################################
### end of constraint definitions ###
#####################################
constraints =
[
upper_bound_constraint,
item_assignment_constraints,
# item_indicator_constraints,
bin_load_constraints,
capacity_constraints,
symmetry_breaking_constraints(bin_used, bin_load, num_bins, num_items_over_half_capacity),
total_bins_constraint,
bin_load_sum_constraint
]
vars =
[bin_used, total_bins_used, bin_load, indicators] |> List.flatten()
Model.new(
vars,
constraints,
objective: Objective.minimize(total_bins_used)
)
|> Map.put(:search,
## if lower_bound = upper_bound, we do not need an advanced strategy
## TODO: maybe even run linear BPP (`first_fit_decreasing` etc)
if lower_bound == num_bins do
{:first_fail, :indomain_max}
else
Search.cdbf(item_weights, x, bin_load, capacity)
end)
end
defp symmetry_breaking_constraints(bin_used, _bin_load, num_bins, _num_over_half_capacity) do
# Symmetry breaking
# 1. Only allow bin j to be used if all bins < j are used.
# This prevents the solver from seeing equivalent packings as different solutions.
used_bins_first =
Enum.map(0..(num_bins - 2), fn bin_idx ->
bin = Enum.at(bin_used, bin_idx)
next_bin = Enum.at(bin_used, bin_idx + 1)
LessOrEqual.new(next_bin, bin)
end)
## TODO: not being used, as it has varying performance effect across instances
# 2. Arrange bin loads in decreasing order
## (only for bins that do not have "over half capacity" items)
# decreasing_loads =
# if num_over_half_capacity + 1 >= num_bins - 1 do
# []
# else
# for i <- (num_over_half_capacity + 1)..num_bins - 1 do
# LessOrEqual.new(Enum.at(bin_load, i), Enum.at(bin_load, i - 1))
# end
# end
[
used_bins_first,
# decreasing_loads
]
end
def check_solution(
%{solutions: solutions, variables: variable_names} = _result,
item_weights,
capacity
) do
item_weights = Enum.sort(item_weights, :desc)
Enum.all?(solutions, fn sol ->
check_solution(sol, item_weights, capacity, variable_names)
end)
end
def check_solution(solution, item_weights, capacity, variable_names) do
item_assignments =
Enum.zip(solution, variable_names)
|> Enum.flat_map(fn {value, variable_name} ->
if is_binary(variable_name) && String.starts_with?(to_string(variable_name), "x_") do
value
end
|> List.wrap()
end)
%{loads: bin_loads, bin_contents: bin_contents} =
solution_to_bin_content(item_assignments, item_weights)
## Loads do no exceed max capacity
true = Enum.all?(bin_loads, fn l -> l <= capacity end)
## All items are placed into bins
all_item_indices =
Enum.reduce(tl(bin_contents), hd(bin_contents) |> MapSet.new(), fn bin_items, acc ->
MapSet.union(acc, MapSet.new(bin_items))
end)
true = all_item_indices == MapSet.new(1..length(item_weights))
## The total sum of bin weights equals the total sum of item weights
true = Enum.sum(item_weights) == Enum.sum(bin_loads)
end
def solution_to_bin_content(item_assignments, item_weights) do
bin_contents =
Enum.group_by(Enum.with_index(item_assignments, 1), fn {val, _} -> val end, fn {_, idx} ->
idx
end)
loads =
Map.new(bin_contents, fn {bin, content} ->
{
bin,
Enum.sum_by(content, fn item_id -> Enum.at(item_weights, item_id - 1) end)
}
end)
%{loads: Map.values(loads), bin_contents: Map.values(bin_contents)}
end
def model(item_weights, capacity, upper_bound, type \\ :minimize)
def model(item_weights, capacity, upper_bound, :minimize),
do: minimization_model(item_weights, capacity, upper_bound)
def solution_handler() do
fn solution ->
objective =
solution
|> Enum.find(fn {var_name, _value} ->
var_name == "total_bins_used"
end)
|> elem(1)
Logger.warning("total bins: #{objective}")
end
end
end
