Packages
fixpoint
0.17.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
@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, _rest_vars} =
Enum.split_with(variables, fn v -> v.name in item_assignment_ids end)
if Enum.empty?(item_vars) do
## All item assignments were made - we're done
nil
else
var = hd(item_vars)
%{
variable: var,
value: value_branching(var, bin_load_vars, item_assignment_map, capacity)
}
end
end
choose_value_fun = fn %{variable: _var, value: value} ->
## the value was computed by choose_variable_fun
value
end
{choose_variable_fun, choose_value_fun}
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} =
Enum.reduce_while(Enum.with_index(bin_load_vars, 1), {[], nil}, fn {load_var, bin_idx},
{min_bins, min_slack} =
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], 0}}
slack == 0 ->
## Perfect fit
{:halt, {[bin_idx], 0}}
slack < 0 ->
## No fit
{:cont, slack_acc}
slack < min_slack ->
## Better fit
{:cont, {[bin_idx], slack}}
true ->
## Keep current min, add bin to the list of current min bins
{:cont, {[bin_idx | min_bins], min_slack}}
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).
##
##
if bin_slack == 0 || length(bins) == length(bin_load_vars) do
List.first(bins)
else
## TODO: to replace with second alternative implementation
List.first(bins)
end
end
end