/*
Global constraint bin packing in Picat.
From Global Constraint Catalogue
http://www.emn.fr/x-info/sdemasse/gccat/sec4.35.html
"""
Given several items of the collection ITEMS (each of them having a specific
weight), and different bins of a fixed capacity, assign each item to a bin
so that the total weight of the items in each bin does not exceed CAPACITY.
Example
<(5,)>
The bin_packing constraint holds since the sum of the height of items
that are assigned to bins 1 and 3 is respectively equal to 3 and 5.
The previous quantities are both less than or equal to the maximum
CAPACITY 5. Figure 4.35.1 shows the solution associated with the example.
Remark
Note the difference with the classical bin-packing problem [MT90] where
one wants to find solutions that minimise the number of bins. In our
case each item may be assigned only to specific bins (i.e., the different
values of the bin variable) and the goal is to find a feasible solution.
This constraint can be seen as a special case of the cumulative
constraint [AB93], where all task durations are equal to 1.
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
/*
From the ECLiPSe model:
"""
This is also a study of translating a simple predicate from MiniZinc to
ECLiPSe. Here is the MiniZinc code, n is the size of weights and bins:
forall(b in 1..n) (
sum(j in 1..n) ( weights[j]*bool2int(bins[j] = b)) <= capacity
)
Using the same approach as MiniZinc, I prefer version 2 to version 1,
since it is more succint. I prefer version 2 to version 3 since it
is clearer.
Note that both the MiniZinc version and this ECLiPSe version are
fully multidirectional, i.e. we can let either (or all) of the
variables be free and it still work.
If we let Bins free, we must fix the length of it (to 3 in the
example).
"""
*/
go =>
foreach(Problem in 1..2, Predicate in [bin_packing1, bin_packing2])
printf("Problem %d using %w\n", Problem,Predicate),
do_problem(Problem,Predicate)
end,
nl.
do_problem(Problem, Predicate) =>
% we let the Capacity be unknown
problem(Problem,Bins, Weights,_Capacity),
% N = 3, % if Bins is free we must set the length of it
N = length(Weights),
Bins = new_list(N),
% Bins :: 1..N,
% Weights :: 1..4,
% Capacity = 5,
Capacity :: 1..20,
% bin_packing3(Bins,Weights,Capacity),
% bin_packing2(Bins,Weights,Capacity),
call(Predicate,Bins,Weights,Capacity),
Vars = Weights ++ Bins ++ [Capacity],
solve([$min(Capacity)],Vars),
writeln(capacity=Capacity),
writeln(bins=Bins),
writeln(weights=Weights),
nl.
% The example cited above
problem(1, Bins, Weights, Capacity) =>
Bins=[3,1,3], Weights=[4,3,1], Capacity=5.
% another example
problem(2, Bins, Weights, Capacity) =>
Bins=[3,1,3,2,2,1,2,3], Weights=[4,3,1,3,4,3,1,2], Capacity=5.
% version 1, using list comprehension
bin_packing1(Bins, Weights, Capacity) =>
N = length(Bins),
N = length(Weights),
foreach(B in 1..N)
sum([(Weights[J]*(Bins[J] #= B)) : J in 1..N ]) #=< Capacity
end.
% version 2, using accumulator Sum
bin_packing2(Bins, Weights, Capacity) =>
N = length(Bins),
N = length(Weights),
foreach(B in 1..N)
Sum = 0,
foreach(J in 1..N)
Sum := $Sum + Weights[J] * (Bins[J] #= B)
end,
Sum #=< Capacity
end.