Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
Thanks for your answer Andrew. When I have to remove a basic variable, I fix its bound using the GLP_FX constant as Heinrich suggested, and when I have to remove a non-basic constraint, I unbind it using GLP_FR, before removing them from the problem object in a further iteration where the variable is no more basic or the constraint becomes basic. I used this logic to obtain the output I sent in the first e-mail. If I had directly removed from the problem object at least either one basic variable or one non-basic constraint, the output would have started at iteration 1 with an objective value of 0. Note that the infeasibility value of 1995 at the first iteration must be the cause of the rather high processing time. In this example really a lot of variables and constraints were removed using the logic I described (although now I don't know exactly how many). The other possibility you give is making a variable non-basic (instead of fixing its bounds) or making a constraint basic (instead of freeing its bounds). Would it make GLPK solve the problem faster? How can it be done? Is it just setting the status of the given variable/constraint? (but this would make the basis invalid, wouldn't it?) *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 [image: WPLEX] 2014-03-22 4:23 GMT-03:00 Andrew Makhorin m...@gnu.org: Now my question is: should I solve the model from scratch in the case I have to remove a lot of variables? Generally, not. Or is there a parameter configuration I should use in my specific case? Glp_simplex always starts the search from the current basis which is provided in glp_prob by means of the statuses of rows and columns. This allows to continue the search (re-optimize) efficiently if you obtain an optimal basis, change the lp, and then call glp_simplex once again. However, in this case you need to make sure that the row/column statuses define a correct basis--the number of basic auxiliary/structural variables should be equal to the number of rows, and the basis matrix consisting of columns of basic variables, including unity ones for auxiliary variables, should be non-singular. For example, removing an active (more precisely, binding) constraint, i.e. a non-basic row, makes the basis incorrect. To avoid this you may either remove the row logically by making it free (unbounded) rather to remove it physically, or make the row basic (non-binding) before removing it by changing the row/column statuses in an appropriate way. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
When I have to remove a basic variable, I fix its bound using the GLP_FX constant as Heinrich suggested, and when I have to remove a non-basic constraint, I unbind it using GLP_FR, before removing them from the problem object in a further iteration where the variable is no more basic or the constraint becomes basic. I used this logic to obtain the output I sent in the first e-mail. If I had directly removed from the problem object at least either one basic variable or one non-basic constraint, the output would have started at iteration 1 with an objective value of 0. Make sure that the lp presolver is disabled and no basis construction routine (like glp_adv_basis) is used when you call glp_simplex to perform reoptimization. Note that the infeasibility value of 1995 at the first iteration must be the cause of the rather high processing time. In this example really a lot of variables and constraints were removed using the logic I described (although now I don't know exactly how many). The other possibility you give is making a variable non-basic (instead of fixing its bounds) or making a constraint basic (instead of freeing its bounds). Would it make GLPK solve the problem faster? How can it be done? Is it just setting the status of the given variable/constraint? (but this would make the basis invalid, wouldn't it?) Rather than to remove active rows and basic columns immediately, to keep the basis valid (that is necessary for reoptimization) you may make the rows free (unbounded) and the columns fixed. It may happen that after reoptimization some of these rows/columns become non-active/non-basic, in which case you can safely remove them from the working lp to reduce its size. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
Please, add the missing information to glpk.pdf as indicated below: Okay. glp_del_rows invalidates the basis factorization. glp_del_cols invalidates the basis factorization if the column is basic. More precisely, any change in the problem object that affects the basis matrix (adding rows, changing row/column of the constraint matrix, etc.) invalidates the basis factorization. After invalidation of the basis factorization glp_warm_up has to be called before calling glp_simplex. Not needed--glp_simplex does that automatically, if necessary. However, if the lp preprocessor is used, glp_simplex does not compute the basis factorization for the original lp at exit. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
Now my question is: should I solve the model from scratch in the case I have to remove a lot of variables? Generally, not. Or is there a parameter configuration I should use in my specific case? Glp_simplex always starts the search from the current basis which is provided in glp_prob by means of the statuses of rows and columns. This allows to continue the search (re-optimize) efficiently if you obtain an optimal basis, change the lp, and then call glp_simplex once again. However, in this case you need to make sure that the row/column statuses define a correct basis--the number of basic auxiliary/structural variables should be equal to the number of rows, and the basis matrix consisting of columns of basic variables, including unity ones for auxiliary variables, should be non-singular. For example, removing an active (more precisely, binding) constraint, i.e. a non-basic row, makes the basis incorrect. To avoid this you may either remove the row logically by making it free (unbounded) rather to remove it physically, or make the row basic (non-binding) before removing it by changing the row/column statuses in an appropriate way. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
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 4 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) 19: 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) *20: 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) *21: 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 =
Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
@Andrew: Please, add the missing information to glpk.pdf as indicated below: glp_del_rows invalidates the basis factorization. glp_del_cols invalidates the basis factorization if the column is basic. After invalidation of the basis factorization glp_warm_up has to be called before calling glp_simplex. On 21.03.2014 20:46, Sylvain Fournier wrote: 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 Hello Sylvain, in glp_set_col_bnds you should also set the type to GLP_FX when you set upper and lower bound to the same value. Best regards Heinrich Schuchardt ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
