DM826 - Modelling and Solving Constrained Optimization Problems
Sheet 6, Spring 2011

This assignment is about “delayed column generation”. The content builds on the elements you have been given and it may be a good exercise. However, this method is not in the syllabus for the final written exam and other exercises in the sheets published may be more important. Make sure you finished with them before tackling this one.

Exercise: Delayed Column Generation for Bin Packing

A set covering formulation for the bin packing problem has the disadvantage of having an exponential number of variables, each representing a feasible packing for a bin. In this exercise, we learn how to generate the packings dynamically thus avoiding to generate many packings that would not be anyway selected.

The bin packing problem asks to find a distribution in bins of capacity κ for a given set of items [n]:={1,…,n} with nonnegative size si such that the number of used bins is minimized. The set covering formulation for this problem is:

min
 
∑
S ∈  S
 xs
subject to
 
∑
S ∈  S
 aSi xS ≥ 1      ∀ i ∈ [n]
 xS ∈ ℤ+      ∀ S ∈  S
     (IP)

Here, the set S:= {S⊆ [n] | ∑i:i ∈ S si ≤ κ} contains all feasible packing patterns.

Since S can be of exponential size we will use the following delayed column generation approach, which is made possible by the use of the simplex algorithm.

We initialize the problem (IP), denoted in this context as the (restricted) master problem with a set of n variables representing packings of a single item per bin.

Once the linear relaxation of the initial master problem is solved we have to search for variables representing “better” packings, i.e, packing patterns that reduce the overall costs. In linear programming theory and sensitivity analysis we saw what are the conditions for a new variable to be worth entering in the basis. Here, this corresponds to say that for a given solution y* of the dual of the linear relaxation of the (restricted) master program, we have to find a variable xS

cS − 
 
∑
i ∈ S
 yi* < 0 

Since all variables xS have an objective coefficient cS=1 this is equivalent to searching a variable xS for which ∑i∈ Syi*>1.


Formulate the pricing problem (aka subproblem) of the set covering formulation of bin packing as a combinatorial optimization problem. Which problem encountered in class does it remind you? In class we saw an integer programming formulation of it. However the problem can be solved efficiently (in pseudo-polynomial time) by dynamic programming.


In the following you are presented with the output of a program based on SCIP that implements the column generation procedure and runs it on the instance u20_00. This instance has 20 items and κ=150. The sizes si of the items are

012345678910111213141516171819
9469329670845878258058668324986042434339


Initially, only the 20 variables representing one single item are included in the restricted master problem. The solution to its linear relaxation is obviously:


 time | node  | left  |LP iter| mem |mdpt |frac |vars |cons |ccons|cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
t 0.0s|     1 |     0 |     0 | 100k|   0 |   - |  20 |  20 |  20 |   0 |   0 |   0 |   0 |   0 |      --      | 2.000000e+01 |    Inf 
Solution:
         0         1         2         3         4         5         6         7         8         9        10        11        12        13        14        15        16        17        18        19
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

The output shows the typical display of SCIP plus the values of the original variables if they are larger than zero.

How did SCIP solved the initial problem?

[In order to answer this question and later questions you may need to recall what the cryptic abbreviations for the columns mean, which are displayed during the solving process of SCIP. Type "display display" in the SCIP interactive shell to get an explanation of them. If a letter appears in front of a display row, it indicates, which heuristic found the new primal bound, a star representing an integral LP-relaxation. Typing "display heuristics" gives you a list of the heuristics including their letters.]

The next part of the output exhibits the dual values corresponding to each constraint # together with the original sizes of the items to which the constraints refer:


Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39

Explain the dual values in the light of the complementary slackness theorem.

At this point the subproblem is solved and a new variable inserted.

Which items will be represented by the new variable? In other terms, what would be the solution calculated by the pricing algorithm?

SCIP output with information replaced by ...


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of ... 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:    ...

Once the new variable is inserted in the master problem, the master problem is solved again. 


  0.0s|     1 |     0 |    23 | 113k|   0 |   0 |  21 |  20 |  20 |  21 |  20 |   0 |   0 |   0 |      --      | 2.000000e+01 |    Inf 
r 0.0s|     1 |     0 |    23 | 113k|   0 |   - |  21 |  20 |  20 |  21 |  20 |   0 |   0 |   0 |      --      | 1.700000e+01 |    Inf 
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        16        17        1819-2-8-13-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Why did SCIP report two lines in its output display? What happened? Was the new variable selected?

The program then does another iteration finding a new variable to insert and a new primal solution that provides an upper bound to the problem.

  
Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00 -0.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:     18   16    2
r 0.0s|     1 |     0 |    26 | 115k|   0 |   - |  22 |  20 |  20 |  22 |  20 |   0 |   0 |   0 |      --      | 1.600000e+01 |    Inf 
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Then:

  
Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00  1.00  1.00 -0.00 -0.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:     17   16    8
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00 -0.00  1.00  1.00  1.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:     18   17   19
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  0.50  0.50  0.50 -0.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      6   10   13
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00 -0.00  1.00  1.00 -0.00  1.00  1.00 -0.00  1.00 -0.00 -0.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      6   17    2
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00  1.00 -0.00  1.00  1.00 -0.00 -0.00  1.00 -0.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      6   18    8
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00 -0.00  1.00  1.00  1.00  1.00  1.00 -0.00  1.00 -0.00  1.00  1.00 -0.00  1.00  1.00  1.00 -0.00 -0.00  1.00
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 3.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      6   16   19
Solution:
         0         1         3         4         5         6         7         9        10        11        12        14        15        1719-2-8-13-  18-16-2-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  0.33  1.00  1.00  1.00  0.33  1.00  0.33  1.00  0.67  1.00  1.00 -0.00  1.00  1.00  0.33  0.33  0.33  0.33
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 2.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:     11   15
r 0.0s|     1 |     0 |    37 | 123k|   0 |   4 |  29 |  20 |  20 |  29 |  20 |   0 |   0 |   0 |      --      | 1.500000e+01 |    Inf 
Solution:
         0         1         3         4         5         7         9        12        1419-2-8-13-  18-16-2-  17-16-8- 18-17-19-  6-10-13-    11-15-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

What happened exactly in the above iterations? How many variables where added to the master problem? How many were selected to enter in the solution?

  
Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  0.33  1.00  1.00  1.00  0.33  1.00  0.33  1.00  0.67  1.00  1.00 -0.00  1.00 -0.00  0.33  0.33  0.33  0.33
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 2.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      1   11
Solution:
         0         1         3         4         5         7         9        12        1419-2-8-13-  18-16-2-  17-16-8- 18-17-19-  6-10-13-    11-15-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  1.00  0.33  1.00  1.00  1.00  0.33  1.00  0.33  1.00  0.67 -0.00  1.00 -0.00  1.00  1.00  0.33  0.33  0.33  0.33
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 2.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      1   15
Solution:
         0         1         3         4         5         7         9        12        1419-2-8-13-  18-16-2-  17-16-8- 18-17-19-  6-10-13-    11-15-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       1.00  0.50  0.33  1.00  1.00  1.00  0.33  1.00  0.33  1.00  0.67  0.50  1.00 -0.00  1.00  0.50  0.33  0.33  0.33  0.33
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39

Calculate again the solution of the pricing problem.

The program then iterates for other several iterations and arrives finally to an end.

From the following output can you tell how many iterations the program performed?

  
Solution:
  6-16-19-    11-15-     1-11-     1-15-      7-4-      9-4-   19-7-8-  16-8-12-     10-5-   13-2-0-     6-12-     18-3-     15-9-    17-14-
      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00      1.00

Dual values:
#             0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
dual       0.71  0.43  0.14  0.71  0.43  0.57  0.43  0.57  0.14  0.57  0.43  0.43  0.57  0.14  0.71  0.43  0.29  0.29  0.29  0.29
size         94    69    32    96    70    84    58    78    25    80    58    66    83    24    98    60    42    43    43    39
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X algorithm for pricing problem calculated reduced costs of 1.000000 X 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
New packing:      7   10
  0.0s|     1 |     0 |    94 | 169k|   0 |  14 |  62 |  20 |  20 |  37 |  20 |   0 |   0 |   0 | 8.571429e+00 | 1.400000e+01 |  63.33%
R 0.0s|     1 |     0 |    94 | 170k|   0 |  14 |  62 |  20 |  20 |  37 |  20 |   0 |   0 |   0 | 8.571429e+00 | 1.300000e+01 |  51.67%
s 0.0s|     1 |     0 |    94 | 171k|   0 |  14 |  62 |  20 |  20 |  37 |  20 |   0 |   0 |   0 | 8.571429e+00 | 1.200000e+01 |  40.00%
b 0.0s|     1 |     0 |    94 | 172k|   0 |   - |  62 |  20 |  20 |  37 |  20 |   0 |   0 |   0 | 8.571429e+00 | 9.000000e+00 |   5.00%
  0.0s|     1 |     0 |    94 | 171k|   0 |   - |  62 |  20 |  20 |  37 |  20 |   0 |   0 |   0 | 9.000000e+00 | 9.000000e+00 |   0.00%

What happened at the final stage? What did SCIP do in the 5 iterations after the packing 7 10 is added? Why it did not return to the pricing problem?

SCIP then terminates resuming the result and displaying the final solution. You can appreciate the huge improvement brought by the set covering formulation with delayed column generation solved via pricing by comparing its results (pricing.txt) with those of the assignment formulation (assignment.txt).

  
SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.01
Solving Nodes      : 1
Primal Bound       : +9.00000000000000e+00 (28 solutions)
Dual Bound         : +9.00000000000000e+00
Gap                : 0.00 %

primal solution:
================

objective value:                                    9
9-4                                                 1  (obj:1)
16-8-12                                             1  (obj:1)
10-5                                                1  (obj:1)
13-2-0                                              1  (obj:1)
18-3                                                1  (obj:1)
6-15-2                                              1  (obj:1)
7-1                                                 1  (obj:1)
17-11-19                                            1  (obj:1)
19-14                                               1  (obj:1)