[Help-glpk] Asking help on an issue of solving via glpk
Hi everybody, I would like to ask a rather simple question, at least for the Gurus of GLPK . I have a very large and difficult optimization problem to solve. GLPK works for days and still it does not find any solution. On the other hand, I have manage to get a good solution (which I do not know if it is optimal or just near optimal, instead) using Computational Intelligence heuristics. The question is : is it possible to "feed" GLPK with this solution and force GLPK to use this solution as a starting point for further searching process? If I can do so, I hope that GLPK would be helped to find at least a better solution compared with that found using heuristics, even if it is not optimal. Please, note that I use Mathprog language and the terminal to run GLPK (command prompt). Nevertheless, being beginner with the capabilities of GLPK, I would appreciate a detailed answer with analytical description of steps I have to follow in order to achieve the above mentioned goal. Thanks for your time and for any possible answer. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
Hello Johannes, first of all it is expected that finding heuristic solutions is much faster than using an MIP solver. For mixed integers problems you can use the callback function of the GLPK library to provide heuristic solutions. If you are only interested in having a good solution and not an optimal one you can provide a time limit or a gap limit to the GLPK solver. Large mixed integer problems are usually not solved by brute force in a MIP solver but by applying heuristics like column generation to guide the solver. Without any further knowledge of the kind of problem you try to solve it is hard to tell how it could be made more amenable to GLPK. Best regards Heinrich Schuchardt On 02/08/2016 08:58 PM, ΤΑΣΣΟΠΟΥΛΟΣ ΙΩΑΝΝΗΣ wrote: > Hi everybody, > I would like to ask a rather simple question, at least for the Gurus of > GLPK. > I have a very large and difficult optimization problem to solve. GLPK > works for days and still it does not find any solution. On the other > hand, I have manage to get a good solution (which I do not know if it is > optimal or just near optimal, instead) using Computational Intelligence > heuristics. The question is : is it possible to "feed" GLPK with this > solution and force GLPK to use this solution as a starting point for > further searching process? If I can do so, I hope that GLPK would be > helped to find at least a better solution compared with that found using > heuristics, even if it is not optimal. > Please, note that I use Mathprog language and the terminal to run GLPK > (command prompt). Nevertheless, being beginner with the capabilities of > GLPK, I would appreciate a detailed answer with analytical description > of steps I have to follow in order to achieve the above mentioned goal. > Thanks for your time and for any possible answer. > > > ___ > Help-glpk mailing list > Help-glpk@gnu.org > https://lists.gnu.org/mailman/listinfo/help-glpk > ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
Hi Johannes, Try to use the proximity option and mipgap option as well, as mentioned by Heinrich. For example, glpsol --math yourMIP_mathprog_model.mod --proxy 200 --mir --mipgap 0.2 Note: 200 in the example above is in seconds. Reggards, Noli ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
Thanks a lot to all of them who answered my question. Should I suppose that the answer to my question is negative, i.e. it is not possible to force GLPK to start searching from a particular point? For your information, my project concerns the school timetabling problem. As I mentioned in my previous mail, I got a solution provided by Particle Swarm Optimization, but I do not know if this solution is optimal or not. Any way, I found your answers very helpful. What I wrote in command prompt was : glpsol --cuts --pcost --math my_model.mod --data my_data.dat --proxy 200 --mir --mipgap 0.2 The results were good and produced fast. Nevertheless, I mast say that I have no idea about what --cuts, --pcost, --proxy, --mir and --mipgap 0.2 mean or stand for. Could any one inform me in a few words about the meaning of all these? Or better, is there any text explaining all these? Please note that the asked information is very crucial to me, as I shall be in a position to explain the way or the method I followed in order to discover these better solutions, compared with those found by Particle Swarm optimization. Thanks for one more time 2016-02-08 23:21 GMT+02:00 Noli Sicad : > Hi Johannes, > > Try to use the proximity option and mipgap option as well, as > mentioned by Heinrich. > > For example, > > glpsol --math yourMIP_mathprog_model.mod --proxy 200 --mir --mipgap 0.2 > > Note: 200 in the example above is in seconds. > > Reggards, Noli > > ___ > Help-glpk mailing list > Help-glpk@gnu.org > https://lists.gnu.org/mailman/listinfo/help-glpk > -- Ioannis X. Tassopoulos ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
Hi John, glpsol --help The above will give you all the help / info / options. Here's the one, the results that I copy and paste for the MIP solver options (below) Options specific to MIP solver: --nomip consider all integer variables as continuous (allows solving MIP as pure LP) --first branch on first integer variable --lastbranch on last integer variable --mostf branch on most fractional variable --drtom branch using heuristic by Driebeck and Tomlin (default) --pcost branch using hybrid pseudocost heuristic (may be useful for hard instances) --dfs backtrack using depth first search --bfs backtrack using breadth first search --bestp backtrack using the best projection heuristic --bestb backtrack using node with best local bound (default) --intopt use MIP presolver (default) --nointoptdo not use MIP presolver --binarizereplace general integer variables by binary ones (assumes --intopt) --fpump apply feasibility pump heuristic --proxy [nnn] apply proximity search heuristic (nnn is time limit in seconds; default is 60) --gomory generate Gomory's mixed integer cuts --mir generate MIR (mixed integer rounding) cuts --cover generate mixed cover cuts --clique generate clique cuts --cutsgenerate all cuts above --mipgap tol set relative mip gap tolerance to tol --minisat translate integer feasibility problem to CNF-SAT and solve it with MiniSat solver --objbnd boundadd inequality obj <= bound (minimization) or obj >= bound (maximization) to integer feasibility problem (assumes --minisat) ~~ Regards, Noli On 2/9/16, john tass wrote: > Thanks a lot to all of them who answered my question. > Should I suppose that the answer to my question is negative, i.e. it is not > possible to force GLPK to start searching from a particular point? > For your information, my project concerns the school timetabling problem. > As I mentioned in my previous mail, I got a solution provided by Particle > Swarm Optimization, but I do not know if this solution is optimal or not. > Any way, I found your answers very helpful. What I wrote in command prompt > was : > glpsol --cuts --pcost --math my_model.mod --data my_data.dat --proxy 200 > --mir --mipgap 0.2 > The results were good and produced fast. > Nevertheless, I mast say that I have no idea about what --cuts, --pcost, > --proxy, --mir and --mipgap 0.2 mean or stand for. > Could any one inform me in a few words about the meaning of all these? Or > better, is there any text explaining all these? > Please note that the asked information is very crucial to me, as I shall be > in a position to explain the way or the method I followed in order to > discover these better solutions, compared with those found by Particle > Swarm optimization. > Thanks for one more time > > 2016-02-08 23:21 GMT+02:00 Noli Sicad : > >> Hi Johannes, >> >> Try to use the proximity option and mipgap option as well, as >> mentioned by Heinrich. >> >> For example, >> >> glpsol --math yourMIP_mathprog_model.mod --proxy 200 --mir --mipgap 0.2 >> >> Note: 200 in the example above is in seconds. >> >> Regards, Noli >> ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
> > Should I suppose that the answer to my question is negative, i.e. it is > not possible to force GLPK to start searching from a particular point? > Since you are using MathProg, you can duplicate the objective function as a constraint and specify the value you obtained with your heuristic as an upper limit (I'm assuming you are minimising). This way the search will not investigate nodes with higher objective values, saving time, effectively duplicating what would happen if the solver found the solution on its own. However this may make each iteration slower, depending on the structure of your problem. Also note that the solver output will not indicate the correct gap until a new solution is found. Nevertheless, I mast say that I have no idea about what --cuts, --pcost, > --proxy, --mir and --mipgap 0.2 mean or stand for. > Could any one inform me in a few words about the meaning of all these? Or > better, is there any text explaining all these? > Some further info in addition to what Noli sent: --pcost enables "pseudocost branching with strong branching initialisation". A google search with the quoted sentence will find lots of additional information. --cuts enables all the implemented cut families, so --mir is redundant. Cuts are constraints added during the search that remove non integer solutions (like the current lp relaxation). --mipgap 0.2 instructs the solver to stop when the best solution found is within 20% of the lower (or upper) limit. Therefore the solution is certain to be at most 20% off the optimum. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Asking help on an issue of solving via glpk
Thanks guys, all these are very interesting. I get down to work. Thanks again. 2016-02-09 1:08 GMT+02:00 Chris Matrakidis : > Should I suppose that the answer to my question is negative, i.e. it is >> not possible to force GLPK to start searching from a particular point? >> > > Since you are using MathProg, you can duplicate the objective function as > a constraint and specify the value you obtained with your heuristic as an > upper limit (I'm assuming you are minimising). This way the search will not > investigate nodes with higher objective values, saving time, effectively > duplicating what would happen if the solver found the solution on its own. > However this may make each iteration slower, depending on the structure of > your problem. Also note that the solver output will not indicate the > correct gap until a new solution is found. > > Nevertheless, I mast say that I have no idea about what --cuts, --pcost, >> --proxy, --mir and --mipgap 0.2 mean or stand for. >> Could any one inform me in a few words about the meaning of all these? Or >> better, is there any text explaining all these? >> > > Some further info in addition to what Noli sent: > --pcost enables "pseudocost branching with strong branching > initialisation". A google search with the quoted sentence will find lots of > additional information. > --cuts enables all the implemented cut families, so --mir is redundant. > Cuts are constraints added during the search that remove non integer > solutions (like the current lp relaxation). > --mipgap 0.2 instructs the solver to stop when the best solution found is > within 20% of the lower (or upper) limit. Therefore the solution is certain > to be at most 20% off the optimum. > > > Best Regards, > > Chris Matrakidis > -- Ioannis X. Tassopoulos ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
