17 Binpacking (examp-binpack)

Run LPL Code  ,  PDF Document

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 wi and a set of bins k K with capacity CA (we suppose that wi CA for all i I), that is all items can be packed in a bin. We need at most maxBins bins :

                     ∑
maxBins   =  min(|I|,   wi ∕CA )
                      i

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 xk,i [0|I|] with k K and i I. For example: x1,1 = 16 means that the first item in bin 1 is the item with number 16, x1,2 = 19 means that the second item in bin 1 is the item with number 19, etc. xi,k = 0 means that there is no k-th item in bin i.

The model then can be formulated as follows:

                      ∑
let           bWk =        wxk,i     forall k ∈ K
                     i|x ⁄=0
                       k,i
let           bUk = couint  xk,i > 0   forall k ∈ K
s.t.          bWk <=  CA             forall k ∈ K
              ∑
min              bUk
               k
setpartition   xk,i ∈ [1 ...|I |]         forall k ∈ K, i ∈ I

bWk is the (unknown) weight of a bin k. bUk 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.


Listing 17: The Complete Model implemented in LPL [10]
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.