The Constraint Programming Solver

PACK Predicate

  • PACK (variable-list,data-list,variable-list)

The PACK predicate specifies a pack constraint, which is used to assign items to bins, subject to the sizes of the items and the capacities of the bins.

For example, suppose you have three bins, whose capacities are 3, 4, and 5, and you have five items of sizes 4, 3, 2, 2, and 1, to be assigned to these three bins. The following statements formulate the problem and find a solution: 

proc optmodel;
   var SpaceUsed {bin in 1..3} integer >= 0 <= bin + 2;
   var WhichBin {1..5} >= 1 <= 3 integer;
   num itemSize {1..5} = [4 3 2 2 1];
   con pack( WhichBin, itemSize, SpaceUsed );
   solve / findall;
quit;

Each row of Table 6.4 represents a solution to the problem. The number in each item column is the number of the bin to which the corresponding item is assigned.

Table 6.4: Bin Packing Solutions

WhichBin Variable

WhichBin[1]

WhichBin[2]

WhichBin[3]

WhichBin[4]

WhichBin[5]

2

3

3

1

1

2

3

1

3

1

2

1

3

3

3

3

1

2

2

3


When you assign a set of k items to m bins, the item variable $b_ i, i \in 1,\dots ,k$ (WhichBin in the preceding example) contains the bin number for the ith item. The constant $s_ i$ (itemSize in the preceding example) holds the size or weight of the ith item. The domain of the load variable $l_ j$ (SpaceUsed in the preceding example) constrains the capacity of bin j. The value of $l_ j$ in the solution is the amount of space used in bin j.

Note: It can be more efficient to assign higher priority to item variables than to load variables, and within the item variables, to assign higher priority to larger itmes.