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
Re: [Help-glpk] Suggestions for GLPK
Hello Emanuele You should join the mailing list if you wish to post. Moreover, your subject line Suggestions for GLPK is not especially clear and it would help both you and those later wishing to search the archives if your post was more precisely titled. To: help-glpk@gnu.org Subject: Suggestions for GLPK From: Emanuele Miucci 1kron...@gmail.com Date: Thu, 31 May 2012 12:09:06 +0200 Dear GLPK group, I'm Emanuele a PhD student in TLC engeneering at the University of Rome Sapienza. TLC engineering? What is that? I'm using GLPK to solve an optimization problem: the input files (.mod and .dat) are written by a C program, and then they are used calling glpsol.exe with a system(). After the solve command in .mod file I've put a check on the results because I want that the system() returns 0 only if the optimal solution is found, otherwise it has to return a number different from 0. If I use GLPK v.4.45 everything works: the solver performs the check when the optimal solution is found and when it's not found. But if I use GLPK v.4.47 the check is performed only when the optimal solution is found. Can you give me some suggestions? Do you know another way to do these operations? Thanks a lot for your attention! Best regards Emanuele As you correctly noted, the GLPSOL interface does not offer a rich set of return codes. However I was not aware of the change in behavior between versions 4.45 and 4.47 you mention. As a consequence of your query, I will add a new Exit status section to the GLPK wikibook: http://en.wikibooks.org/wiki/GLPK/Using_GLPSOL But I need confirmation from Andrew here: 0 = solver completed successfully but does not mean that an optimal solution was necessarily found -- the solver may have detected a proven infeasibility for instance / this exit status corresponds to 0 being returned from the appropriate solver call, one of: 'glp_simplex', 'glp_exact', 'glp_interior', or 'glp_intopt' else non-zero I think that the GLPK API manual should also be updated to record this information. Getting back to your original question. If you code using the GLPK APIs (rather than invoke the 'system' function), you can examine the value returned by the (above mentioned) solver call and respond accordingly (more details in the API manual). Moreover, GLPK offers APIs to read in MathProg models and write out the solutions in various formats. Otherwise you can continue with the 'stdlib.h' 'system' call, redirect the GLPSOL terminal output to a text file, and then read this file in and examine its contents (someone who uses Windows might be able to help with the redirect syntax for that system). Personally I would use 'Boost.String_Algo' or even 'Boost.Regex' C++ libraries for the text scanning part (but you could also use standard C string functions): http://www.boost.org/doc/libs/1_49_0/doc/html/string_algo.html http://www.boost.org/doc/libs/1_49_0/libs/regex/doc/html/index.html The first suggestion is programmatically cleaner. The second option would need to be updated whenever GLPK modifies its terminal reporting. HTH, Robbie --- Robbie Morrison PhD student -- policy-oriented energy system simulation Technical University of Berlin (TU-Berlin), Germany University email (redirected) : morri...@iet.tu-berlin.de Webmail (preferred) : rob...@actrix.co.nz [from Webmail client] ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Suggestions
I've been trying GLPK for a month now and I have some suggestions for enhancement that would make the package more attractive (at least to me!). Thank you for suggestions. 1) The possibility to specify that the matrix is symmetric and therefore use half the storage. I've never met lp/mip problems having symmetric matrices. Could you provide an example? 2) The possibility to use normal matrix storage (instead of sparse). For a dense matrix that would save half the storage again. On api level the user cannot work with the normal matrix. It is implemented internally in the interior-point solver. 3) The possibility to use an initial point in the lpx_interior method. Probably this feature would be useful. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
