The Constraint Programming Solver (Experimental)

PACK Predicate

  • PACK (scalar-variable,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 Bin {j in 1..3} >= 0 <= j + 2 integer;
   var Item {1..5} >= 1 <= 3 integer;
   num size {1..5} = [4 3 2 2 1];
   con Mycon: pack(Item, size, Bin);
   solve;
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

Item Variable

Item[1]

Item[2]

Item[3]

Item[4]

Item[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$ contains the bin number for the ith item. The variable $s_ i$ holds the size or weight of the ith item. The domain of the load variable $l_ j$ constrains the capacity of bin j.

Note: It can be more efficient to list the item variables in nonincreasing size order and to specify VARSELECT=FIFO in the SOLVE WITH CLP statement.