%
% Simple Bin Packing problem in Minizinc
%
% Note the symmetry breaking constraints.
%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc

int: num_stuff;                    % number of things to pack
array[1..num_stuff] of int: stuff; % the value/weight of the things to pack
int: bin_capacity;                 % all bins have the same capacity

% Number of bins cannot exceed num_stuff...
int: num_bins = num_stuff;

% either the thing is packed or not
array[1..num_bins, 1..num_stuff] of var 0..1: bins;

% calculate how many things a bin takes
array[1..num_bins] of var int: bin_loads;

% number of loaded bins (which we will minimize)
var 0..num_bins: num_loaded_bins;

% minimize the number of loaded bins
solve minimize num_loaded_bins;

% alternative solve statement
% solve :: int_search([num_loaded_bins], "first_fail", "indomain", "complete") minimize num_loaded_bins;

constraint

    % sanity clause: No thing can be larger than capacity.
    forall(s in 1..num_stuff) ( 
       stuff[s] <= bin_capacity 
    )

    /\ % the total load in the bin cannot exceed bin_capacity
    forall(b in 1..num_bins) (
       bin_loads[b] = sum(s in 1..num_stuff) (stuff[s]*bins[b,s]) /\ 
       bin_loads[b] <= bin_capacity /\
       bin_loads[b] >= 0
    ) 

    /\ % calculate the total load for a bin
    sum(s in 1..num_stuff) (stuff[s]) = sum(b in 1..num_bins) (bin_loads[b])

    /\ % a thing is packed just once 
    forall(s in 1..num_stuff) ( 
       sum(b in 1..num_bins) (bins[b,s])  = 1 
    )

    /\ % symmetry breaking: 
       % if bin_loads[i+1] is > 0 then bin_loads[i] must be > 0
    forall(b in 1..num_bins-1) (
       bin_loads[b+1] > 0 -> bin_loads[b] > 0
       /\ % and should be filled in order of weight
       bin_loads[b] >= bin_loads[b+1] 
    ) 
    /\ % another symmetry breaking: first bin must be loaded
    bin_loads[1] > 0 

    /\ % calculate num_loaded_bins
    num_loaded_bins = sum(b in 1..num_bins) (bool2int(bin_loads[b] > 0))
;

%
% Output
%
output [
       if (b = 1 /\ s = 1) then show(num_loaded_bins) ++ "\n" else "" endif ++
       if s = 1 then show(bin_loads[b]) ++ " : " else "" endif ++
       show(bins[b,s]) ++ if s mod num_stuff = 0 then "\n" else " " endif
       | b in 1..num_bins, s in 1..num_stuff
];


%
% data
%

% simple (and probably unrealistic) packing
% num_stuff = 20;
% stuff = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
% bin_capacity = 30; 

% The 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;

% same source of data, but now there are 22 things
num_stuff = 22; % antal saker
stuff = [42,69,67,57,93,90,38,36,45,42,33,79,27,57,44,84,86,92,46,38,85,33];
bin_capacity = 250;

%
% still more stuff
%
% num_stuff = 50;
% stuff = [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,3];
% bin_capacity = 290;