The CLP Procedure

PACK Statement

(Experimental)

  • PACK bin_packing_constraint-1 <…bin_packing_constraint-n>;

where bin_packing_constraint is specified in the following form:

( ($b_1$ <…$b_ k$>) ( $s_1$ <…$s_ k$>) ( $l_1$ <…$l_ m$> ) )

The PACK constraint is used to assign k items to m bins, subject to the sizes of the items and the capacities of the bins. The item variable $b_ i$ assigns a bin to the ith item so that the domain for the item variables is 1 to m. Optionally, the domain for the item variables can be any contiguous set up to size m, where the smallest member represents the first bin, the second-smallest represents the second bin, and so on. The constant $s_ i$ gives the size or weight of the ith item. The value of load variable $l_ j$ is determined by the total size of the contents of the corresponding bin.

For example, suppose there are three bins with capacities 3, 4, and 5. There are five items with sizes 4, 3, 2, 2, and 1 to be assigned to these three bins. The following statements formulate the problem and find all solutions: 

proc clp out=out findallsolns;
   var bin1 = [0,3];
   var bin2 = [0,4];
   var bin3 = [0,5];
   var (item1-item5) = [1,3];
   pack ((item1-item5) (4,3,2,2,1) (bin1-bin3));
run;

Each row of Table 3.2 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 3.2: Bin Packing Solutions

 

Item Variable

 

item1

item2

item3

item4

item5
 

2

3

3

1

1

 

2

3

1

3

1

 

2

1

3

3

3

 

3

1

2

2

3


Note: In specifying a PACK constraint, it can be more efficient to list the item variables in order by nonincreasing size and to specify VARSELECT=FIFO in the PROC CLP statement so that load variables are selected last.