The Decomposition Algorithm

The bin packing problem (BPP) finds the minimum number of capacitated bins that are needed to store a set of products with varying size. Define a set of products, their sizes , and a set of candidate bins, each with capacity . Let be a binary variable, which, if set to , indicates that product is assigned to bin . In addition, let be a binary variable, which, if set to , indicates that bin is used.

A BPP can be formulated as a MILP as follows:

In this formulation, constraints (assignment) ensure that each product is assigned to at least one bin. The objective function ensures that there exists an optimal solution that never assigns a product to more than one bin. Constraints (capacity) ensure that the capacity restrictions are met for each bin. In addition, these constraints enforce that if any product is assigned to bin , then must be positive.

In this formulation, the bin identifier is arbitrary. For example, in any solution, the assignments to bin can be swapped with the assignments to bin without affecting feasibility or the objective value. Consider a decomposition by bin, where the assignment constraints form the master problem and the capacity constraints form identical subproblems. As described in the section Special Case: Identical Blocks, this is a situation in which an aggregate formulation and Ryan-Foster branching can greatly improve performance by reducing symmetry.

Consider a series of UNC basketball games that are recorded on a DVR. The following data set dvr provides the name of each game in column opponent and the size of that game in gigabytes (GB) as it resides on the DVR in column size:

/* game, size (in GBs) */
data dvr;
   input opponent $ size;
   datalines;
Clemson  1.36 
Clemson2 1.97 
Duke     2.76 
Duke2    2.52 
FSU      2.56 
FSU2     2.34 
GT       1.49 
GT2      1.12 
IN       1.45 
KY       1.42 
Loyola   1.42 
MD       1.33 
MD2      2.71 
Miami    1.22 
NCSU     2.52 
NCSU2    2.54 
UConn    1.25 
VA       2.33 
VA2      2.48 
VT       1.41 
Vermont  1.28 
WM       1.25 
WM2      1.23 
Wake     1.61 
;

The goal is to use the fewest number of DVDs on which to copy the games for safekeeping. Each DVD can hold 4.38GB of recording. The problem can be formulated as a bin packing problem and solved by using PROC OPTMODEL and the decomposition algorithm. The following PROC OPTMODEL statements read in the data, declare the optimization model, and use the decomposition algorithm to solve it.

proc optmodel;
   /* read the product and size data */
   set <str> PRODUCTS;
   num size {PRODUCTS};
   read data dvr into PRODUCTS=[opponent] size;

   /* 4.38 GBs per DVD */
   num binsize = 4.38;

   /* the number of products is a trivial upper bound on the
      number of bins needed */
   num upperbound init card(PRODUCTS);
   set BINS = 1..upperbound;

   /* Assign[p,b] = 1, if product p is assigned to bin b */
   var Assign {PRODUCTS, BINS} binary;
   /* UseBin[b] = 1, if bin b is used */
   var UseBin {BINS} binary;

   /* minimize number of bins used */
   min Objective = sum {b in BINS} UseBin[b];

   /* assign each product to at least one bin (relax partitioning
      to covering) */
   con Assign_def {p in PRODUCTS}:
      sum {b in BINS} Assign[p,b] >= 1;

   /* capacity constraint on each bin (and definition of UseBin) */
   con CapacityLink {b in BINS}:
      sum {p in PRODUCTS} size[p] * Assign[p,b] <= binsize * UseBin[b];

   /* decompose by bin (subproblem is a knapsack problem) */
   for {b in BINS} CapacityLink[b].block = b;

   /* solve using decomp (aggregate formulation) */
   solve with milp / decomp=();

The following OPTMODEL statements create a sequential numbering of the bins and output to the data set dvd the optimal assignments of games to bins:

   /* create a map from arbitrary bin number to sequential bin number */
   num binId init 1;
   num binMap {BINS};
   for {b in BINS: UseBin[b].sol > 0.5} do;
      binMap[b] = binId;
      binId     = binId + 1;
   end;

   /* create map of product to bin from solution */
   num bin {PRODUCTS};
   for {p in PRODUCTS} do;
      for {b in BINS: Assign[p,b].sol > 0.5} do;
         bin[p] = binMap[b];
         leave;
      end;
   end;

   /* create solution data */
   create data dvd from [product] bin size;
quit;

The solution summary is displayed in Output 14.5.1.

The iteration log is displayed in Output 14.5.2.

The following call to PROC SORT sorts the assignments by bin:

proc sort data=dvd;
   by bin;
run;

The optimal assignments from the output data set dvd are displayed in Output 14.5.3.