[Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.

[Sylvain Fournier]

Hello,

I embed the linear GLPK solver into my own Branch-and-Price algorithm and until now I am very satisfied with the performance and stability of the tool.

Lately I tested my algorithm on greater models (typically about 5600 constraints and 57000 variables) and I'd like to know if there is some way to make the master problem solving (using GLPK) faster, either using some GLPK routine before solving or configuring better GLPK parameters. The real time consuming process is when I have to "remove" some variables (at branching): in this case I don't remove them from the model (at least not the ones that are basic) but I just set both their bounds to 0. But then GLPK has some difficulties to escape from infeasibility.

I am sending you an example of the output GLPK gives (in this example, the final solution is found after over 50 seconds and 40000 iterations). The reason why it doesn't start from iteration 1 is that I use the same model from the beginning until the end of the algorithm, adding and/or "removing" variables between each run.

Now my question is: should I solve the model from scratch in the case I have to remove a lot of variables? Or is there a parameter configuration I should use in my specific case?

For your information, I try to solve a set covering problem with few other constraints, so my variables are all between 0 and 1 and their coefficients in the covering constraints are 0 or 1. If needed I could send a model file that can be quite big, though.
---
GLPK Simplex Optimizer, v4.49
5609 rows, 57216 columns, 442641 non-zeros
 184524: obj =   8.477862291e+04  infeas =  1.995e+03 (532)
 185000: obj =   8.495146783e+04  infeas =  1.026e+03 (476)
 185500: obj =   8.524330196e+04  infeas =  6.856e+02 (429)
 186000: obj =   8.546210680e+04  infeas =  5.689e+02 (399)
 186500: obj =   8.585633471e+04  infeas =  4.434e+02 (362)
 187000: obj =   8.628479341e+04  infeas =  3.730e+02 (339)
 187500: obj =   8.677416460e+04  infeas =  3.022e+02 (305)
 188000: obj =   8.716531305e+04  infeas =  2.683e+02 (293)
 188500: obj =   8.758187048e+04  infeas =  2.177e+02 (274)
 189000: obj =   8.769307123e+04  infeas =  1.987e+02 (262)
 189500: obj =   8.826045208e+04  infeas =  1.603e+02 (239)
 190000: obj =   8.846620422e+04  infeas =  1.418e+02 (220)
 190500: obj =   8.884405764e+04  infeas =  1.126e+02 (200)
 191000: obj =   8.911873348e+04  infeas =  9.864e+01 (187)
 191500: obj =   8.949984050e+04  infeas =  7.952e+01 (169)
 192000: obj =   8.977483328e+04  infeas =  6.772e+01 (158)
 192500: obj =   9.030200817e+04  infeas =  5.103e+01 (128)
 193000: obj =   9.050686489e+04  infeas =  4.413e+01 (121)
 193500: obj =   9.092975478e+04  infeas =  3.440e+01 (101)
 194000: obj =   9.130469718e+04  infeas =  2.631e+01 (87)
 194500: obj =   9.195376372e+04  infeas =  1.740e+01 (64)
 195000: obj =   9.232221673e+04  infeas =  1.151e+01 (52)
 195500: obj =   9.284730302e+04  infeas =  3.312e+00 (24)
*195867: obj =   9.311871624e+04  infeas =  4.626e-15 (7)
*196000: obj =   9.298279802e+04  infeas =  1.007e-14 (7)
*196500: obj =   9.211512017e+04  infeas =  5.870e-15 (6)
*197000: obj =   9.168395897e+04  infeas =  2.264e-14 (6)
*197500: obj =   9.103887754e+04  infeas =  8.461e-15 (6)
*198000: obj =   9.070511611e+04  infeas =  7.326e-15 (5)
*198500: obj =   9.013085368e+04  infeas =  1.095e-14 (5)
*199000: obj =   8.999240819e+04  infeas =  6.093e-15 (5)
*199500: obj =   8.948911192e+04  infeas =  1.542e-14 (5)
*200000: obj =   8.935636006e+04  infeas =  1.055e-14 (5)
*200500: obj =   8.906060307e+04  infeas =  5.671e-15 (5)
*201000: obj =   8.889092104e+04  infeas =  9.518e-15 (4)
*201500: obj =   8.859711706e+04  infeas =  9.632e-15 (4)
*202000: obj =   8.850120391e+04  infeas =  9.433e-15 (4)
*202500: obj =   8.826286212e+04  infeas =  1.631e-14 (4)
*203000: obj =   8.817078413e+04  infeas =  7.893e-15 (4)
*203500: obj =   8.804909674e+04  infeas =  7.945e-15 (4)
*204000: obj =   8.800114404e+04  infeas =  6.245e-15 (4)
*204500: obj =   8.790454714e+04  infeas =  8.575e-15 (4)
*205000: obj =   8.780247089e+04  infeas =  8.627e-15 (3)
*205500: obj =   8.764453035e+04  infeas =  1.192e-14 (3)
*206000: obj =   8.760591328e+04  infeas =  5.890e-15 (3)
*206500: obj =   8.741195775e+04  infeas =  6.505e-15 (3)
*207000: obj =   8.738110421e+04  infeas =  7.170e-15 (3)
*207500: obj =   8.728064143e+04  infeas =  1.404e-14 (3)
*208000: obj =   8.724302418e+04  infeas =  1.300e-14 (3)
*208500: obj =   8.715632640e+04  infeas =  1.440e-14 (3)
*209000: obj =   8.710498074e+04  infeas =  1.060e-14 (3)
*209500: obj =   8.703230368e+04  infeas =  8.704e-15 (3)
*210000: obj =   8.700284952e+04  infeas =  1.543e-14 (3)
*210500: obj =   8.695211680e+04  infeas =  1.053e-14 (3)
*211000: obj =   8.693488255e+04  infeas =  1.606e-14 (3)
*211500: obj =   8.688837605e+04  infeas =  1.418e-14 (3)
*212000: obj =   8.688079563e+04  infeas =  9.412e-15 (3)
*212500: obj =   8.683924443e+04  infeas =  1.248e-14 (3)
*213000: obj =   8.683410100e+04  infeas =  7.097e-15 (3)
*213500: obj =   8.679797445e+04  infeas =  1.796e-14 (3)
*214000: obj =   8.678434306e+04  infeas =  1.350e-14 (3)
*214500: obj =   8.673684483e+04  infeas =  1.628e-14 (3)
*215000: obj =   8.670740559e+04  infeas =  1.143e-14 (3)
*215500: obj =   8.661954412e+04  infeas =  1.289e-14 (3)
*216000: obj =   8.660799217e+04  infeas =  1.677e-14 (3)
*216500: obj =   8.656506517e+04  infeas =  9.777e-15 (3)
*217000: obj =   8.655457175e+04  infeas =  2.034e-14 (3)
*217500: obj =   8.650503085e+04  infeas =  1.224e-14 (3)
*218000: obj =   8.648445437e+04  infeas =  1.825e-14 (3)
*218500: obj =   8.645254391e+04  infeas =  1.875e-14 (3)
*219000: obj =   8.643635972e+04  infeas =  1.703e-14 (3)
*219500: obj =   8.640302368e+04  infeas =  1.183e-14 (3)
*220000: obj =   8.639636539e+04  infeas =  1.740e-14 (3)
*220500: obj =   8.637719928e+04  infeas =  1.480e-14 (3)
*221000: obj =   8.636110863e+04  infeas =  1.800e-14 (3)
*221500: obj =   8.632864402e+04  infeas =  1.960e-14 (3)
*222000: obj =   8.630773847e+04  infeas =  2.122e-14 (3)
*222500: obj =   8.628781348e+04  infeas =  1.885e-14 (3)
*223000: obj =   8.628491632e+04  infeas =  1.721e-14 (3)
*223500: obj =   8.626956052e+04  infeas =  1.480e-14 (3)
*224000: obj =   8.626295607e+04  infeas =  3.034e-14 (3)
*224500: obj =   8.625357631e+04  infeas =  1.348e-14 (3)
*225000: obj =   8.625218764e+04  infeas =  1.569e-14 (3)
*225500: obj =   8.624515500e+04  infeas =  1.173e-14 (3)
*225775: obj =   8.624472901e+04  infeas =  1.272e-14 (3)
OPTIMAL SOLUTION FOUND

---

Regards,

Sylvain Fournier

Analista de Pesquisa Operacional
48 3239-2423
WPLEX Software Ltda.
Rod SC 401 no. 8600 Corporate Park bloco 5 sala 101
88050-000 Santo Antônio de Lisboa, Florianópolis SC +55 48 3239-2400
wplex.com.br