/*
Bin packing in Picat.
Simple bin packing problems
This model is based on my B-Prolog version, via
the ECLiPSe and SICStus Prolog models.
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
import cp.
main => go.
% sorted Stuff: very slow for problem 9
go =>
foreach(P in 0..9) time2($bin_packing(P,sorted)) end.
% Unsorted Stuff: very slow for problem 9
go2 =>
foreach(P in 0..9) time2($bin_packing(P,unsorted)) end.
% In all very slow...
go3 =>
foreach(P in 0..9) time2($bin_packing2(P)) end.
scalar_product(A, X, Product) =>
Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).
bin_packing(Problem, SortMode) =>
problem(Problem, StuffUnordered, BinCapacity),
% sorting (reversed) the stuff may makes it a bit faster
if SortMode = sorted then
Stuff = sort_down(StuffUnordered)
else
Stuff = StuffUnordered
end,
printf("\nProblem %w\n",Problem),
% BinCapacity: the (common) capacity for each bin
write(bin_capacity=BinCapacity),nl,
% Stuff: values/weight of the things to pack
NumStuff = length(Stuff),
write(stuff=Stuff),nl,
write(num_stuff=NumStuff),nl,
% Number of bins cannot exceed num_stuff...
NumBins #= NumStuff,
% Sanity clause:
% No thing can be larger than capacity.
foreach(S in Stuff)
if S > BinCapacity then
printf("Stuff %d is larger than BinCapacity %d\n", S, BinCapacity)
end
end,
% Bins: where to put a thing.
Bins = new_array(NumBins,NumStuff),
BinsList = vars(Bins),
BinsList :: 0..1,
% BinLoads: contains how many things (the summed
% weights of) a bin takes
BinLoads = new_list(NumBins),
BinLoads :: 0..BinCapacity,
foreach({Bin,Load} in zip(Bins.to_list(),BinLoads))
scalar_product(Stuff,Bin,Load)
end,
% a thing is packed exactly once
foreach(Column in transpose(Bins).array_matrix_to_list_matrix()) sum(Column) #= 1 end,
% compare the total loads
sum(Stuff) #= sum(BinLoads),
% load the bins in order:
% first bin must be loaded, and the list must be ordered
% element(1, BinLoads, BinLoads1),
% BinLoads1 #> 0,
BinLoads[1] #> 0,
% decreasing(BinLoads),
% symmetry breaking:
% if bin_loads[i+1] is > 0 then bin_loads[i] must be > 0
% (This seems to be better than using decreasing/1.)
foreach(B in 1..NumBins-1)
BinLoads[B+1] #>0 #=> BinLoads[B] #> 0,
BinLoads[B] #>= BinLoads[B+1]
end,
% calculate the number of loaded bins (which we will minimize)
NumLoadedBins #= sum([(BL #> 0) : BL in BinLoads]),
%
% search
%
writeln(search),
% term_variables([BinsList,BinLoads,NumBins,NumLoadedBins],Vars),
Vars = Bins.to_list() ++ BinLoads,
% minof(labeling([inout,split],Vars), NumLoadedBins,
solve([$min(NumLoadedBins), inout],Vars),
% labeling([inout], Vars),
% output
writeln('...'),
writeln(bin_loads=BinLoads),
writeln(num_loaded_bins=NumLoadedBins),
writeln(numBins=NumBins),
% just print smaller problems
if NumBins =< 40 then
% pretty_print(Bins)
pretty_print2(Bins)
else
printf("Bins are too large to print.\n")
end,
nl.
%
% Using cumulative for this problem was suggested by Mats Carlsson
% (and it is very fast in the SICStus prolog version).
%
% However, the implementation has been rewritten trying to keep
% the same approach. However, this is (much) slower than bin_packing/1.
% The correct MaxStart value is mostly found very fast
% (including for #9), but it then takes a long time to prove
% its optimality. I might have missed something here...
%
bin_packing2(Problem) =>
problem(Problem, StuffUnordered, BinCapacity),
% Stuff = sort(StuffUnordered),
Stuff = sort_down(StuffUnordered),
% Stuff = StuffUnordered,
N = length(Stuff),
printf("\nProblem %d BinCapacity:%d N:%d\n", Problem,BinCapacity,N),
writeln(stuff=Stuff),
Duration = [1 : _I in 1..N],
Resources = Stuff,
Limit #= BinCapacity,
Start = new_list(N),
Start :: 1..BinCapacity,
End = new_list(N),
End :: 1..BinCapacity,
% to minimize
MaxStart #= max(Start),
foreach({S,D,E} in zip(Start,Duration,End)) E #= S+D end,
cumulative(Start,Duration,Resources,Limit),
Vars = Start,
solve([$min(MaxStart),forward,split],Vars),
nl,
writeln(maxStart=MaxStart),
writeln(start=Start),
writeln(duration=Duration),
writeln(end=End),
writeln(limit=Limit),
writeln(stuff=Stuff),
writeln(binCapacity=BinCapacity),
foreach({S,E,T} in zip(Start,End,Stuff))
writeln([bin=S,stuff=T])
end,
nl.
%
% pretty prints the Bin matrix.
pretty_print(X) =>
writeln(pretty_print),
foreach(Row in X)
foreach(R in Row) printf("%d ", R) end,
printf(" = %w\n", sum(Row.to_list()))
end.
% just print the filled bins
pretty_print2(X) =>
writeln(pretty_print2),
foreach(Row in X)
Sum = sum(Row.to_list()),
if Sum > 0 then
foreach(R in Row) printf("%d ", R) end,
printf(" = %d\n", Sum)
end
end.
decreasing(List) =>
foreach(I in 2..List.length) List[I-1] #>= List[I] end.
increasing(List) =>
foreach(I in 2..List.length) List[I-1] #=< List[I] end.
%
% Data
%
% easy problem to test with
problem(0, P, Capacity) =>
P=[1,2,3,4,5,6,7,8,9,10],
Capacity=30.
%
% Example from the Alice system
% Copying files to disks
% http://news.mozart-oz.org/alice/manual/cptutorial/node55.html
%
% """
% Suppose, you want to copy a set of files from your hard-disk onto as
% few as possible diskettes of a given size, e. g. onto common 1.44 MB
% diskettes. In case your files do not fit on a single diskette, it might
% become quite tricky to figure out the minimal number of needed diskettes
% and how to partition the files.
% """
problem(1, P, Capacity) =>
P=[360, 850, 630, 70, 700, 210],
Capacity=1440.
% simple (and probably unrealistic) packing
problem(2, P, Capacity) =>
P=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
Capacity=20.
% simple (and probably even less unrealistic) packing
problem(3, P, Capacity) =>
P = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25],
Capacity = 50.
% This problem below is from
% http://www.dcs.gla.ac.uk/~pat/cpM/slides/binPacking.ppt
% 1D Bin Packing (or "CP? Who cares?"), page 3
% and also from
% http://www.dcs.gla.ac.uk/~pat/cpM/JChoco/binPack
%
% num_stuff = 10;
% stuff = [42,63,67,57,93,90,38,36,45,42];
% bin_capacity = 150;
problem(4, P, Capacity) =>
P= [42,69,67,57,93,90,38,36,45,42],
Capacity = 150.
% same source of data, but now there are 22 things
problem(5, P, Capacity) =>
P=[42,69,67,57,93,90,38,36,45,42,33,79,27,57,44,84,86,92,
46,38,85,33],
Capacity = 250.
%
% continuing of the above example.
%
problem(6, P, Capacity) =>
P = [42,69,67,57,93,90,38,36,45,42,33,79,27,57,44,84,86,92,
46,38,85,33,82,73,49,70,59,23,57,72,74,69,33,42,28,46,
30,64,29,74,41,49,55,98,80,32,25,38,82,30],
Capacity = 290.
% ibid.
problem(7, P, Capacity) =>
P= [42,69,67,57,93,90,38,36,45,42,33,79,27,57,44,84,86,92,46,38,
85,33,82,73,49,70,59,23,57,72,74,69,33,42,28,46,30,64,29,74,
41,49,55,98,80,32,25,38,82,30,35,39,57,84,62,50,55,27,30,36,
20,78,47,26,45,41,58,98,91,96,73,84,37,93,91,43,73,85,81,79,
71,80,76,83,41,78,70,23,42,87,43,84,60,55,49,78,73,62,36,44,
94,69,32,96,70,84,58,78,25,80,58,66,83,24,98,60,42,43,43,
39],
Capacity = 500.
% From
% Graham Kendall: Bin Packing made Easier
% http://research-reflections.blogspot.com/2009/07/bin-packing-made-easier.html
problem(8, P, Capacity) =>
P = [442,252,127,106,37,10,10,252,252,127,106,37,10,9,
252,252,127,85,12,10,9,252,127,106,84,12,10,252,
127,106,46,12,10],
Capacity = 524.
% Variant: remove 46 from the problem above
problem(9, P, Capacity) =>
P =
[442,252,127,106,37,10,10,252,252,127,106,37,10,9,
252,252,127,85,12,10,9,252,127,106,84,12,10,252,
127,106,12,10],
Capacity = 524.