Packages
fixpoint
0.17.5
0.22.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/search.ex
defmodule CPSolver.Examples.BinPacking.Search do
alias CPSolver.Variable.Interface
alias CPSolver.Search
alias CPSolver.Search.Partition
@doc """
Complete decreasing best fit branching,
roughly as per https://www.gecode.dev/doc-latest/MPG.pdf, chapter 20
"""
def cdbf(item_weights, item_assignment_vars, bin_load_vars, capacity) do
## Create a list [{item_assignment_index, item_weight}]
## (will be used for matching the item assignment variables with items' weights)
##
## Note: item weights are sorted in decreasing order
item_assignment_map =
Enum.zip(item_assignment_vars, item_weights)
|> Map.new(fn {var, weight} -> {var.name, weight} end)
item_assignment_ids = MapSet.new(Map.keys(item_assignment_map))
choose_variable_fun = fn variables ->
## get all (unfixed) item assignment vars
_item_vars =
Enum.reduce_while(variables, nil, fn v, item_vars_acc ->
item_var? = v.name in item_assignment_ids
cond do
#Interface.fixed?(v) ->
# {:cont, item_vars_acc}
is_nil(item_vars_acc) ->
(item_var? && {:cont, [v]}) || {:cont, nil}
true ->
(item_var? && {:cont, [v | item_vars_acc]}) || {:halt, item_vars_acc}
end
end)
end
choose_value_fun = fn var ->
value_branching(var, bin_load_vars, item_assignment_map, capacity)
end
fn
:init, _, _ ->
:ok
:branch, variables, _data ->
case choose_variable_fun.(variables) do
nil ->
[]
item_variables ->
## By construction (choose_variable_fun), item vars are in increasing order of weights
selected_variable = List.last(item_variables)
{bins, slack, num_loads} = choose_value_fun.(selected_variable)
domain_partitions =
partitions(selected_variable, bins, slack, num_loads)
List.wrap(Search.partition_record(selected_variable, domain_partitions))
end
end
end
defp value_branching(var, bin_load_vars, item_assignment_map, capacity) do
## The variable is quaranteed to be unfixed `item assignment`,
## (see `choose_variable_fun`)
item_weight = Map.get(item_assignment_map, var.name)
## Find bin with minimal slack
## TODO: advanced branching, as described by Gecode docs ("two alternatives" case)
##
{bins, bin_slack, num_loads} =
Enum.reduce_while(Enum.with_index(bin_load_vars, 1), {[], nil, 0}, fn
{load_var, bin_idx},
{min_bins, min_slack, load_count} = slack_acc ->
cond do
Interface.contains?(var, bin_idx) ->
slack = capacity - Interface.min(load_var) - item_weight
cond do
Interface.fixed?(load_var) ->
## The bin load has already been fixed,
## so the item has to be there (no choice).
## TODO: this is the case where further branching doesn't make sense.
## The related issue: https://github.com/bokner/fixpoint/issues/96
{:halt, {[bin_idx], nil, nil}}
slack == 0 ->
## Perfect fit
{:halt, {[bin_idx], nil, nil}}
slack < 0 ->
## No fit
{:cont, slack_acc}
slack < min_slack ->
## Better fit
{:cont, {[bin_idx], slack, load_count + 1}}
true ->
## Keep current min, add bin to the list of current min bins
{:cont, {[bin_idx | min_bins], min_slack, load_count + 1}}
end
true ->
{:cont, slack_acc}
end
end)
## TODO:
## We have not implemented the branching
## as suggested by Gecode docs for 2-alternative branching:
###
### – Not only prune bin b from the potential bins for item i but also prune all bins with
## - the same slack as b from the potential bins for all items with the same size as i
###
## What we currently do for branching (see CPSolver.Search):
## - For the first branch we fix the variable with the chosen value;
## - For the second branch, we remove the value from the variable.
##
## - To match Gecode, we will have to remove values for several variables (the ones with the same slack)
##
## May be possible by implementing custom value selector:
## (see CPSolver.Search.ValueSelector.Split for an example).
##
##
## Also, return length of bin loads (to be used when building partitions)
{bins, bin_slack, num_loads}
end
defp partitions(variable, bins, slack, _num_loads) do
bin = Enum.random(bins)
if slack in [nil, 0] do ##|| (length(bins) == num_loads) do
Partition.fixed_partition(bin, variable)
else
Partition.partition_by_fix(bin, variable)
end
|> List.wrap()
end
end