The Decomposition Algorithm

Example 14.2 Generalized Assignment Problem

The generalized assignment problem (GAP) is that of finding a maximum profit assignment from $n$ tasks to $m$ machines such that each task is assigned to precisely one machine subject to capacity restrictions on the machines. With each possible assignment, associate a binary variable $x_{ij}$, which, if set to $1$, indicates that machine $i$ is assigned to task $j$. For ease of notation, define two index sets $M=\left\{ 1,\dots ,m\right\} $ and $N=\left\{ 1,\dots ,n\right\} $. A GAP can be formulated as a MILP as follows:

\begin{align*} & \text {maximize} &  \sum _{i \in M} \sum _{j \in N} p_{ij} x_{ij}\\ & \text {subject to} &  \sum _{i \in M} x_{ij} &  = 1 & &  j \in N & &  \text {(assignment)}\\ & &  \sum _{j \in N} w_{ij} x_{ij} &  \leq b_ i & &  i \in M & &  \text {(knapsack)} \\ & &  x_{ij} &  \in \left\{ 0,1\right\}  & &  i \in M, \  j \in N \end{align*}

In this formulation, constraints (assignment) ensure that each task is assigned to exactly one machine. Constraints (knapsack) ensure that for each machine, the capacity restrictions are met.

Consider the following example taken from Koch et al. (2011) with $n=24$ tasks to be assigned to $m=8$ machines. The data set profit_data provides the profit for assigning a particular task to a particular machine:

%let NumTasks    = 24;
%let NumMachines = 8;

data profit_data;
   input p1-p&NumTasks;
   datalines;
25 23 20 16 19 22 20 16 15 22 15 21 20 23 20 22 19 25 25 24 21 17 23 17
16 19 22 22 19 23 17 24 15 24 18 19 20 24 25 25 19 24 18 21 16 25 15 20
20 18 23 23 23 17 19 16 24 24 17 23 19 22 23 25 23 18 19 24 20 17 23 23
16 16 15 23 15 15 25 22 17 20 19 16 17 17 20 17 17 18 16 18 15 25 22 17
17 23 21 20 24 22 25 17 22 20 16 22 21 23 24 15 22 25 18 19 19 17 22 23
24 21 23 17 21 19 19 17 18 24 15 15 17 18 15 24 19 21 23 24 17 20 16 21
18 21 22 23 22 15 18 15 21 22 15 23 21 25 25 23 20 16 25 17 15 15 18 16
19 24 18 17 21 18 24 25 18 23 21 15 24 23 18 18 23 23 16 20 20 19 25 21
;

The data set weight_data provides the amount of resources used by a particular task when assigned to a particular machine:

data weight_data;
   input w1-w&NumTasks;
   datalines;
 8 18 22  5 11 11 22 11 17 22 11 20 13 13  7 22 15 22 24  8  8 24 18  8
24 14 11 15 24  8 10 15 19 25  6 13 10 25 19 24 13 12  5 18 10 24  8  5
22 22 21 22 13 16 21  5 25 13 12  9 24  6 22 24 11 21 11 14 12 10 20  6
13  8 19 12 19 18 10 21  5  9 11  9 22  8 12 13  9 25 19 24 22  6 19 14
25 16 13  5 11  8  7  8 25 20 24 20 11  6 10 10  6 22 10 10 13 21  5 19
19 19  5 11 22 24 18 11  6 13 24 24 22  6 22  5 14  6 16 11  6  8 18 10
24 10  9 10  6 15  7 13 20  8  7  9 24  9 21  9 11 19 10  5 23 20  5 21
 6  9  9  5 12 10 16 15 19 18 20 18 16 21 11 12 22 16 21 25  7 14 16 10
;

Finally, the data set capacity_data provides the resource capacity for each machine:

data capacity_data;
   input b @@;
   datalines;
36 35 38 34 32 34 31 34
;

The following PROC OPTMODEL statements read in the data and define the necessary sets and parameters:

proc optmodel;
   /* declare index sets */
   set TASKS    = 1..&NumTasks;
   set MACHINES = 1..&NumMachines;

   /* declare parameters */
   num profit   {MACHINES, TASKS};
   num weight   {MACHINES, TASKS};
   num capacity {MACHINES};

   /* read data sets to populate data */
   read data profit_data   into [i=_n_] {j in TASKS} <profit[i,j]=col('p'||j)>;
   read data weight_data   into [i=_n_] {j in TASKS} <weight[i,j]=col('w'||j)>;
   read data capacity_data into [_n_] capacity=b;

The following statements declare the optimization model:

   /* declare decision variables */
   var Assign {MACHINES, TASKS} binary;

   /* declare objective */
   max TotalProfit =
      sum {i in MACHINES, j in TASKS} profit[i,j] * Assign[i,j];

   /* declare constraints */
   con AssignmentCon {j in TASKS}:
      sum {i in MACHINES} Assign[i,j] = 1;

   con KnapsackCon {i in MACHINES}:
      sum {j in TASKS} weight[i,j] * Assign[i,j] <= capacity[i];

The following statements use two different decompositions to solve the problem. The first decomposition defines each assignment constraint as a block and uses the pure network simplex solver for the subproblem. The second decomposition defines each knapsack constraint as a block and uses the MILP solver for the subproblem.

   /* each assignment constraint defines a block */
   for{j in TASKS}
      AssignmentCon[j].block = j;

   solve with milp / logfreq=1000
      decomp        =()
      decomp_subprob=(algorithm=nspure);

   /* each knapsack constraint defines a block */
   for{j in TASKS}
      AssignmentCon[j].block = .;
   for{i in MACHINES}
      KnapsackCon[i].block = i;

   solve with milp / decomp=();
quit;

The solution summaries are displayed in Output 14.2.1.

Output 14.2.1: Solution Summaries

The OPTMODEL Procedure

Solution Summary
Solver MILP
Algorithm Decomposition
Objective Function TotalProfit
Solution Status Optimal within Relative Gap
Objective Value 563.0000075
   
Relative Gap 0.0000986547
Absolute Gap 0.0555480556
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0
   
Best Bound 563.05555556
Nodes 3287
Iterations 3477
Presolve Time 0.01
Solution Time 8.61

Solution Summary
Solver MILP
Algorithm Decomposition
Objective Function TotalProfit
Solution Status Optimal
Objective Value 563
   
Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0
   
Best Bound 563
Nodes 3
Iterations 33
Presolve Time 0.01
Solution Time 0.24


The iteration log for both decompositions is shown in Output 14.2.2. This example is interesting because it shows the tradeoff between the strength of the relaxation and the difficulty of its resolution. In the first decomposition, the subproblems are totally unimodular and can be solved trivially. Consequently, each iteration of the decomposition algorithm is very fast. However, the bound obtained is as weak as the bound found in direct methods (the LP bound). The weaker bound leads to the need to enumerate more nodes overall. Alternatively, in the second decomposition, the subproblem is the knapsack problem, which is solved using MILP. In this case, the bound is much tighter and the problem solves in very few nodes. The tradeoff, of course, is that each iteration takes longer because solving the knapsack problem is not trivial. Another interesting aspect of this problem is that the subproblem coverage in the second decomposition is much smaller than that of the first decomposition. However, when dealing with MILP, it is not always the size of the coverage that determines the overall effectiveness of a particular choice of decomposition.

Output 14.2.2: Log

NOTE: There were 8 observations read from the data set WORK.PROFIT_DATA.              
NOTE: There were 8 observations read from the data set WORK.WEIGHT_DATA.              
NOTE: There were 8 observations read from the data set WORK.CAPACITY_DATA.            
NOTE: Problem generation will use 4 threads.                                          
NOTE: The problem has 192 variables (0 free, 0 fixed).                                
NOTE: The problem has 192 binary and 0 integer variables.                             
NOTE: The problem has 32 linear constraints (8 LE, 24 EQ, 0 GE, 0 range).             
NOTE: The problem has 384 linear constraint coefficients.                             
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The MILP presolver value AUTOMATIC is applied.                                  
NOTE: The MILP presolver removed 0 variables and 0 constraints.                       
NOTE: The MILP presolver removed 0 constraint coefficients.                           
NOTE: The MILP presolver modified 0 constraint coefficients.                          
NOTE: The presolved problem has 192 variables, 32 constraints, and 384 constraint     
      coefficients.                                                                   
NOTE: The MILP solver is called.                                                      
NOTE: The Decomposition algorithm is used.                                            
NOTE: The Decomposition algorithm is executing in single-machine mode.                
NOTE: The DECOMP method value USER is applied.                                        
NOTE: The subproblem solver chosen is an LP solver but at least one block has integer 
      variables.                                                                      
NOTE: The problem has a decomposable structure with 24 blocks. The largest block      
      covers 3.13% of the constraints in the problem.                                 
NOTE: The decomposition subproblems cover 192 (100.00%) variables and 24 (75.00%)     
      constraints.                                                                    
NOTE: The deterministic parallel mode is enabled.                                     
NOTE: The Decomposition algorithm is using up to 4 threads.                           
      Iter         Best       Master         Best       LP       IP   CPU  Real       
                  Bound    Objective      Integer      Gap      Gap  Time  Time       
NOTE: Starting phase 1.                                                               
         1       0.0000       8.9248            . 8.92e+00        .     0     0       
         4       0.0000       0.0000            .    0.00%        .     0     0       
NOTE: Starting phase 2.                                                               
         5     574.0000     561.1587            .    2.24%        .     0     0       
         6     568.8833     568.5610            .    0.06%        .     0     0       
         7     568.6464     568.6464     560.0000    0.00%    1.52%     0     0       
         7     568.6464     568.6464     560.0000    0.00%    1.52%     0     0       
NOTE: Starting branch and bound.                                                      
         Node  Active   Sols         Best         Best      Gap     CPU    Real       
                                  Integer        Bound             Time    Time       
            0       1      1     560.0000     568.6464    1.52%       0       0       
            5       7      2     563.0000     568.4782    0.96%       0       0       
          530     450      3     563.0000     565.6629    0.47%       1       1       
         1000     694      3     563.0000     565.0719    0.37%       3       3       
         2000     770      3     563.0000     564.4587    0.26%       5       5       
         3000     258      3     563.0000     564.0748    0.19%       7       8       
         3286       0      3     563.0000     563.0556    0.01%       8       8       
NOTE: The Decomposition algorithm used 4 threads.                                     
NOTE: The Decomposition algorithm time is 8.58 seconds.                               
NOTE: Optimal within relative gap.                                                    
NOTE: Objective = 563.0000075.                                                        
NOTE: The MILP presolver value AUTOMATIC is applied.                                  
NOTE: The MILP presolver removed 0 variables and 0 constraints.                       
NOTE: The MILP presolver removed 0 constraint coefficients.                           
NOTE: The MILP presolver modified 0 constraint coefficients.                          
NOTE: The presolved problem has 192 variables, 32 constraints, and 384 constraint     
      coefficients.                                                                   
NOTE: The MILP solver is called.                                                      
NOTE: The Decomposition algorithm is used.                                            
NOTE: The Decomposition algorithm is executing in single-machine mode.                
NOTE: The DECOMP method value USER is applied.                                        
NOTE: The problem has a decomposable structure with 8 blocks. The largest block       
      covers 3.13% of the constraints in the problem.                                 
NOTE: The decomposition subproblems cover 192 (100.00%) variables and 8 (25.00%)      
      constraints.                                                                    
NOTE: The deterministic parallel mode is enabled.                                     
NOTE: The Decomposition algorithm is using up to 4 threads.                           
      Iter         Best       Master         Best       LP       IP   CPU  Real       
                  Bound    Objective      Integer      Gap      Gap  Time  Time       
NOTE: Starting phase 1.                                                               
         1       0.0000       7.0000            . 7.00e+00        .     0     0       
         5       0.0000       0.0000            .    0.00%        .     0     0       
NOTE: Starting phase 2.                                                               
         .     820.0000     549.0000     549.0000   33.05%   33.05%     0     0       
         6     815.4074     549.0000     549.0000   32.67%   32.67%     0     0       
         7     678.4667     549.0000     549.0000   19.08%   19.08%     0     0       
         8     650.1852     549.0000     549.0000   15.56%   15.56%     0     0       
         9     638.8750     549.0000     549.0000   14.07%   14.07%     0     0       
         .     638.8750     549.0000     549.0000   14.07%   14.07%     0     0       
        10     638.8750     549.0000     549.0000   14.07%   14.07%     0     0       
        12     594.2000     549.0000     549.0000    7.61%    7.61%     0     0       
        13     591.7143     549.0000     549.0000    7.22%    7.22%     0     0       
        15     584.4545     558.0000     556.0000    4.53%    4.87%     0     0       
        16     577.8571     558.7143     556.0000    3.31%    3.78%     0     0       
        17     569.0000     559.0769     556.0000    1.74%    2.28%     0     0       
        19     567.3333     562.6667     559.0000    0.82%    1.47%     0     0       
         .     567.3333     562.9231     559.0000    0.78%    1.47%     0     0       
        20     564.5385     562.9231     559.0000    0.29%    0.98%     0     0       
        22     564.0000     564.0000     559.0000    0.00%    0.89%     0     0       
        22     564.0000     564.0000     559.0000    0.00%    0.89%     0     0       
NOTE: Starting branch and bound.                                                      
         Node  Active   Sols         Best         Best      Gap     CPU    Real       
                                  Integer        Bound             Time    Time       
            0       1      5     559.0000     564.0000    0.89%       0       0       
            1       3      6     560.0000     564.0000    0.71%       0       0       
            2       0      8     563.0000     563.0000    0.00%       0       0       
NOTE: The Decomposition algorithm used 4 threads.                                     
NOTE: The Decomposition algorithm time is 0.20 seconds.                               
NOTE: Optimal.                                                                        
NOTE: Objective = 563.