Problem

Another example, that can be formulated as a permutation problem is the Bin-Packing problem. In contrast the the CVRP problem (see examp-cvrp), the order of the subsets is not important: a bin just contains a subset of items, the order is not important.

The bin packing problem (BPP) is a classical model from the operations research (see also binpack for another formulation of the problem). Different items of given weights must be packed into a number of bins of given capacity. How many bins are needed to pack all items? A MIP implementation of the binpacking problem can be found in binpack.

Modeling Steps

Given a set of items i ∈ I with a weight w_{i} and a set of bins k ∈ K with capacity CA (we
suppose that w_{i} ≤ CA for all i ∈ I), that is all items can be packed in a bin. We need at most
maxBins bins :

So let K = {1,…,maxBins}.

Let’s enumerate all items from 1 to |I|. Then we are asked to partition these numbers into
maximally |K| subsets (but as few as possible), such that the cumulated weight of the items in
a subset do not exceed the capacity CA. The item numbers form a permutation, that
must be partitioned into subsets. We can formulated this by introducing a variable
x_{k,i} ∈ [0…|I|] with k ∈ K and i ∈ I. For example: x_{1,1} = 16 means that the first item in
bin 1 is the item with number 16, x_{1,2} = 19 means that the second item in bin 1
is the item with number 19, etc. x_{i,k} = 0 means that there is no k-th item in bin
i.

The model then can be formulated as follows:

bW_{k} is the (unknown) weight of a bin k. bU_{k} is true (1) if the bin k is not empty (it counts the
items in a bin k and if there is at least 1 then it is true). The unique constraint makes sure that
the capacity of a bin is not exceeded, and the objective function minimizes the number of bins
used.

model binpacking "Binpacking";

set i,j "items";

k "bins";

parameter CA "capacity of bin";

weight{i} "weight of item i";

alldiff x{k,i} 'set partition';

expression bWeight{k}: sum{i|x} weight[x];

expression bUsed{k}: count{i} x > 0;

constraint bCapa{k}: bWeight <= CA;

minimize nrBins: sum{k} bUsed;

model data;

parameter n; m;

Read('bin-t60-00.txt',n);

i:=1..n;

Read('%1;1',CA);

Read{i}('%1;2',weight);

parameter minBins:=Ceil(sum{i} weight/CA);

maxBins:= min(#i, 2*minBins);;

k:=1..maxBins;

end

model output;

Write{k|bUsed}('Bin weight: %4d '

| Items: %3d' n',bWeight,{i|x} x);

end

end

Further Comments

In LPL, the permutation variables is declared as a alldiff variable with two dimensions and the attribute ’set partition’ in this case.