Packages
fixpoint
0.16.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/bin_packing.ex
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
import CPSolver.Variable.View.Factory
alias CPSolver.Objective
def minimization_model(item_weights, max_bin_capacity) do
num_items = length(item_weights)
num_bins = num_items
item_weights = Enum.sort(item_weights, :desc)
# x[i][j] item i assigned to bin j
indicators =
for i <- 0..(num_items - 1) do
for j <- 0..(num_bins - 1) do
Variable.new(0..1, name: "item_#{i}_in_bin_#{j}")
end
end
# bin j is used
bin_used =
for j <- 0..(num_bins - 1) do
Variable.new(0..1, name: "bin_#{j}_used")
end
# total weight in bin j
bin_load =
for j <- 0..(num_bins - 1) do
Variable.new(0..max_bin_capacity, name: "bin_load_#{j}")
end
item_assignment_constraints =
Enum.map(indicators, fn inds ->
Sum.new(1, inds)
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, max_bin_capacity))
end)
total_bins_used =
Variable.new(ceil(Enum.sum(item_weights) / max_bin_capacity)..num_bins,
name: "total_bins_used"
)
total_bins_constraint =
Sum.new(total_bins_used, bin_used)
# Only allow bin j to be used if all bins < j are used.
# This prevents the solver from seeing equivalent packings as different solutions.
symmetry_breaking =
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)
bin_load_sum_constraint = Sum.new(Enum.sum(item_weights), bin_load)
constraints =
[
item_assignment_constraints,
bin_load_constraints,
capacity_constraints,
symmetry_breaking,
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)
)
end
def print_result(%{status: status} = result) do
result =
cond do
status == :unsatisfiable ->
"Solution does not exist"
status == :unknown ->
"No solution found within allotted time"
true ->
Enum.map_join(items_by_bin(result), "\n", fn {bin, items} ->
"Bin #{bin} contains: #{Enum.join(items, ", ")}"
end)
end
IO.puts(result)
end
defp items_by_bin(result) do
solution = List.last(result.solutions)
variable_names = result.variables
assignments =
Enum.zip(variable_names, solution)
|> Enum.filter(fn {name, value} ->
is_binary(name) and value == 1 and String.starts_with?(name, "item_")
end)
Enum.reduce(assignments, %{}, fn {name, _}, acc ->
case String.split(name, "_in_bin_") do
[item, bin] ->
Map.update(acc, bin, [item], fn items -> [item | items] end)
_ ->
acc
end
end)
|> Enum.map(fn {bin_str, items} ->
bin = String.to_integer(bin_str)
item_ids =
items
|> Enum.map(fn item ->
item
|> String.replace_prefix("item_", "")
|> String.to_integer()
end)
{bin, item_ids}
end)
|> Map.new()
end
def check_solution(result, item_weights, max_capacity) do
best_solution = result.solutions |> List.last()
%{loads: bin_loads, bin_contents: bin_contents} =
solution_to_bin_content(best_solution, item_weights, max_capacity)
## Loads do no exceed max capacity
true = Enum.all?(bin_loads, fn l -> l <= max_capacity end)
## All items are placed into bins
all_item_indices =
Enum.reduce(tl(bin_contents), hd(bin_contents), fn bin_items, acc ->
MapSet.union(acc, bin_items)
end)
true = all_item_indices == MapSet.new(0..(length(item_weights) - 1))
## For each bin, the load is the sum of weights of items placed to bin
true =
Enum.all?(Enum.zip(bin_loads, bin_contents), fn {load, items} ->
load == Enum.sum_by(items, fn item_idx -> Enum.at(item_weights, item_idx) end)
end)
## 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(solution, item_weights, _max_capacity) do
num_items = length(item_weights)
{_bins, rest} = Enum.split(solution, num_items)
total_bins = hd(rest)
{bin_loads, rest} = Enum.split(tl(rest), total_bins)
{assignments, _rest} = Enum.split(rest, num_items * num_items)
## placements[i] row corresponds to the placement of the item
## (position of 1 signifies the bin the item was assigned to)
placements = Enum.chunk_every(assignments, num_items)
### Transpose placements to get bins as rows
bin_contents =
Enum.zip_with(placements, &Function.identity/1)
|> Enum.flat_map(fn bin ->
bin_content =
Enum.reduce(Enum.with_index(bin, 0), MapSet.new(), fn {i, pos}, acc ->
(i == 0 && acc) || MapSet.put(acc, pos)
end)
(MapSet.size(bin_content) == 0 && []) || [bin_content]
end)
%{loads: bin_loads, bin_contents: bin_contents}
end
def model(item_weights, max_bin_capacity, type \\ :minimize)
def model(item_weights, max_bin_capacity, :minimize),
do: minimization_model(item_weights, max_bin_capacity)
end