Re: glpsol will not handle example
You need --math instead of --glp. Best Regards, Chris Matrakidis <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> Virus-free.www.avg.com <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2> On Sun, 12 Nov 2023 at 21:08, Michael Hennebry wrote: > > From the glpk manual, I copied example E.1 to ex1.gmpl . > glpsol did not like it: > [hennebry@fedora triangle-free]$ glpsol --glp ex1.gmpl > GLPSOL--GLPK LP/MIP Solver 5.0 > Parameter(s) specified in the command line: > --glp ex1.gmpl > Reading problem data from 'ex1.gmpl'... > ex1.gmpl:1: error: problem line missing or invalid > GLPK LP/MIP file processing error > [hennebry@fedora triangle-free]$ > > Here is ex1.gmpl: > # A TRANSPORTATION PROBLEM > # > # This problem finds a least cost shipping schedule that meets > # requirements at markets and supplies at factories. > # > # References: > # > Dantzig G B, "Linear Programming and Extensions." > # > Princeton University Press, Princeton, New Jersey, 1963, > # > Chapter 3-3. > set I; > /* canning plants */ > set J; > /* markets */ > param a{i in I}; > /* capacity of plant i in cases */ > param b{j in J}; > /* demand at market j in cases */ > param d{i in I, j in J}; > /* distance in thousands of miles */ > > param f; > /* freight in dollars per case per thousand miles */ > param c{i in I, j in J} := f * d[i,j] / 1000; > /* transport cost in thousands of dollars per case */ > var x{i in I, j in J} >= 0; > /* shipment quantities in cases */ > minimize cost: sum{i in I, j in J} c[i,j] * x[i,j]; > /* total transportation costs in thousands of dollars */ > s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i]; > /* observe supply limit at plant i */ > s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j]; > /* satisfy demand at market j */ > data; > > set I := Seattle San-Diego; > set J := New-York Chicago Topeka; > param a := Seattle > San-Diego350 > 600; > param b := New-York > Chicago > Topeka325 > 300 > 275; > param d :New-York > 2.5 > 2.5 > Seattle > San-Diego > Chicago > 1.7 > 1.8 > param f := 90; > end; > > What is going on and what can I do about it? > > -- > Michael henne...@mail.cs.ndsu.nodak.edu > "I was just thinking about the life of a pumpkin. Grow up in the sun, > happily entwined with others, and then someone comes along, > cuts you open, and rips your guts out." -- Buffy >
Re: glpk 5.0 release information
On Mon, 21 Dec 2020 at 01:38, Andrew Makhorin wrote: > This bug is not fixed yet, because both ssx_chuzc and ssx_chuzr will be > replaced by new versions. > Andrew, what are your plans for the next glpk versions? As you know I have some stuff that I would like to upstream. Best Regards, Chris Matrakidis <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> Virus-free. www.avg.com <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
Re: GLPK/glpsol gives different objective values for mip/nomip
On Tue, 6 Oct 2020 at 16:15, Domingo Alvarez Duarte wrote: > Testing GLPK with miplib2017 I noticed that GLPK/glpsol gives different > values for LP objective funcion value when a MIP problem is given with > the option --nomip , is this the expected behavior ? > Yes, this is expected. For a mip additional preprocessing is possible, a trivial example is that integer variable bounds can be tightened to the next integer. Best Regards, Chris Matrakidis
Updated script for miplib2017
Domingo mentioned looking at miplib2017 problems, which reminded me of this: I noticed some time ago that the current script offered with miplib2017 suffers from accuracy loss when checking the results, because it was parsing the solution file in printable form, which rounds values a bit. An example miplib result file is in http://plato.asu.edu/ftp/milp_res1/benchmark.glpk.1threads.7200s.res where in the last column many solutions are reported as "fail" or "error". I made an updated version that also uses a solution file in printable form, that offers more digits of accuracy (attached) and seems to work a lot better with a subset of miplib problems I used for testing. Best Regards, Chris Matrakidis run_glpk.sh Description: application/shellscript
Re: How hard would be to add "Indicator Constraints"
Should be fairly easy to do when branching, to me the hard part seems to be extending the api for this in a clean way. Best Regards, Chris Matrakidis On Mon, 5 Oct 2020 at 16:16, Erwin Kalvelagen < er...@amsterdamoptimization.com> wrote: > > Indicator constraints can be transformed into a normal constraint using > SOS1 (Special Ordered Set of type 1) variables. If the solver (like GLPK) > does not have SOS1 variables you can simulate this with binary variables, > but this needs some additional assumptions (some bounds for the big-M > constraints). So I think it is difficult to add direct and general support > for indicator constraints to GLPK. > > > Erwin Kalvelagen > Amsterdam Optimization Modeling Group > er...@amsterdamoptimization.com > https://www.amsterdamoptimization.com <https://amsterdamoptimization.com> > > > > On Mon, Oct 5, 2020 at 6:02 AM Domingo Alvarez Duarte > wrote: > >> Hello ! >> >> While testing GLPK with miplib2017 I noticed that several problems can >> not be handled by GLPK due to having "Indicator Constraints" in the mps >> file. >> >> Looking here >> >> https://www.gams.com/latest/docs/UG_LanguageFeatures.html#UG_LanguageFeatures_IndicatorConstraints >> for a explanation of it I'm asking if someone else have extended GLPK to >> manage then ? Or if not how hard could be to do it ? >> >> Cheers ! >> >> >>
Re: Solver performance solving examples/life_goe.mod
The code uses the avl tree to make a priority queue, and only cares about the relative ordering of the nodes. As a matter of fact, in this specific use having duplicate keys is expected and actually quite common. The pre-existing GLPK implementation of AVL trees works fine in this case, as I never search for a specific key but only access the previous or next nodes of a given one. Best Regards, Chris Matrakidis On Sat, 26 Sep 2020 at 19:52, Domingo Alvarez Duarte wrote: > Hello Chris ! > > I've add my fix of avl_tree to your code and compiled it and it segfaults > due to try insert a duplicate node. > > = > > gdb --args ./glpsol -m tiling.mod > GNU gdb (Ubuntu 8.2-0ubuntu1~18.04) 8.2 > Copyright (C) 2018 Free Software Foundation, Inc. > License GPLv3+: GNU GPL version 3 or later > <http://gnu.org/licenses/gpl.html> <http://gnu.org/licenses/gpl.html> > This is free software: you are free to change and redistribute it. > There is NO WARRANTY, to the extent permitted by law. > Type "show copying" and "show warranty" for details. > This GDB was configured as "x86_64-linux-gnu". > Type "show configuration" for configuration details. > For bug reporting instructions, please see: > <http://www.gnu.org/software/gdb/bugs/> > <http://www.gnu.org/software/gdb/bugs/>. > Find the GDB manual and other documentation resources online at: > <http://www.gnu.org/software/gdb/documentation/> > <http://www.gnu.org/software/gdb/documentation/>. > > For help, type "help". > Type "apropos word" to search for commands related to "word"... > Reading symbols from ./glpsol...done. > (gdb) r > Starting program: GLPK-cmatraki/examples/glpsol -m tiling.mod > GLPSOL: GLPK LP/MIP Solver, v4.65 > Parameter(s) specified in the command line: > -m tiling.mod > Reading model section from tiling.mod... > Reading data section from tiling.mod... > 118 lines were read > Generating covers... > Generating objeval... > Generating obj... > Model has been successfully generated > GLPK Integer Optimizer, v4.65 > 198 rows, 1349 columns, 8458 non-zeros > 1348 integer variables, all of which are binary > Preprocessing... > 196 rows, 1348 columns, 8260 non-zeros > 1348 integer variables, all of which are binary > Scaling... > A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 > Problem data seem to be well scaled > Constructing initial basis... > Size of triangular part is 196 > Solving LP relaxation... > GLPK Simplex Optimizer, v4.65 > 196 rows, 1348 columns, 8260 non-zeros > * 0: obj = 0.0e+00 inf = 0.000e+00 (1152) > * 458: obj = 1.96000e+02 inf = 1.162e-14 (0) 2 > OPTIMAL LP SOLUTION FOUND > Integer optimization begins... > Long-step dual simplex will be used > Objective step = 1 > + 458: mip = not found yet <= +inf(1; 0) > > Program received signal SIGSEGV, Segmentation fault. > 0x555ae48d in _glp_avl_set_node_link (node=0x0, > link=0x55dc11c8) at misc/avl.c:170 > 170 node->link = link; > (gdb) bt > #0 0x555ae48d in _glp_avl_set_node_link (node=0x0, > link=0x55dc11c8) at misc/avl.c:170 > #1 0x555898cf in _glp_ios_insert_node (tree=0x55dcca20, > node=0x55dc11c8) at draft/glpios01.c:837 > #2 0x5558d1d5 in branch_on (T=0x55dcca20, j=95, next=2) at > draft/glpios03.c:529 > #3 0x5558f859 in _glp_ios_driver (T=0x55dcca20) at > draft/glpios03.c:1490 > #4 0x5558018d in solve_mip (P=0x55876e10, > parm=0x7fffd808, P0=0x55876760, npp=0x5587c0e0) > at draft/glpapi09.c:250 > #5 0x5558098e in preprocess_and_solve_mip (P=0x55876760, > parm=0x7fffd808) at draft/glpapi09.c:415 > #6 0x000055581855 in glp_intopt (P=0x55876760, > parm=0x7fffd808) at draft/glpapi09.c:635 > #7 0xa97a in main (argc=3, argv=0x7fffdb88) at > glpsol.c:1427 > (gdb) q > A debugging session is active. > > Inferior 1 [process 804] will be killed. > > Quit anyway? (y or n) y > > = > > Cheers ! > On 26/9/20 17:30, Chris Matrakidis wrote: > > A brief description of the changes is in > https://lists.gnu.org/archive/html/help-glpk/2018-02/msg00018.html - > those considerably increased the number of miplib problems that can be > solved, in particular using pseudocost branching. Do ask if you have any > specific questions, but it was some time ago so it will take me a bit to > dig up the details. > > Note that for problems like the one you are using with lots of binary > variables, a pre-processing technique called probing is very eff
Re: Solver performance solving examples/life_goe.mod
A brief description of the changes is in https://lists.gnu.org/archive/html/help-glpk/2018-02/msg00018.html - those considerably increased the number of miplib problems that can be solved, in particular using pseudocost branching. Do ask if you have any specific questions, but it was some time ago so it will take me a bit to dig up the details. Note that for problems like the one you are using with lots of binary variables, a pre-processing technique called probing is very effective but not available in GLPK. I have a draft implementation but I'm not very happy with it, so it isn't committed to my tree. Best Regards, Chris Matrakids On Sat, 26 Sep 2020 at 17:55, Domingo Alvarez Duarte wrote: > Hello Chris ! > > Thank you for reply ! > > Can you describe in a few lines what your improvements achieved ? > > I've been looking at your changes and found that you've bitten by > "src/env/avl.c" avl_tree do not reject duplicate keys but do not provide a > way to recover duplicates, I fixed this here > https://github.com/mingodad/GLPK/commit/502da3ae23ffb4c1731cc437fd6b420ac82443d5 > and I found it while trying to update your code to work with splay_tree. > > See this thread > https://lists.gnu.org/archive/html/bug-glpk/2020-08/msg00018.html . > > Comparing your glpsol with mine solving hashi.mod we get this: > > = > > # your repository compiled with -O3 -DNDEBUG -march=native > -ffp-contract=off > > ... > > INTEGER OPTIMAL SOLUTION FOUND > Time used: 91.6 secs > Memory used: 19.6 Mb (20560460 bytes) > > ... > > Model has been successfully processed > 91.72user 0.64system 1:32.37elapsed 100%CPU (0avgtext+0avgdata > 23032maxresident)k > 0inputs+0outputs (0major+764597minor)pagefaults 0swaps > = > > # your repository compiled with -O2 -MT -MD -MP -MF > > ... > > INTEGER OPTIMAL SOLUTION FOUND > Time used: 120.9 secs > Memory used: 19.6 Mb (20560460 bytes) > > ... > Model has been successfully processed > 120.93user 1.23system 2:02.16elapsed 99%CPU (0avgtext+0avgdata > 22900maxresident)k > 0inputs+0outputs (0major+764575minor)pagefaults 0swaps > > = > > #my repository compiled with -g -O3 -DNDEBUG -march=native > -ffp-contract=off -DWITH_SPLAYTREE > > INTEGER OPTIMAL SOLUTION FOUND > Time used: 59.2 secs > Memory used: 10.6 Mb (11130654 bytes) > ... > > Model has been successfully processed > 58.99user 0.60system 0:59.59elapsed 99%CPU (0avgtext+0avgdata > 13664maxresident)k > 0inputs+0outputs (0major+397605minor)pagefaults 0swaps > > = > > # ubuntu 18.04 glpsol package > > INTEGER OPTIMAL SOLUTION FOUND > Time used: 70.5 secs > Memory used: 19.8 Mb (20725782 bytes) > ... > > Model has been successfully processed > 71.49user 0.22system 1:11.71elapsed 99%CPU (0avgtext+0avgdata > 23500maxresident)k > 0inputs+0outputs (0major+135565minor)pagefaults 0swaps > > = > > Cheers ! > On 26/9/20 16:20, Chris Matrakidis wrote: > > I made some performance improving patches a few years ago. You can find > them in: https://github.com/cmatraki/GLPK > > Best Regards, > > Chris Matrakidis > > On Sat, 26 Sep 2020 at 14:54, Domingo Alvarez Duarte > wrote: > >> Hello ! >> >> Testing GLPK I left it solving examples/lie_goe.mod for more than 2 >> hours and it didn't found a solution (wasm and native) then I stopped >> then and tried with cplex/gurobi/xpress/scip all of then gives a >> solution instantly (except scip that takes 3s). >> >> The difference is so big, have someone managed through command line >> options or other means managed to get a solution quickly with glpsol ? >> >> Any idea of how to improve GLPK to not be so behind ? >> >> Cheers ! >> >> >>
Re: Solver performance solving examples/life_goe.mod
I made some performance improving patches a few years ago. You can find them in: https://github.com/cmatraki/GLPK Best Regards, Chris Matrakidis On Sat, 26 Sep 2020 at 14:54, Domingo Alvarez Duarte wrote: > Hello ! > > Testing GLPK I left it solving examples/lie_goe.mod for more than 2 > hours and it didn't found a solution (wasm and native) then I stopped > then and tried with cplex/gurobi/xpress/scip all of then gives a > solution instantly (except scip that takes 3s). > > The difference is so big, have someone managed through command line > options or other means managed to get a solution quickly with glpsol ? > > Any idea of how to improve GLPK to not be so behind ? > > Cheers ! > > >
Re: GLPSOL in webassemby faster than native ?
It is well known that varying initial conditions can dramatically change the running time of a solver (and the tree searched). In this case there are floating point differences and in the first instance the integer solution is found very early and has the same value with the lp solution terminating the search instantly, while in the other it takes a few iterations more (and again terminates the search instantly). You can't draw any conclusion about solver performance from just one instance, where you may be lucky (or not). Best Regards, Chris Matrakidis On Tue, 22 Sep 2020 at 20:03, Domingo Alvarez Duarte wrote: > Hello Andrew ! > > In this case mean compiling with "-O3 -DNDEBUG -DWITH_SPLAYTREE" on > Arm7, "-O3 -DNDEBUG -flto -march=native -ffp-contract=off > -DWITH_SPLAYTREE" on x86_64 and "-O3 -DNDEBUG -flto -DWITH_SPLAYTREE" on > wasm. > > How are the parameters for the cut generations selected ? > > Isn't strange that on wasm it's been faster than native ? > > Doesn't this difference gives insight to select the parameter differently ? > > Cheers ! > > On 22/9/20 17:56, Andrew Makhorin wrote: > > On Tue, 2020-09-22 at 15:53 +0200, Domingo Alvarez Duarte wrote: > >> Hello again ! > >> > >> On an Android phone arm7 32bits Nexux-5 with chrome browser (wasm) > >> solving the "hashi.mod" with "--cuts" takes 98s and without it 909s, > >> using glpsol native compiled within termux takes 497s with "--cuts" > >> and > >> without it 925s. > > > > What does "native" mean? Just changing, for example, optimization level > > of the compiler may essentially change the set of generated cuts and > > thus the solution time. > > > > > >> Arm7 32bits Nexus-5: > >> > >> wasm "--cuts -m hashi.mod" -> 98s > >> > >> wasm " -m hashi.mod" -> 909s > >> > >> native "--cuts -m hashi.mod" -> 497s > >> > >> native " -m hashi.mod" -> 925s > >> > >> > >> Laptop Linux 64bits I7: > >> > >> wasm "--cuts -m hashi.mod" -> 8s > >> > >> wasm " -m hashi.mod" -> 142s > >> > >> native "--cuts -m hashi.mod" -> 73s > >> > >> native " -m hashi.mod" -> 55s > >> > >> > >> On arm7 "--cuts" improves the performance in both wasm and native. > >> > >> On x86_64 "--cuts" improves in wasm but degrade in native. > >> > >> I hope this could give hints to improve GLPK solver performance by > >> inspecting the decision's criteria and eventually find a better ones. > >> > >> Anyone can give any idea with this data ? > >> > >> Cheers ! > >> > >> On 21/9/20 17:11, Andrew Makhorin wrote: > >>> On Mon, 2020-09-21 at 16:09 +0200, Domingo Alvarez Duarte wrote: > >>>> Hello Andrew ! > >>>> > >>>> Are you saying that floating point calculations are more > >>>> efficient/precise in webassembly ? > >>> No. I meant that due to floating-point computations running the same > >>> computer program with the same data as a rule produces different > >>> results > >>> on different platforms. > >>> > >>>> Cheers ! > >>>> > >>>> On 21/9/20 15:08, Andrew Makhorin wrote: > >>>>>> Does someone can give a possible explanation ? > >>>>> floating-point computations > >> > >
Re: [Help-glpk] is this list (help-glpk) still active?
On Tue, 3 Mar 2020 at 16:57, Heinrich Schuchardt wrote: > > https://ftp.gnu.org/gnu/glpk/glpk-4.65.tar.gz > is the most current source tarball. There is no Git code repository. > I maintain a git repository in https://github.com/cmatraki/GLPK/tree/master but it only includes the official releases. There you can also find the "work" branch with some of my suggested patches. Best Regards, Chris Matrakidis
Re: [Help-glpk] [Fwd: Project development]
> Thanks for the GitHub repo, that's useful. For what I understand, if I > open a PR to your GitHub repo, it won't end up in the "official" project, > right? If that's the case, how are contributions to the project made? > Yes, this is not an official repository, it is just for convenience since I update it with every new release. For contributions I send patch files to the list, so that Andrew can pick them up. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: Project development]
Dear Marc, Your mail had to be forwarded because you are not subscribed to the list. I maintain a tree updated with all recent GLPK releases in https://github.com/cmatraki/GLPK/tree/master (going back to 4.57). There is also a "work" branch with some extensions I'm developing if you want to take a look. Best Regards, Chris Matrakidis On Tue, 2 Apr 2019 at 15:18, Andrew Makhorin wrote: > Forwarded Message > From: Marc Garcia > To: help-glpk@gnu.org > Subject: Project development > Date: Tue, 2 Apr 2019 12:02:16 +0100 > > Hi there, > > I'd like to get involved with glpk development, and I found the > information on the website: https://www.gnu.org/software/glpk/ but I'm > used to tools like GitHub, and I don't see how to get started. > > Are contributions to the code encouraged? If that's the case, is there > a github repo (or similar) somewhere, or am I expected to download the > latest tar.gz, and send a diff with my changes to the email addresses > mentioned in the website? > > I'm happy to help with setting up a repo if there is not one, and there > is interest, just let me know. > > Cheers! > > ___ > 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] TRYING TO GET A NON-OPTMIAL SOLUTION OF A MIP MODEL.
> > The problem is that in this part, it takes about 5h working on analyzing > the whole tree, but the strange thing is that it keeps showing the same > value every iteration it does until it gets to the end of the tree. The > value it shows is the same value that can be seen when it finds the lp > solution, does it means that the LP solution was the optimal since the > beginning? Am i able to interrupt the execution and take a look at this > solution? > What this means is that there are many feasible non-integer solutions with the same value as the integer one. The solver actually finds the solution following the very first branch (the last 0 in the parenthesis indicates that there were no backtracking steps taken) and does this after considering 1213 nodes. which seems quite good given the size of the problem. The issue is that each node takes a lot of time to do so, leading to your next question: > Or is there a way to speed it up a little bit? > Cant really say without more information, but the obvious thing to check is the scaling of the problem. Another thing to consider is reformulating the problem. On occasion, even adding redundant constraints helps. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: Re: Is it possible to feed glpsol with a feasible initial solution to a MIP problem?]
Hi Alejandro, > Anyway, I can't get glpsol to use the feasible solutition fed with > --ini. I think you need to disable the presolver with options --nopresol --nointopt to use a given solution. The presolver generates a new problem, for which the given solution is no longer valid. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Compiling and linking problems
Dear Mike, > I am able to build glpk v4.65 with --disable-reentrant. Unfortunately, > Heinrich’s solution does not work for me. > Can you give more details on the problems with Heinrich's solution? It works for me, but am only doing static builds with a custom makefile, so maybe missing something. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Compiling and linking problems
Dear Mike, The config.h you provided looks correct. Until we find a more permanent solution, you have two options: a) run configure with --disable-reentrant, or b) follow Heinrich's solution This has been discussed in the past[1] and Andrew seems to favour option a. Best Regards, Chris Matrakidis [1] https://lists.gnu.org/archive/html/help-glpk/2017-06/msg00033.html On 17 March 2018 at 01:23, Heinrich Schuchardt wrote: > Hello Mike, > > https://stackoverflow.com/questions/6394512/standard-c-library-in-mingw > writes: > "MinGW is designed to build native Windows code, and as such it builds > against Windows' native libc." > > So probably you want to change this line in src/env/stdc.c: > > -#elif defined(__WOE__) > +#elif defined(__CYGWIN__) || defined(__MINGW32__) || defined(__WOE__) > > Please, reply if this works. Then Andrew could update it in the next > version of GLPK. > > There might be more lines needing such a change: > > examples/glpsol.c:956:#ifndef __WOE__ > src/env/time.c:88:#elif defined(__WOE__) > src/env/dlsup.c:107:#elif defined(__WOE__) > src/env/tls.c:85:#ifdef __WOE__ > src/env/stdc.c:52:#elif defined(__WOE__) > > Best regards > > Heinrich > > > On 03/15/2018 02:35 PM, mike.stegl...@berlin.de wrote: > > Dear GLPK-Team, > > > > > > > > I have got some problems with building glpk 4.65 on Windows 10 with > > msys/mingw. > > > > > > > > I tried to build it with: > > > > ./configure --enable-static --disable-shared > > > > make > > > > > > > > Configure finished without problems. All sources are compiled without > > errors. > > > > But it ends with the following issues: > > > > … > > > > /bin/sh ../libtool --tag=CC --mode=link gcc -g -O2 -o glpsol.exe > > glpsol.o ../src/libglpk.la -lm > > > > libtool: link: gcc -g -O2 -o glpsol.exe glpsol.o ../src/.libs/libglpk.a > > > > ../src/.libs/libglpk.a(libglpk_la-stdc.o): In function `glp_xgmtime': > > > > C:\Users\Mike\Documents\Projekte\CMPL-1-12\Cmpl\data\ > glpk-4.65\src/env/stdc.c:81: > > undefined reference to `gmtime_r' > > > > ../src/.libs/libglpk.a(libglpk_la-stdc.o): In function `glp_xstrtok': > > > > C:\Users\Mike\Documents\Projekte\CMPL-1-12\Cmpl\data\ > glpk-4.65\src/env/stdc.c:93: > > undefined reference to `strtok_r' > > > > collect2.exe: error: ld returned 1 exit status > > > > make[2]: *** [glpsol.exe] Error 1 > > > > make[2]: Leaving directory > > `/Documents/Projekte/CMPL-1-12/Cmpl/data/glpk-4.65/examples' > > > > make[1]: *** [all-recursive] Error 1 > > > > make[1]: Leaving directory > > `/Documents/Projekte/CMPL-1-12/Cmpl/data/glpk-4.65' > > > > make: *** [all] Error 2 > > > > > > > > > > > > I have seen that in stdc.c are alternative versions of some function > > depending on some defines. But I am not sure what is do do. I was > > wondering that the defines are set by the configure script. > > > > I use as mentioned before msys/mingw: > > > > $ gcc -v > > > > Using built-in specs. > > > > COLLECT_GCC=C:\MinGW\bin\gcc.exe > > > > COLLECT_LTO_WRAPPER=c:/mingw/bin/../libexec/gcc/mingw32/6. > 3.0/lto-wrapper.exe > > > > Target: mingw32 > > > > Configured with: ../src/gcc-6.3.0/configure --build=x86_64-pc-linux-gnu > > --host=mingw32 --target=mingw32 --with-gmp=/mingw --with-mpfr > > --with-mpc=/mingw --with-isl=/mingw --prefix=/mingw > > --disable-win32-registry --with-arch=i586 --with-tune=generic > > --enable-languages=c,c++,objc,obj-c++,fortran,ada > > --with-pkgversion='MinGW.org GCC-6.3.0-1' --enable-static > > --enable-shared --enable-threads --with-dwarf2 --disable-sjlj-exceptions > > --enable-version-specific-runtime-libs --with-libiconv-prefix=/mingw > > --with-libintl-prefix=/mingw --enable-libstdcxx-debug --enable-libgomp > > --disable-libvtv --enable-nls > > > > Thread model: win32 > > > > gcc version 6.3.0 (MinGW.org GCC-6.3.0-1) > > > > > > > > > > > > Any suggestions are welcome! > > > > > > > > Thanks, > > > > > > > > Mike > > > > > > > > > > > > ___ > > 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 > ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Compiling and linking problems
Dear Mike, Can you share a copy of the generated config.h? Best Regards, Chris Matrakidis On 15 March 2018 at 15:35, wrote: > Dear GLPK-Team, > > > > I have got some problems with building glpk 4.65 on Windows 10 with > msys/mingw. > > > > I tried to build it with: > > ./configure --enable-static --disable-shared > > make > > > > Configure finished without problems. All sources are compiled without > errors. > > But it ends with the following issues: > > … > > /bin/sh ../libtool --tag=CC --mode=link gcc -g -O2 -o glpsol.exe > glpsol.o ../src/libglpk.la -lm > > libtool: link: gcc -g -O2 -o glpsol.exe glpsol.o ../src/.libs/libglpk.a > > ../src/.libs/libglpk.a(libglpk_la-stdc.o): In function `glp_xgmtime': > > C:\Users\Mike\Documents\Projekte\CMPL-1-12\Cmpl\data\glpk-4.65\src/env/stdc.c:81: > undefined reference to `gmtime_r' > > ../src/.libs/libglpk.a(libglpk_la-stdc.o): In function `glp_xstrtok': > > C:\Users\Mike\Documents\Projekte\CMPL-1-12\Cmpl\data\glpk-4.65\src/env/stdc.c:93: > undefined reference to `strtok_r' > > collect2.exe: error: ld returned 1 exit status > > make[2]: *** [glpsol.exe] Error 1 > > make[2]: Leaving directory `/Documents/Projekte/CMPL-1- > 12/Cmpl/data/glpk-4.65/examples' > > make[1]: *** [all-recursive] Error 1 > > make[1]: Leaving directory `/Documents/Projekte/CMPL-1- > 12/Cmpl/data/glpk-4.65' > > make: *** [all] Error 2 > > > > > > I have seen that in stdc.c are alternative versions of some function > depending on some defines. But I am not sure what is do do. I was > wondering that the defines are set by the configure script. > > I use as mentioned before msys/mingw: > > $ gcc -v > > Using built-in specs. > > COLLECT_GCC=C:\MinGW\bin\gcc.exe > > COLLECT_LTO_WRAPPER=c:/mingw/bin/../libexec/gcc/mingw32/6. > 3.0/lto-wrapper.exe > > Target: mingw32 > > Configured with: ../src/gcc-6.3.0/configure --build=x86_64-pc-linux-gnu > --host=mingw32 --target=mingw32 --with-gmp=/mingw --with-mpfr > --with-mpc=/mingw --with-isl=/mingw --prefix=/mingw > --disable-win32-registry --with-arch=i586 --with-tune=generic > --enable-languages=c,c++,objc,obj-c++,fortran,ada > --with-pkgversion='MinGW.org GCC-6.3.0-1' --enable-static --enable-shared > --enable-threads --with-dwarf2 --disable-sjlj-exceptions > --enable-version-specific-runtime-libs --with-libiconv-prefix=/mingw > --with-libintl-prefix=/mingw --enable-libstdcxx-debug --enable-libgomp > --disable-libvtv --enable-nls > > Thread model: win32 > > gcc version 6.3.0 (MinGW.org GCC-6.3.0-1) > > > > > > Any suggestions are welcome! > > > > Thanks, > > > > Mike > > > > ___ > 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] glpk 4.65 release information
Hi Andrew, A few weeks ago you wrote: I'd like to note that sometimes '--cuts' is not a best choice. > I did an experiment regarding this. In particular, I tried 84 out of the 87 problems in the miplib 2010 benchmark set (the other 3 needed more than an hour to solve the root relaxation). I provided the optimal solution in every (feasible) case to make sure no unnecessary nodes were searched (and disabled the rounding heuristic to save some time). Then did three runs with a time limit of 1 hour per problem and pcost branching: with cuts, without cuts and with cuts added every fourth backtracking step. The problems solved for the three cases were 25, 21 and 23 respectively. The results are summarised in the following table (which I hope is readable). The numbers in parentheses are the average execution time or gap compared to the other case, so in the 3 cases where A is faster with an average of 56% means they executed in 56% of the time B took (i.e. lower is better). +---+---++++++-+-+ | A | B | both | only A | only B |A |B | gap A | gap B | | | | solved | solved | solved | faster | faster | smaller | smaller | +---+---++++++-+-+ | with | w/o | 19 |6 |2 |3 | 12 |24 |19 | | cuts | cuts |||| (56%) | (52%) | (61%) | (76%) | +---+---++++++-+-+ | w/o | every | 20 |1 |3 | 11 |5 |15 |27 | | cuts | 4 |||| (65%) | (71%) | (75%) | (59%) | +---+---++++++-+-+ | every | with | 22 |1 |3 | 13 |4 |23 |17 | | 4 | cuts |||| (72%) | (87%) | (85%) | (84%) | +---+---++++++-+-+ The situation was very different using the modifications I published earlier. The problems solved were now 38, 40 and 43 for the same three cases respectively. Now without cuts more problems are solved within the time limit than with cuts, which I wasn't expecting. However even more problems are solved by adding cuts every fourth backtracking step. Again the following table has more details. +---+---++++++-+-+ | A | B | both | only A | only B |A |B | gap A | gap B | | | | solved | solved | solved | faster | faster | smaller | smaller | +---+---++++++-+-+ | with | w/o | 32 |6 |8 |3 | 25 |16 |12 | | cuts | cuts |||| (40%) | (51%) | (42%) | (61%) | +---+---++++++-+-+ | w/o | every | 36 |4 |7 | 23 |9 |7 |19 | | cuts | 4 |||| (59%) | (61%) | (71%) | (46%) | +---+---++++++-+-+ | every | with | 37 |6 |1 | 27 |4 |17 |12 | | 4 | cuts |||| (63%) | (63%) | (68%) | (74%) | +---+---++++++-+-+ I think this change in behaviour with my modifications is due to restoring the root node less during the search, and consequently requiring fewer factorisations. I'm attaching csv files with the results of the runs if you want to see more details. Best Regards, Chris Matrakidis GLPK 4.65 --cuts --pcost,,, Name, Dual Bound, Primal Bound, Gap%, Nodes, Time, Status, Solution 30n20b8,151,302,100,2607,3601, stopped, ok acc-tight5,0,0,0,1,1, ok, ok aflow40b,1122,1168,4.1,13795,3600, stopped, ok air04,56137,56137,0,43945,2934, ok, ok app1-2,-230,-41,461,13206,3603, stopped, ok ash608gpia-3col,1.00E+20,1.00E+20,--,57,185, ok, -- bab5,-111665.934,-106411.84,4.9,357,3603, stopped, ok beasleyC3,560,754,34.6,7484,3600, stopped, ok biella1,3062607.68,3065005.78,0.1,1206,3606, stopped, ok bienst2,54.6,54.6,0,216243,1454, ok, ok binkar10_1,6742.20002,6742.20002,0,87877,891, ok, ok bnatt350,0,0,0,1,1, ok, ok core2536-691,688.779403,689,0,2364,3604, stopped, ok cov1075,18,20,11.1,18985,3601, stopped, ok csched010,369.901019,408,10.3,3849,3600, stopped, ok danoint,63.9111228,65.667,2.7,55887,3600, stopped, ok dfn-gwin-UUM,37900,38752,2.2,60429,3601, stopped, ok eil33-2,934.007916,934.007916,0,4769,131, ok, ok eilB101,1216.92017,1216.92017,0,71847,895, ok, ok enli
Re: [Help-glpk] Use the best found integer solution regardless of mip gap
Dear Pietro, Since nobody answered, I'll give it a try, although I'm not using C#. My understanding is that glpk-cli is a thin wrapper around glpk, and the behaviour should be the same: the best integer solution is always available when the solver terminates. So, there is no need for the more complicated schemes you are describing. Can you give more details on what you are observing when the solver reaches the time limit? Best Regards, Chris Matrakidis On 5 March 2018 at 19:05, Pietro Scionti wrote: > Hello, > I am solving a MIP problem giving it a certain time limit. I am using the > library from a C# project calling the CLI interface ( > http://glpk-cli.sourceforge.net/) and my version is 4.60. > > This problem sometimes (I think corresponding to whether certain "strange" > constraints are activated or not) arrives just short of the optimal > solution, then loops there until it stops due to the time limit. IE the > console prints lines like these > +116950: mip = 1.50047e+02 >= 1.50010e+02 < 0.1% (2557; 2349) > +169952: mip = 1.50047e+02 >= 1.50010e+02 < 0.1% (3679; 3420) > +223563: mip = 1.50047e+02 >= 1.50010e+02 < 0.1% (4529; 4662) > +276156: mip = 1.50047e+02 >= 1.50010e+02 < 0.1% (5488; 5755) > +328782: mip = 1.50047e+02 >= 1.50010e+02 < 0.1% (6167; 6875) > For some time before "TIME LIMIT EXCEEDED. SEARCH TERMINATED". > > Now, in these cases (or in general, every time it doesn't reach the wanted > mip gap), I would like to be able to use the best found integer solution. > Basically, I came up with two possible approaches: > 1) keeping a pointer to the best found solution inside my user-defined > callback and use it if the b&c algorithm exits > 2) somehow trick the solver into relaxing the mip gap condition when I see > the time limit is approaching > 3) stupid solution: memorize the best found mipgap, and restart the solver > with the same input giving it a less restrictive mip gap. Obviously this > solution would (at worst?) double the total time needed, so it's a last > ditch effort > > So, first question, is what I'm doing even possible? Especially the 2nd > idea, since I haven't found something related to it in the documentation!! > And if so, are there better ideas? > > Going on with the first approach, I defined this callback > public void callback(glp_tree tree) > { > // .. > int reason = GLPK.glp_ios_reason(tree); > if (reason == GLPK.GLP_IBINGO) > bingo = GLPK.glp_ios_get_prob(tree); > } > The glp_prob bingo object is a private member of the class. > Then, inside the main method, > > ret = GLPK.glp_intopt(mip, iocp); > // .. > if (ret == GLPK.GLP_ETMLIM) > if (bingo != null) > _parserOutputBINGO?.Invoke(bingo, mip, > result); > > And finally, the _parserOutputBINGO method at some point calls > > int index = GLPK.glp_find_col(prob, colName); > if (index == 0) >throw new Exception("Non-existing column " + > colName); > > GLPK.glp_mip_col_val(bingo, index); > > I know from the documentation that this problem is not necessarily the > same as my original problem, so the parser method tries to reconcile the > difference. > 9 times out of 10, this call fails with a "System.AccessViolationException > : Attempted to read or write protected memory. This is often an indication > that other memory is corrupt. ", while the other time the method works as > intented. I guess the bingo object has already been been disposed? > > So, my further question is, can i trust to use this object outside the > callback, or is it bound to be disposed at an unforeseeable time and thus > this code could fail when it feels like it? Is there something I'm doing > wrong? > > Thank you very much > > Pietro Scionti > > ___ > 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
[Help-glpk] Patches to improve solver performance for integer problems
Hi Andrew, I have been preparing some patches to improve the performance when solving integer problems. Instead of spamming the list, I have created a git repository on github where I maintain them: https://github.com/cmatraki/GLPK/tree/work The main patches can be split in the following 6 groups (giving the short commit id and description for each patch): 1) faster pseudocost calculation and product score: 9dc0a6e reuse glp_prob for faster pcost initialisation a5816c7 add bfd copy operation cdffc12 use bfd_copy in pcost to avoid identical factorizations e96cd73 add --pcostmul product score option I have already sent these patches to the list some time ago: https://lists.gnu.org/archive/html/help-glpk/2017-01/msg00022.html https://lists.gnu.org/archive/html/help-glpk/2017-01/msg00090.html 2) objective step f233ccf find objective step and exploit it in search This patch finds cases where the objective value has discrete steps and uses this information to avoid some calculations 3) node preprocessor speed cdcd235 improve node preprocessor execution speed This patch avoids some copying and memory allocations inside the node preprocessor, which surprisingly was evident in some profiles. 4) Keep factorisation valid as much as possible 789e4c6 decouple root restoration from freezing 2d6bcfa avoid root restoration when restoring a child subproblem 947b7b9 avoid root restoration when restoring the sibling subproblem 45576b8 small ios_delete_node() cleanup Currently, when backtracking the solver restores the root node and then recreates the node to be restored. This set avoids this as much as possible and introduces the concept of sibling nodes (having the same parent) that can be similarly restored without invalidating the factorisation. 5) Use more information for pseudocost update 49dff33 update pcosts using reduced cost of nonbasic variables This is based on a presentation from SAS called "More Ways to Use Dual Information in MILP". 6) Improve active list search speed in the common case be47768 keep active list sorted in local bound order 8f5f9df fix comment to reflect new active list order 129bdd8 Make active list a true priority queue using the existing avl tree routines... ae86fdf Make active node count correct (including current node) When the active list becomes very large, traversing it becomes very time consuming (probably processor cache invalidation). This set makes the active list into a priority queue that is always in local bound order, with the exception of the current node that is not on the list to avoid unnecessary moves while its bound is updated. This is a small API change. These patches collectively can solve 36 problems from miplib 2010 within a time limit of two hours per problem. Do let me know if you have any comments, suggestions or questions. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.65 release information
Hi Andrew, I'd like to note that sometimes '--cuts' is not a best choice. For > example, air04 and air05 (hard set partitioning problems) from miplib > 3.0 are solved quickly (about 10 mins on my machine) with '--pcost', > but with cutting planes the solution takes more 6 hours. Probably this > is because cutting planes increase fractionality of node subproblems. > I know, but on average they seem to help (at least for miplib). There is another reason for this slowdown: MIR cut generation still takes a lot of time for some problems (even after the changes from two years ago). Some testing suggests that reducing the maximal number of rows that can be aggregated is not affecting the quality of generated cuts, but I haven't tested this as much as I would like. Moreover, the second paper referenced in ios_process_cuts() [1] states "...we found that better overall results are typically obtained if separation is only invoked at each k-th backtracking (we choose k = 4 in our implementation)." Indeed, generating cuts after every fourth backtracking step seems to improve overall solver performance but again I haven't tested this as much as I would like. Best Regards, Chris Matrakidis [1] Andreello, A.Caprara, and M.Fischetti, "Embedding Cuts in a Branch&Cut Framework: a Computational Study with {0,1/2}-Cuts", http://www.dei.unipd.it/~fisch/papers/012_branch_and_cut.pdf ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.65 release information
Hi Andrew, In order to test the release, I tried the 2010 MIPLIB benchmark set, calling glpsol with "--pcost --cuts" and a two hour time limit. The final result is in the attached file, but the quick summary is that 20 problems from this set were solved, while there were three aborts. Of the three aborts, problem mspp16 just run out of memory, while problems msc98-ip and ns1688347 failed in the primal simplex. Specifically, msc98-ip failed with: Warning: numerical instability (dual simplex, phase II) Warning: dual simplex failed due to excessive numerical instability Assertion failed: teta_lim >= 0.0 Error detected in file simplex/spxprim.c at line 665 while ns1688347 failed with: Error: basis matrix is singular to working precision (cond = 3.07e+18) Assertion failed: teta_lim >= 0.0 Error detected in file simplex/spxprim.c at line 665 Best Regards, Chris Matrakidis On 16 February 2018 at 11:57, Andrew Makhorin wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA1 > > GLPK 4.65 Release Information > * > > Release date: February 16, 2018 > > GLPK (GNU Linear Programming Kit) is intended for solving large-scale > linear programming (LP), mixed integer linear programming (MIP), and > other related problems. It is a set of routines written in ANSI C89 and > organized as a callable library. > > In this release: > > The following new API routines for LP/MIP preprocessing were > added: > > glp_npp_alloc_wkspallocate the preprocessor workspace > glp_npp_load_prob load original problem instance > glp_npp_preprocess1 perform basic LP/MIP preprocessing > glp_npp_build_probbuild resultant problem instance > glp_npp_postprocess postprocess solution to resultant problem > glp_npp_obtain_solobtain solution to original problem > glp_npp_free_wksp free the preprocessor workspace > > See doc/npp.txt for detailed description of these API routines. > > A new, more robust implementation of locally valid simple cover > cuts was included in the MIP solver. > > The API routine glp_init_iocp was changed to enable long-step > option of the dual simplex by default. > > See GLPK web page at <http://www.gnu.org/software/glpk/glpk.html>. > > GLPK distribution can be ftp'ed from <ftp://ftp.gnu.org/gnu/glpk/> or > from some mirror ftp sites; see <http://www.gnu.org/order/ftp.html>. > > MD5 check-sum is the following: > > 470a984a8b1c0e027bdb6d5859063fe8 *glpk-4.65.tar.gz > > GLPK is also available as a Debian GNU/Linux package. See its web page > at <http://packages.debian.org/stable/math/glpk-utils>. > > Precompiled GLPK binaries (lib, dll, exe) for 32- and 64-bit MS Windows > can be downloaded from <http://winglpk.sourceforge.net/>. > -BEGIN PGP SIGNATURE- > Version: GnuPG v1.2.1 (MingW32) > > iD8DBQFahqok0XvyMFmB6BgRAsXcAJ9rDlNG1A291WDzllXUebV/7f52wQCeInUE > XcANQ1QzjXAVdIiRJFpC8Sw= > =IFEM > -END PGP SIGNATURE- > > > > ___ > Help-glpk mailing list > Help-glpk@gnu.org > https://lists.gnu.org/mailman/listinfo/help-glpk > glpk-4.65.res Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Andrew, > There is no need (and technically it'd be difficult) to load Q back into > the PP wksp. It would be sufficient to provide some specific > preprocessor routines that allows, for example, fixing a column or add a > row to the current instance residing in the workspace. > If I understand correctly, currently glp_npp_build_prob() frees almost all problem data from the workspace, keeping only the references needed for glp_npp_load_sol() and glp_npp_recover_sol(). This is a reasonable design since in most cases there is no need to keep the additional data in the workspace. However this means that after calling glp_npp_build_prob() no further preprocessing can be done using the same workspace, and that glp_npp_build_prob() can only be called once. The patch I sent earlier associates the references left in the workspace with the rows/columns of the problem when glp_npp_load_prob() is called a second time, so that the solution to the original problem can still be recovered. For an unmodified problem the workspace would be in the same state it was right before calling glp_npp_build_prob(). Of course there are limitations to what kind of modifications can be done to the preprocessed problem (e.g. no column/row deletions). However, glp_npp_load_sol() and glp_npp_recover_sol() have exactly the same restrictions, so I don't see it as a show stopper. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Andrew, > Sorry, I don't catch your idea. The resulting (preprocessed) problem > always resides in the PP workspace, so one can preprocess it in several > passes, if necessary. > This is true, however after step L4 in your suggested API: Q = glp_npp_build_prob(npp, ...); any subsequent modifications to Q are not reflected in the PP workspace. My suggestion is to allow calling glp_npp_load_prob() with this modified Q (with changed bounds or added rows) to update the workspace before further preprocessing passes. In a way this takes your suggestion to Heinrich, to "...first preprocess your instance with glpk pp and then preprocess the resulting instance with your own preprocessor" one step further, in that it allows to rerun the glpk preprocessor again using the same workspace. I have used this procedure myself in: a) a loop that fixes columns of the proproecessed problem using probing until no further changes are possible; and b) for additional preprocessing after adding symmetry breaking inequalities to the preprocessed problem. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Bug-glpk] [bug] glpk cycling
Hi Andrew, Please replace file glpk-4.63/src/simplex/spydual.c with a new one > (see attachment) and then build the package as usual. > I did some testing with this version of dual simplex: I tried several problems from miplib 2010, including some that had trouble with the previous version and it seems to be a big improvement. The only issue I run into was with primal simplex, similar to the case that was reported earlier [1]. Best Regards, Chris Matrakidis [1] https://lists.gnu.org/archive/html/help-glpk/2017-08/msg0.html ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] non-official updated version of glpk (4.63 pre-release)
Andrew, I run into this behaviour with the released version as well (with a different MIP): Warning: dual simplex failed due to excessive numerical instability > > and later on it seems to get stuck in a sequence like: > *279500: obj = 2.196544071e+08 inf = 1.239e-13 (2) > *28: obj = 2.196544071e+08 inf = 1.239e-13 (2) > *280500: obj = 2.196544071e+08 inf = 1.239e-13 (2) > ... > *9366000: obj = 2.196544071e+08 inf = 1.239e-13 (2) > *9366500: obj = 2.196544071e+08 inf = 1.239e-13 (2) > *9367000: obj = 2.196544071e+08 inf = 1.239e-13 (2) > and so on. > In this case I see the following: Warning: numerical instability (dual simplex, phase II) ... Warning: numerical instability (dual simplex, phase II) Warning: dual simplex failed due to excessive numerical instability *4718105: obj = -2.406747734e+06 inf = 1.988e-08 (1) *4999119: obj = -2.406747734e+06 inf = 1.988e-08 (1) ... *156100559: obj = -2.406747734e+06 inf = 1.988e-08 (1) *156388395: obj = -2.406747734e+06 inf = 1.988e-08 (1) and so on. I did some additional checking and it seems that spx_chuzc_sel finds an eligible variable with d[j] ~3 times the eps value but no progress is made, ending up cycling between two variables. Is this enough information to go on, or do you want me to check any other variables or provide additional details? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] non-official updated version of glpk (4.63 pre-release)
Andrew, A "smart" LP perturbation was also implemented in the dual simplex > solver. This feature is similar to the one implemented in the primal > simplex solver (see below). > I did some testing of this and it seems like the dual simplex is less stable than the previous version. An example to see this is problem sp98ir from miplib 2010. Trying to solve this with --pcost I see lots of warnings like: Warning: numerical instability (dual simplex, phase II) or: Warning: numerical instability (dual simplex, phase I) and finally: Warning: dual simplex failed due to excessive numerical instability and later on it seems to get stuck in a sequence like: *279500: obj = 2.196544071e+08 inf = 1.239e-13 (2) *28: obj = 2.196544071e+08 inf = 1.239e-13 (2) *280500: obj = 2.196544071e+08 inf = 1.239e-13 (2) ... *9366000: obj = 2.196544071e+08 inf = 1.239e-13 (2) *9366500: obj = 2.196544071e+08 inf = 1.239e-13 (2) *9367000: obj = 2.196544071e+08 inf = 1.239e-13 (2) and so on. With version 4.62 this problem is solved rather quickly with only a few occasional: Warning: numerical instability (dual simplex, phase II) messages. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: GLPK was used in the proof of the 300 year old Kepler conjecture]
> Really nice !!! GLPK page should include a section "Successful > applications". > Here is another one I found recently, although not so impressive: Weibin Dai, Jun Zhang and Xiaoqian Sun, "On solving Multi-Commodity Flow Problems: An experimental evaluation," Chinese Journal of Aeronautics, preprint: http://m3nets.de/publications/CJA2017b.pdf >From the conclusion: "Separately, for column generation, GLPK has the best properties, but CVXPY can outperform GLPK while solving MCFP with a large number of commodities. For Lagrangian relaxation, it is shown that using Dijkstra shortest-path method to solve the Lagrangian sub-problem is the best choice. In general, GUROBI performs a medium level in both algorithms and SCIPY is always the worst one." Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Building 4.62 on mingw64
Hi Andrew, > Please see the attachment for a replacement of glpk/src/env/time.c. > I replaced the Posix version of glp_time with a new one, where gmtime is > not used (don't remember the reason for it; probably I was not sure > about the epoch.). This works fine. > Thank you for the patch. But is it really necessary to provide > reentrancy for msys2? Well, with mingw I use hand written config.h and Makefile so for me it isn't important. But I have a mutithreaded ios_driver() I was planning to send you (but needs lots of cleanup to reach that stage) and I would like it to be buildable with msys2. If you have reservations about exposing __WOE__ I can prepare a patch to check for *_s and *_r thread safe functions instead. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Building 4.62 on mingw64
Andrew, > Another way: > > ./configure --disable-reentrant There is a second problem with mingw on 64 bit windows, so this still won't work: The tv_sec field in struct timeval is 32 bit while time_t is 64 bit. Looking at msdn this seems like a microsoft header issue. The attached patch tries to correct both issues, by adding a configure check that the tv_sec field size is the same as the time_t size and by defining __WOE__ for mingw to get the *_s thread safe functions instead of the *_r ones. It has been tested to work on 64 bit mingw with configure run under msys2 (thanks Rob) and on linux where it doesn't change anything. Best Regards, Chris Matrakidis mingw.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Building 4.62 on mingw64
Rob, What does your config.h look like? Chris On 28 June 2017 at 17:35, Schroeder, Rob wrote: > Chris, > Thanks for the response. > > I made the change to config.h, and the make completed, but with some warnings. > env/time.c: In function 'glp_time': > env/time.c:63:20: warning: passing argument 1 of '_glp_xgmtime' from > incompatible pointer type [-Wincompatible-pointer-types] >tm = xgmtime(&tv.tv_sec); > ^ > In file included from env/env.h:27:0, > from env/time.c:28: > env/stdc.h:52:17: note: expected 'const time_t * {aka const long long int *}' > but argument is of type 'long int *' > #define xgmtime _glp_xgmtime > ^ > env/stdc.h:53:12: note: in expansion of macro 'xgmtime' > struct tm *xgmtime(const time_t *); > ^~~ > > The make check failed with the following info: > > ./glpsol.exe --mps ./murtagh.mps --max > GLPSOL: GLPK LP/MIP Solver, v4.62 > Parameter(s) specified in the command line: > --mps ./murtagh.mps --max > Reading problem data from './murtagh.mps'... > Problem: OILREFI > Objective: PROFIT > 74 rows, 81 columns, 504 non-zeros > 600 records were read > One free row was removed > Assertion failed: j >= 0 > Error detected in file env/time.c at line 66 > > This application has requested the Runtime to terminate it in an unusual way. > Please contact the application's support team for more information. > make[1]: *** [Makefile:555: check] Error 3 > make[1]: Leaving directory '/c/sw/glpk-4.62/examples' > make: *** [Makefile:321: check-recursive] Error 1 > > I'd be happy to test a patch if we can get it to work. > > Rob > > -Original Message- > From: Chris Matrakidis [mailto:cmatr...@gmail.com] > Sent: Wednesday, June 28, 2017 12:16 PM > To: Schroeder, Rob > Cc: help-glpk@gnu.org > Subject: Re: [Help-glpk] Building 4.62 on mingw64 > > Rob, > > I build 4.62 on mingw64 all the time, but I don't use msys2. > > Your problem seems to be that the symbol __WOE__ is not defined, thus the > complains for the *_r thread safe functions, instead of using the *_s ones. > > Add the following line to your config.h and try again: > #define __WOE__ 1 > > If this works, are you willing to test a patch to automate this? > > Best Regards, > > Chris Matrakidis > > On 28 June 2017 at 15:59, Schroeder, Rob wrote: >> Just curios if anyone has had success building 4.62 on mingw64 (via MSYS2)? >> I’m running into issues with the *_r thread safe time functions in the >> stdc.c file. >> >> >> >> Thanks, >> >> Rob >> >> >> >> >> >> >> ___ >> 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] Building 4.62 on mingw64
Rob, I build 4.62 on mingw64 all the time, but I don't use msys2. Your problem seems to be that the symbol __WOE__ is not defined, thus the complains for the *_r thread safe functions, instead of using the *_s ones. Add the following line to your config.h and try again: #define __WOE__ 1 If this works, are you willing to test a patch to automate this? Best Regards, Chris Matrakidis On 28 June 2017 at 15:59, Schroeder, Rob wrote: > Just curios if anyone has had success building 4.62 on mingw64 (via MSYS2)? > I’m running into issues with the *_r thread safe time functions in the > stdc.c file. > > > > Thanks, > > Rob > > > > > > > ___ > 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] glp_intopt runs forever (related to Dusan Plavak's issue)
Hi Andrew, > Thank you. I could reproduce the error using glpk 4.62; it appears due > to numerical instability in the dual simplex routine. For my setup, the instability appears with pre-release 4.59.2, if this is any help. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glp_intopt runs forever (related to Dusan Plavak's issue)
Hi Dusan, > we found out that the looping forever on this example manifests on the > version 4.59 onward i.e. with 4.58 it still ran successfully. This seems more reasonable, but am still curious. Can you share the test code? I have here several intermediate versions between 4.58 and 4.59 and I would like to isolate the change responsible for this. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glp_intopt runs forever (related to Dusan Plavak's issue)
Dear Rafael, > even after scaling your model the ratio between minimum and maximum > coefficient in the matrix is very big. See below. I agree that Heinrich's explanation is the most likely one. However I am curious why this change of behaviour happened with version 4.61. There are no changes in this version that should affect the simplex method execution. Did you change anything else in your environment (like C compiler or compilation flags)? Or are you comparing against an older version of GLPK (and if so which one)? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glp_intopt runs forever
Hi Dusan. > and glp_intopt() call runs "forever". I was able to quickly solve it, so it looks like either some precision problem that is solved by the (small) loss of accuracy when saving or something wrong with your setup. Have you tried the standalone solver with the saved file? > Also the interesting part is that on the older version of glpk it was solved > without any problems. I tried both version 4.61 and the 4.62 pre-release without problems. Which one was the older version that run without problems? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] non-official updated version of glpk (4.62 pre-release)
Hi Andrew, > i) if the primal simplex detects primal infeasibility, it should return > rather than continue the search starting from phase I; This should work OK as it is now. > and ii) in the dual simplex perturbation should be disabled. I don't understand the reason for this. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] non-official updated version of glpk (4.62 pre-release)
Hi Andrew, > NEW: The bound perturbation technique was implemented in the primal > simplex solver (now this feature is enabled by default). I did some testing and it seems to work fine: I run most of the instances in the "Benchmark of Simplex LP solvers" by H. Mittelmann ( http://plato.asu.edu/ftp/lpsimp.html ) and for many fewer iterations are needed now, while two more can be solved (neos2 and neos3). One thing I noticed is that in some cases primal feasibility is lost when removing the perturbation. The attached patch is a hack to continue using the dual simplex solver when this happens. This further improves solution times for some instances and allows two more to be solved (self and stat96v1). I'm not suggesting to add this patch as is, just sending it for easy testing. Best Regards, Chris Matrakidis diff --git a/src/glpapi06.c b/src/glpapi06.c index 4a5267c..f23fb25 100644 --- a/src/glpapi06.c +++ b/src/glpapi06.c @@ -245,7 +245,10 @@ static int solve_lp(glp_prob *P, const glp_smcp *parm) if (ret != 0) goto done; } if (parm->meth == GLP_PRIMAL) - ret = spx_primal(P, parm); + { ret = spx_primal(P, parm); + if (ret == -1 && P->valid) +ret = spx_dual(P, parm); + } else if (parm->meth == GLP_DUALP) { ret = spx_dual(P, parm); if (ret == GLP_EFAIL && P->valid) diff --git a/src/simplex/spxprim.c b/src/simplex/spxprim.c index 3f09b6c..ad29b4f 100644 --- a/src/simplex/spxprim.c +++ b/src/simplex/spxprim.c @@ -1040,6 +1040,12 @@ loop: /* main loop starts here */ xprintf("Perturbation removed at iteration %d\n", csa->it_cnt); #endif +if (check_feas(csa, 2, tol_bnd, tol_bnd1)) +{ if (msg_lev >= GLP_MSG_ALL) + xprintf("Switching to dual\n"); + ret = -1; + goto fini; +} } #endif if (csa->beta_st != 1) ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] testing glpk 4.62 on a 64-bit platform
Hi Andrew. > Please explain. Many glpk routines assume that sizeof(int) = 4 and will > just not work if sizeof(int) = 8. I was thinking of scenarios where we fix this in the future. I expect most GLPK problems will lead to crashes and will be easy to find, while minisat will continue working so a reminder seemed appropriate. > I wouldn't like to include a C++ code in glpk. It seems to me that a > better way would be to add an API routine that allows to set up an > user-provided CNF-SAT solver (which is, for example, minisat by > default). My plan is to link with the library that provides a C interface. However, when I looked at it a few months ago, the semantics of the interface looked a bit different to those of the current code so this was not so easy to test quickly. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] testing glpk 4.62 on a 64-bit platform
Hi Andrew. >> This assumes that int never has more bits then size_t. This is not >> guaranteed. The x32 ABI uses 32bit addresses and supports 64bit integers >> (https://lwn.net/Articles/456731/). It depends on the compiler if int >> has 32 or 64bit. I think Heinrich is right to be worried about this. > This wouldn't resolve the issue, because the glpk code supports only > ILP32 and LP64 programming models, where int is assumed to be 32-bit; > this is checked in the routine glp_init_env (see glpk/src/env/env.c). However, it is easy to guard against this just in case. We can change the "if (sizeof(void *) != sizeof(size_t))" in minisat1.c to something like "if (sizeof(void *) != sizeof(size_t) || sizeof(int) > sizeof(size_t))" which should catch x32 variants with 64 bit ints. As I said back in March, there is a C interface available for the C++ MiniSat, so it may be possible to hook a more recent version to GLPK. I am planning to work on this at some point - if there is interest I can look into it earlier. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] testing glpk 4.62 on a 64-bit platform
Hi Andrew, > I'd very appreciate if someone could test the --minisat option on a > 64-bit platform. I can confirm that minisat works as expected in 64-bit linux and windows. Note that I did the windows testing using mingw64 so some testing with another compiler may still be worthwhile. Regarding the rest of the preliminary release, the check for the objective limit in dual simplex is still disabled with perturbation. I think there was code to handle it in one of the previous preliminary releases. Moreover, this seems like a good time to remind you of some other patches I've send: 1. http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg6.html 2. http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg1.html 3. and the second patch in http://lists.gnu.org/archive/html/help-glpk/2017-01/msg00013.html (the first patch in the last link is an attempt at the dual simplex objective limit check but I got the #if wrong). Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: Enabling MiniSat for 64 bit?]
Hi Andrew, > Could you please post me the entire files (not diff's)? Here they are. Best Regards, Chris Matrakidis /* minisat1.c (driver to MiniSat solver) */ /*** * This code is part of GLPK (GNU Linear Programming Kit). * * Copyright (C) 2011-2016 Andrew Makhorin, Department for Applied * Informatics, Moscow Aviation Institute, Moscow, Russia. All rights * reserved. E-mail: . * * GLPK is free software: you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * GLPK is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public * License for more details. * * You should have received a copy of the GNU General Public License * along with GLPK. If not, see <http://www.gnu.org/licenses/>. ***/ #include "env.h" #include "minisat.h" #include "prob.h" int glp_minisat1(glp_prob *P) { /* solve CNF-SAT problem with MiniSat solver */ solver *s; GLPAIJ *aij; int i, j, len, ret, *ind; double sum; #if 0 /* 04/IV-2016 */ /* check problem object */ if (P == NULL || P->magic != GLP_PROB_MAGIC) xerror("glp_minisat1: P = %p; invalid problem object\n", P); #endif if (P->tree != NULL) xerror("glp_minisat1: operation not allowed\n"); /* integer solution is currently undefined */ P->mip_stat = GLP_UNDEF; P->mip_obj = 0.0; /* check that problem object encodes CNF-SAT instance */ if (glp_check_cnfsat(P) != 0) { xprintf("glp_minisat1: problem object does not encode CNF-SAT " "instance\n"); ret = GLP_EDATA; goto done; } #if 1 /* 07/XI-2015 */ if (sizeof(void *) != sizeof(size_t)) { xprintf("glp_minisat1: sorry, MiniSat solver is not supported " "on this platform\n"); ret = GLP_EFAIL; goto done; } #endif /* solve CNF-SAT problem */ xprintf("Solving CNF-SAT problem...\n"); xprintf("Instance has %d variable%s, %d clause%s, and %d literal%" "s\n", P->n, P->n == 1 ? "" : "s", P->m, P->m == 1 ? "" : "s", P->nnz, P->nnz == 1 ? "" : "s"); /* if CNF-SAT has no clauses, it is satisfiable */ if (P->m == 0) { P->mip_stat = GLP_OPT; for (j = 1; j <= P->n; j++) P->col[j]->mipx = 0.0; goto fini; } /* if CNF-SAT has an empty clause, it is unsatisfiable */ for (i = 1; i <= P->m; i++) { if (P->row[i]->ptr == NULL) { P->mip_stat = GLP_NOFEAS; goto fini; } } /* prepare input data for the solver */ s = solver_new(); solver_setnvars(s, P->n); ind = xcalloc(1+P->n, sizeof(int)); for (i = 1; i <= P->m; i++) { len = 0; for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next) { ind[++len] = toLit(aij->col->j-1); if (aij->val < 0.0) ind[len] = lit_neg(ind[len]); } xassert(len > 0); if (!solver_addclause(s, &ind[1], &ind[1+len])) { /* found trivial conflict */ xfree(ind); solver_delete(s); P->mip_stat = GLP_NOFEAS; goto fini; } } xfree(ind); /* call the solver */ s->verbosity = 1; if (solver_solve(s, 0, 0)) { /* instance is reported as satisfiable */ P->mip_stat = GLP_OPT; /* copy solution to the problem object */ xassert(s->model.size == P->n); for (j = 1; j <= P->n; j++) { P->col[j]->mipx = s->model.ptr[j-1] == l_True ? 1.0 : 0.0; } /* compute row values */ for (i = 1; i <= P->m; i++) { sum = 0; for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next) sum += aij->val * aij->col->mipx; P->row[i]->mipx = sum; } /* check integer feasibility */ for (i = 1; i <= P->m; i++) { if (P->row[i]->mipx < P->row[i]->lb) { /* solution is wrong */ P->mip_stat = GLP_UNDEF; break; } } } else { /* instance is reported as unsatisfiable */
Re: [Help-glpk] [Fwd: Tricks with MathProg to approximate non-linear functions?]
Dear Dolan, You mail had to be forwarded manually because you are not subscribed to the list. > Are there any known tricks with GLPK for what I'm trying to do, or am I > best off just choosing a linear objective function? You don't give enough information for detailed answers, so some general comments: 1. For piecewise linear approximations, you can use SOS2 constraints, which you can model using the approach in http://winglpk.sourceforge.net/media/glpk-sos2_02.pdf . Note that if you have a linear program this will make it an integer one. 2. The FICO guide you reference shows several linearisations that you can use if you have binary variables. 3. For a single ratio, like in the F1 score, the method described in http://lpsolve.sourceforge.net/5.5/ratio.htm may be appropriate. 4. You can evaluate the nonlinear function after the optimisation and compare it to the approximate one to see how accurate it was. Hope this helps. Best Regards, Chris Matrakidis > > Best Regards, > Dolan Antenucci > > > > > > > > ___ > 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] [Fwd: question about GLPK]
Dear Xu, There is also the option of trying the compatibility layer provided in directory examples/oldapi which may help in your case. Best Regards, Chris Matrakidis On 14 April 2017 at 09:15, Heinrich Schuchardt wrote: > Dear Xu, > > your mail had to be forwarded manually because you are not subscribed to > the GLPK help list. See > https://lists.gnu.org/mailman/listinfo/help-glpk > > You are trying to use functions that have been replaced in the GLPK > library several years ago. > > The best thing to do would be to update the code of ILPSolver.cpp to use > the current API (see glpk-4.61/doc/glpk.pdf). > > Or you will have to determine which outdated version of GLPK > ILPSolver.cpp was written for (definitely before 4.53). > > Best regards > > Heinrich Schuchardt > > On 04/14/2017 07:44 AM, Andrew Makhorin wrote: >> Forwarded Message >> To: help-glpk >> Subject: question about GLPK >> Date: Thu, 13 Apr 2017 11:03:04 +0800 >> >> Hello, I am a student of Qingdao Technological University. I have some >> problems with using GLPK 4.60. >> I have installed GLPK, compiled in. cpp file, an error occurs: >> ILPSolver.cpp: (.Text+0x126a): undefined reference to >> `glp_lpx_get_obj_dir' >> ILPSolver.cpp: (.Text+0x127d): undefined reference to >> `glp_lpx_get_obj_dir' >> ILPSolver.cpp: (.Text+0x1291): undefined reference to >> `glp_lpx_get_class' >> ILPSolver.cpp: (.Text+0x129f): undefined reference to >> `glp_lpx_get_class' >> ILPSolver.cpp: (.Text+0x12e4): undefined reference to >> `glp_lpx_read_cpxlp' >> ILPSolver.cpp: (.Text+0x12f2): undefined reference to >> `glp_lpx_delete_prob' >> . >> >> >> >> >> >> ___ >> 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 ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: Enabling MiniSat for 64 bit?]
Andrew, Here are three patches for MiniSat related issues. The first one is a small modification (better comment) of my original patch [1] to restore MiniSat on 64 bit systems. The second is a resend of [2] that handle the case where MiniSat detects trivial conflicts. The third patch allows running intfeas1() on problems without integer objective coefficients, if no bound is specified. All patches are relative to version 4.61. Somewhat related: There are C bindings for the C++ MiniSat [3], so it may be possible to hook a more recent version to GLPK. Best Regards, Chris Matrakidis PS. Erik, your mail had to be forwarded manually because you are not subscribed to the list. [1] http://lists.gnu.org/archive/html/bug-glpk/2015-11/msg4.html [2] http://lists.gnu.org/archive/html/bug-glpk/2015-11/msg9.html [3] https://github.com/niklasso/minisat-c-bindings From 2d9b6c7c4d800dc8f4c8e4c4ba6fabf2857fa110 Mon Sep 17 00:00:00 2001 From: Chris Matrakidis Date: Sun, 8 Jan 2017 22:13:26 +0200 Subject: [PATCH 1/3] less restrictive minisat 64-bit portability check diff --git a/src/api/minisat1.c b/src/api/minisat1.c index cb4148d..2244493 100644 --- a/src/api/minisat1.c +++ b/src/api/minisat1.c @@ -50,9 +50,9 @@ int glp_minisat1(glp_prob *P) goto done; } #if 1 /* 07/XI-2015 */ - if (sizeof(void *) != sizeof(int)) + if (sizeof(void *) != sizeof(size_t)) { xprintf("glp_minisat1: sorry, MiniSat solver is not supported " -"on 64-bit platforms\n"); +"on this platform\n"); ret = GLP_EFAIL; goto done; } diff --git a/src/minisat/minisat.c b/src/minisat/minisat.c index f242d83..47cf920 100644 --- a/src/minisat/minisat.c +++ b/src/minisat/minisat.c @@ -143,13 +143,13 @@ struct clause_t /* Encode literals in clause pointers: */ #define clause_from_lit(l) \ - (clause*)((unsigned long)(l) + (unsigned long)(l) + 1) + (clause*)((size_t)(l) + (size_t)(l) + 1) #define clause_is_lit(c) \ - ((unsigned long)(c) & 1) + ((size_t)(c) & 1) #define clause_read_lit(c) \ - (lit)((unsigned long)(c) >> 1) + (lit)((size_t)(c) >> 1) /**/ /* Simple helpers: */ @@ -332,8 +332,11 @@ static clause* clause_new(solver* s, lit* begin, lit* end, int learnt) c = (clause*)malloc(sizeof(clause) + sizeof(lit) * size + learnt * sizeof(float)); c->size_learnt = (size << 1) | learnt; -#if 0 /* by mao; meaningless non-portable check */ -assert(((unsigned int)c & 1) == 0); +#if 1 /* by mao & cmatraki; non-portable check that is a fundamental + * assumption of minisat code: bit 0 is used as a flag (zero + * for pointer, one for shifted int) so allocated memory should + * be at least 16-bit aligned */ +assert(((size_t)c & 1) == 0); #endif for (i = 0; i < size; i++) -- 2.7.4 From c8155b7c33eaaa1894df7d9be26e493428121a6b Mon Sep 17 00:00:00 2001 From: Chris Matrakidis Date: Sun, 8 Jan 2017 21:41:58 +0200 Subject: [PATCH 2/3] remove assert where minisat detects trivial conflicts diff --git a/src/api/minisat1.c b/src/api/minisat1.c index 2244493..1b7ea91 100644 --- a/src/api/minisat1.c +++ b/src/api/minisat1.c @@ -88,7 +88,13 @@ int glp_minisat1(glp_prob *P) ind[len] = lit_neg(ind[len]); } xassert(len > 0); - xassert(solver_addclause(s, &ind[1], &ind[1+len])); + if (!solver_addclause(s, &ind[1], &ind[1+len])) + { /* found trivial conflict */ +xfree(ind); +solver_delete(s); +P->mip_stat = GLP_NOFEAS; +goto fini; + } } xfree(ind); /* call the solver */ -- 2.7.4 From b232c5f7ae1ccd16b2b9aa2ddc1ca8c0c8ef2b62 Mon Sep 17 00:00:00 2001 From: Chris Matrakidis Date: Sun, 8 Jan 2017 23:31:03 +0200 Subject: [PATCH 3/3] intfeas1 needs to check objective only when bound specified diff --git a/src/api/intfeas1.c b/src/api/intfeas1.c index c2e5989..f440984 100644 --- a/src/api/intfeas1.c +++ b/src/api/intfeas1.c @@ -123,22 +123,24 @@ int glp_intfeas1(glp_prob *P, int use_bound, int obj_bound) goto done; } } - /* check the objective function */ - temp = (int)P->c0; - if ((double)temp != P->c0) - { xprintf("glp_intfeas1: objective constant term %g is non-integ" -"er or out of range\n", P->c0); - ret = GLP_EDATA; - goto done; - } - for (j = 1; j <= P->n; j++) - { temp = (int)P->col[j]->coef; - if ((double)temp != P->col[j]->coef) - { xprintf("glp_intfeas1: column %d: objective coefficient is " - "non-integer or out of range\n", j, P->col[j]->coef); + /* check the
Re: [Help-glpk] non-official updated version of glpk (4.62 pre-release)
Hi Andrew, The attached patch adds the _s variants for windows. I have only tested it using mingw64, so some some additional testing would be appropriate. Best Regards, Chris Matrakidis On 30 January 2017 at 13:07, Andrew Makhorin wrote: > Please see an updated version of glpk here: > http://sourceforge.net/projects/noumenon/files/tmp/ > (Note that this is *not* an official release.) > > The following main changes were made: > > 1. glp_config was added to the export section (for MS Windows). > > 2. Calls to non-thread-safe functions gmtime, strerror, and strtok were >replaced by calls to corresponding thread-safe equivalents (gmtime_r, >strerror_r, and strtok_r for GNU/Linux). > > If the application calls glpk routines from multiple threads, the > following should be taken into account: > > 1) a thread should not access glpk program objects (e.g. glp_proc) >created by other threads; > > 2) to prevent memory leaks each thread before termination should call >the glpk api routine glp_free_env. > > > Andrew Makhorin > > > ___ > Help-glpk mailing list > Help-glpk@gnu.org > https://lists.gnu.org/mailman/listinfo/help-glpk stdc.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] things I don't understand in src/env/time.c + bugs + suggested patch
Hi Andrew, > As Heinrich noticed, gmtime, strerror, and strtok are non-thread-safe Checking the online MSDN documentation, I see that strtok is also safe on Windows for multiple threads, but It isn't clear what happens for strerror - it is implied that a pointer to a fixed string is returned but there is no explicit mention of threads. That being said, I think it is better to use the _s functions on windows, so that linking will fail in old version where there may be issues. > The problem I > encountered is that gcc (Debian 4.7.2-5) 4.7.2 installed on my Linux > machine doesn't have gmtime_s, strerror_s, and strtok_s. My understanding is that it is unlikely that a version will be provided by glibc. > It is unclear > what to do if no thread-safe version of these functions are available. I think that configure should check for the posix versions or the windows versions and fail if not found when TLS is set. I can prepare a patch for this, but I can only test it on Linux. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] things I don't understand in src/env/time.c + bugs + suggested patch
Hi Andrew, > Not sure, but gmtime_s looks like a MSVC function. Could you point me > out where gmtime_s is standardized? Thanks. gmtime_s is included in the (optional) annex K of C11. However, the parameters are reversed compared to the MSVC version and the standard one returns struct tm * while the MSVC one returns errno_t. Moreover, some searching shows that gmtime_s is documented starting with VS 2010 (and _gmtime_s in VS 2005 and VS 2008). However, since VS 2005 gmtime returns a different pointer per thread [1], so there is no reason to use gmtime_s here - gmtime_s offers additional error checking for null pointers, which is not an issue in this code. Best Regards, Chris Matrakidis [1] https://msdn.microsoft.com/en-us/library/0z9czt0w(v=vs.80).aspx ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch for pseudocost branching with product score
Hi Andrew, > At first I'd like to finish the dual simplex routines (including your > patch from May 2016), and then inspect and implement your improvements > related to the mip solver. This patch is orthogonal to any changes in the simplex solver, and shouldn't affect the default behaviour. So, if you are worried that it will be hard to evaluate the changes to the simplex solver between the releases, I think it is safe. > BTW, how did you implement bfd_copy? I missed that. I'm re-sending the relevant patch, which adds a copy operation in each factorisation driver and the bfd_copy function that uses them. The copy operations reuse existing allocations in the destination when possible. Best Regards, Chris Matrakidis pcost2.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Patch for pseudocost branching with product score
Hi Andrew, This patch adds the option to select the branching variable using pseudocosts with product score, as described in Tobias Achterberg's thesis [1]. This is selected with a new br_tech option (GLP_BR_PMH) and a new option in glpsol (--pcostmul), so the old default behaviour is preserved. The patch also updates the manual accordingly. The patch is on top of the three initial patches I sent for speeding-up pseudocost initialisation, but should apply even without them. Using "glpsol --pcostmul --cuts" I was able to solve the following 32 problems from the MIPLIB 2010 benchmark set: acc-tight5, air04, app1-2, ash608gpia-3col, biella1, bienst2, binkar10_1, core2536-691, dfn-gwin-UUM, eil33-2, eilB101, lectsched-4-obj, map18, map20, mcsched, mine-166-5, neos-1109824, neos13, neos18, neos-476283, neos-686190, ns1766074, opm2-z7-s2, qiu, ran16x16, rmatr100-p10, rmatr100-p5, rmine6, sp98ir, tanglegram1, tanglegram2 and triptim1. Best Regards, Chris Matrakidis [1] T. Achterberg, "Constraint Integer Programming," PhD thesis, TU Berlin, 2007. commit 85cb76830f41e50c2a970f94b2da7efcf9a03cda Author: Chris Matrakidis Date: Wed Mar 9 03:06:23 2016 +0200 add --pcostmul product score option diff --git a/doc/glpk02.tex b/doc/glpk02.tex index 08a0219..a653a0e 100644 --- a/doc/glpk02.tex +++ b/doc/glpk02.tex @@ -2956,7 +2956,11 @@ Branching technique option: \verb|GLP_BR_DTH| --- heuristic by Driebeck and Tomlin; -\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic. +\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic; + +\verb|GLP_BR_PMH| --- hybrid pseudo-cost heuristic with product +score\footnote{T. Achterberg, ``Constraint Integer Programming,'' +PhD thesis, TU Berlin, 2007.}. \bigskip\vspace*{-2pt} diff --git a/doc/glpk10.tex b/doc/glpk10.tex index 1943ef0..c3cc7ff 100644 --- a/doc/glpk10.tex +++ b/doc/glpk10.tex @@ -118,6 +118,7 @@ the problem, and write its solution to an output text file. (default) --pcost branch using hybrid pseudocost heuristic (may be useful for hard instances) + --pcostmulvariation of --pcost using product score --dfs backtrack using depth first search --bfs backtrack using breadth first search --bestp backtrack using the best projection heuristic @@ -153,6 +154,8 @@ For description of the modeling language see the document ``Modeling Language GNU MathProg: Language Reference'' included in the GLPK distribution. +\newpage + For description of the DIMACS min-cost flow problem format and DIMACS maximum flow problem format see the document ``GLPK: Graph and Network Routines'' included in the GLPK distribution. diff --git a/examples/glpsol.c b/examples/glpsol.c index f4d4b1d..5adee8d 100644 --- a/examples/glpsol.c +++ b/examples/glpsol.c @@ -357,6 +357,8 @@ static void print_help(const char *my_name) xprintf(" --pcost branch using hybrid pseudocost heur" "istic (may be\n"); xprintf(" useful for hard instances)\n"); + xprintf(" --pcostmulvariation of --pcost using product " + "score\n"); xprintf(" --dfs backtrack using depth first search " "\n"); xprintf(" --bfs backtrack using breadth first searc" @@ -805,6 +807,8 @@ static int parse_cmdline(struct csa *csa, int argc, char *argv[]) csa->iocp.br_tech = GLP_BR_DTH; else if (p("--mostf")) csa->iocp.br_tech = GLP_BR_MFV; + else if (p("--pcostmul")) +csa->iocp.br_tech = GLP_BR_PMH; else if (p("--pcost")) csa->iocp.br_tech = GLP_BR_PCH; else if (p("--dfs")) diff --git a/src/glpapi09.c b/src/glpapi09.c index 8e5496c..cf08764 100644 --- a/src/glpapi09.c +++ b/src/glpapi09.c @@ -465,7 +465,8 @@ int glp_intopt(glp_prob *P, const glp_iocp *parm) parm->br_tech == GLP_BR_LFV || parm->br_tech == GLP_BR_MFV || parm->br_tech == GLP_BR_DTH || -parm->br_tech == GLP_BR_PCH)) +parm->br_tech == GLP_BR_PCH || +parm->br_tech == GLP_BR_PMH)) xerror("glp_intopt: br_tech = %d; invalid parameter\n", parm->br_tech); if (!(parm->bt_tech == GLP_BT_DFS || diff --git a/src/glpios09.c b/src/glpios09.c index 727761c..d4e1ba6 100644 --- a/src/glpios09.c +++ b/src/glpios09.c @@ -69,7 +69,8 @@ int ios_choose_var(glp_tree *T, int *next) { /* branch using the heuristic by Dreebeck and Tomlin */ j = branch_drtom(T, next); } - else if (T->parm->br_tech == GLP_BR_PCH) + else if (T->parm->br_tech == GLP_BR_PCH || + T->parm->br_tech == GLP
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Andrew, > Probably there should be an option to > choose between FT+bfd_copy and SC. In any case bfd_copy would be useful > addition I think. Since we are talking about pseudocosts here, where currently only 30 simplex iterations are done, I see two options: 1. Always use FT update + bfd_copy 2. Choose between bfd_copy and bfd_reset depending on the update method selected by the user. My preference would be for the second choice, under the assumption that the user has selected an alternative update method for additional accuracy. The attached schur3.patch implements this approach. >> > This approach, however, limits >> > the number of simplex iteration (say, to 100-200), since if >> > refactorization is needed, to keep B0 = L0 * U0 we should stop. >> >> I suppose this means that a new simplex flag may be needed, to stop >> when re-factorisation is required. > > Perfectly correct. Currently, if BFD is unable to perform update, the > simplex routine computes the factorization from scratch and then > continues the search; however, in the case of estimation of objective > degradation the dual simplex should stop reporting the current > super-optimal (i.e. primal infeasible and dual feasible) basic solution. A suggestion for a way to implement this is in the attached schur4.patch. This adds a new simplex method GLP_DUALNF, where dual simplex fails instead of calling the factorization procedure. Both patches apply on top of the previous ones in the series. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Hi Andrew, Leaving aside the issue of the API for the time being, I did some additional experiments in this area. > To resolve this > issue some time ago I implemented another factorization of the basis > based on Schur complement (please see comments in src/bflib/scf.h), > where B0 = L0 * U0 is not changed, so B = B0 can be easily restored as > in case of "eta file". I did try this, and it seems to work OK. The attached two patches implement it on top of the three original patches I sent (pcost1.patch to pcost3.patch). The first one just makes the pseudocost initialisation use Schur complement updates, to use as a baseline since the pseudocosts calculated may be different now. The second ones introduces a bfd_reset() function that restores the original factorisation and uses this instead of bfd_copy(). Unfortunately, it looks like that the speed gain from using bfd_reset does not offset the overhead of Schur complement updates, so Forrest-Tomlin update with bfd_copy seems to be the preferred option here. > This approach, however, limits > the number of simplex iteration (say, to 100-200), since if > refactorization is needed, to keep B0 = L0 * U0 we should stop. I suppose this means that a new simplex flag may be needed, to stop when re-factorisation is required. Best Regards, Chris Matrakidis commit 9734f4815fda152a20491a617818badb631adbf6 Author: Chris Matrakidis Date: Sat Jan 14 16:24:45 2017 +0200 use schur complement update in pcost calculation diff --git a/src/glpios09.c b/src/glpios09.c index 727761c..255e681 100644 --- a/src/glpios09.c +++ b/src/glpios09.c @@ -447,12 +447,19 @@ static double eval_degrad(glp_tree *T, int j, double bnd) double degrad; /* prepare lp */ if (lp == NULL) - { /* the current basis must be optimal */ + { glp_bfcp bfcp; + /* the current basis must be optimal */ xassert(glp_get_status(P) == GLP_OPT); /* create a copy of mip */ lp = glp_create_prob(); glp_copy_prob(lp, P, 0); csa->work = lp; + glp_get_bfcp(lp, &bfcp); + if (bfcp.type & GLP_BF_FT) + { bfcp.type &= ~GLP_BF_FT; +bfcp.type |= GLP_BF_BG; + } + glp_set_bfcp(lp, &bfcp); /* factorize and store */ glp_factorize(lp); csa->bfd = bfd_create_it(); commit d9944e1c142a09e20ee0cf58fa660b3d09206475 Author: Chris Matrakidis Date: Sat Jan 14 19:36:43 2017 +0200 use bfd_reset in pcost initialisation diff --git a/src/bfd.c b/src/bfd.c index 89d547a..a085298 100644 --- a/src/bfd.c +++ b/src/bfd.c @@ -514,6 +514,16 @@ int bfd_update(BFD *bfd, int j, int len, const int ind[], const double return ret; } +void bfd_reset(BFD *bfd) +{ /* reset LP basis factorization to initial state */ + int ret; + xassert(bfd->valid); + xassert(bfd->type == 2); + scfint_reset(bfd->u.scfi); + bfd->upd_cnt = 0; + return; +} + int bfd_get_count(BFD *bfd) { /* determine factorization update count */ return bfd->upd_cnt; diff --git a/src/bfd.h b/src/bfd.h index 3f63099..d652c55 100644 --- a/src/bfd.h +++ b/src/bfd.h @@ -94,6 +94,10 @@ int bfd_update(BFD *bfd, int j, int len, const int ind[], const double val[]); /* update LP basis factorization */ +#define bfd_reset _glp_bfd_reset +void bfd_reset(BFD *bfd); +/* reset LP basis factorization to initial state */ + #define bfd_get_count _glp_bfd_get_count int bfd_get_count(BFD *bfd); /* determine factorization update count */ diff --git a/src/bflib/scfint.c b/src/bflib/scfint.c index 25aed12..6e572b0 100644 --- a/src/bflib/scfint.c +++ b/src/bflib/scfint.c @@ -135,6 +135,26 @@ int scfint_factorize(SCFINT *fi, int n, int (*col)(void *info, int j, return ret; } +void scfint_reset(SCFINT *fi) +{ /* reset SC-factorization to initial state */ + int k; + int n = fi->scf.n0; + xassert(n > 0); + /* initialize SC-factorization */ + fi->scf.n = n; + fi->scf.nn = 0; + fi->scf.rr_ref = sva_alloc_vecs(fi->scf.sva, fi->scf.ifu.n_max); + fi->scf.ss_ref = sva_alloc_vecs(fi->scf.sva, fi->scf.ifu.n_max); + fi->scf.ifu.n = 0; + for (k = 1; k <= n; k++) + { fi->scf.pp_ind[k] = k; + fi->scf.pp_inv[k] = k; + fi->scf.qq_ind[k] = k; + fi->scf.qq_inv[k] = k; + } + return; +} + int scfint_update(SCFINT *fi, int upd, int j, int len, const int ind[], const double val[]) { /* update SC-factorization after replacing j-th column of A */ diff --git a/src/bflib/scfint.h b/src/bflib/scfint.h index 67ca65d..45142a6 100644 --- a/src/bflib/scfint.h +++ b/src/bflib/scfint.h @@ -63,6 +63,10 @@ int scfint_factorize(SCFINT *fi, int n, int (*col)(void *info, int j, int ind[], double val[]), void *info); /* compute SC-factorization of specif
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Hi Andrew, >> I am a bit more optimistic: Using the draft API, I saw some cases of >> ~20% improvement in pseudocost initialisation time. > > Did you use bfd_copy or the basis factorization was computed from > scratch for every re-optimization as currently implemented? This was using bfd_copy in both cases, so the only change was using the internal API or not. Of course not every problem gained as much, but some (like triptim1 and app1-2 from miplib) did. The gain was calculated by counting the number of pseudocosts estimated at the root node, for the same fixed time interval in both cases. > Also please note that your changes might lead to some differences in the > pseudo-costs computed that, in turn, might affect the choice of > branching variables and thus change the overall solution time > signficantly. I tried to make the code produce the exact same results in every case, in order to keep the performance of the different approaches directly comparable, and in my tests this seems to be the case. The code would be a bit simpler if that was not the case but then the evaluation of the performance would be difficult, as you point out, and I'm not sure profiling would help there. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Hi Andrew, > I thought about that. Converting glp_prob to internal primal/dual > simplex structures takes a tiny percentage of the overall solution time, > so I decided not to complicate the interface. I am a bit more optimistic: Using the draft API, I saw some cases of ~20% improvement in pseudocost initialisation time. Of course this was for large problems and for just 30 dual simplex iterations, but I expect some gain. I'll try it when I have some time, to get actual numbers, and get back to you. >> Therefore I still think than a different internal API is needed, with >> this procedure (and others) implemented on top of it. I'll think about >> it some more and get back to you with a more detailed proposal for >> this API. I think that offering something like the eval_degrad() function of glpios09.c from the simplex routines is the best approach to implement the procedure you outlined. If you want, I can make a mock-up using the bfd_copy() operation which can be later simplified to work with the Schur complement basis factorisation. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Hi Andrew, > I think your design is too complicated. It seems to me that both > pseudo-cost initialization and strong branching could be implemented > as a special call to the dual simplex routine. I agree that this design is too complicated (except maybe the first part that I think is straightforward). And I really like the idea you outlined for restoring the original factorisation instead of copying it. However, there was an additional objective for the dual simplex API that I left out from my previous email: I was going for something that can also be used in the branch & bound procedure to avoid reinitialising the internal dual simplex structures between successive calls. This is something I think is needed, but, admittedly, the version I showed is not appropriate for this. > The procedure above can be implemented *within* the dual simplex > driver and thus can use internal data structures of the simplex > routines (no API is needed). I feel that this procedure is a bit too high level to include in the simplex routines, for two reasons: 1. It requires knowledge of the factorisation to use inside the simplex routines, breaking modularity. 2. I don't see how variations of strong branching like the ones presented in "Branching on nonchimerical fractionalities" by Fischetti and Monaci can be implemented on top of this procedure. Therefore I still think than a different internal API is needed, with this procedure (and others) implemented on top of it. I'll think about it some more and get back to you with a more detailed proposal for this API. > To resolve this > issue some time ago I implemented another factorization of the basis > based on Schur complement (please see comments in src/bflib/scf.h), > where B0 = L0 * U0 is not changed, so B = B0 can be easily restored as > in case of "eta file". Is this what you were referring to in http://lists.gnu.org/archive/html/help-glpk/2012-06/msg00023.html ? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Andrew, > Sorry, I don't catch your idea. On initializing pseudocosts there > appears the same implementation issue as for strong branching (which is > still not implemented in glpk). Namely, given a subset of structural > variables and their new lower and upper bounds we need to solve a set of > LPs introducing one new lower/upper bound for every variable and keeping > other bounds untouched. It is obviously natural to start solving every > LP from the optimal point of the master LP, which (the point) is primal > and dual feasible; introducing a new bound makes the solution primal > infeasible, but keeps its dual feasibility, so for reoptimization the > dual simplex can be used. However, to start the search we need to have > the basis factorization corresponding to the optimal basic solution of > the master LP. Currently the pseudocost routine just invalidates the > factorization to compute it from scratch every time it starts solving a > next LP and thus takes much time. This is the only issue; I see no other > points where the pseudocosts initialization procedure could be improved. I'm not sure which patch confuses you, so I'll describe all of them, since they try to address three different issues. 1. pcost1.patch just reuses the same glp_prob to avoid calling glp_create_prob() and glp_copy_prob() repeatedly, but the factorisation is still invalidated every time before calling dual simplex. 2. pcost2.patch and pcost3.patch calculate the factorisation once and keep a copy which is restored before every call to glp_simplex(). I tried a simpler version where the factorisation is just copied from the master LP every time, but this changed the calculated pseudocosts and the branching seemed to be less accurate, so I decided to leave it aside until I have time to do more exhaustive testing. 3. dual_API1.patch and dual_API2.patch define an internal API to keep the data structures inside spydual.c and update them for bound (and factorisation) changes before the next call. This avoids the overhead for making multiple copies of the same problem data for each simplex call but as I said, I'm not happy with the way I designed this API. So the second point above is the one you are describing, but I also found that the data copying takes a considerable portion of the time for pseudocost initialisation. I hope this makes the intention of the patches clearer, but do ask if you need more details. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Andrew, >> I have a draft patch that introduces an internal API for keeping the >> dual simplex state between calls and adjusting it for new bounds. It >> works fine and speeds up pseudocost initialisation for all >> configurations of the solver (i.e. combinations of USE_AT, EXCL and >> SHIFT). However, I'm not happy with the API design, so I don't >> consider it ready for submission. If you think it may be helpful, I >> will send it. > > Please post your patch to the list with minimal comments for archiving. Here it is, broken down in two pieces. The first patch defines the API and all necessary changes and uses it in pseudocost initialisation. This is on top of my previous pseudocost initialisation patches but not the other simplex patches (but should apply without conflicts). The second patch is a tentative initial effort to update the row wise representation of N. A more worked out version, should probably have reset_nt() in spxnt.c and choose between build_nt() and reset_nt() depending on the number of simplex iterations since the last call. Best Regards, Chris Matrakidis dual_API1.patch Description: Binary data dual_API2.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed
Hi Andrew, > I'm starting to make changes according to some of your patches. I think > it will take a time, in particular, because the dual simplex driver > routine should be revised, rewritten, and tested more carefully. I have a draft patch that introduces an internal API for keeping the dual simplex state between calls and adjusting it for new bounds. It works fine and speeds up pseudocost initialisation for all configurations of the solver (i.e. combinations of USE_AT, EXCL and SHIFT). However, I'm not happy with the API design, so I don't consider it ready for submission. If you think it may be helpful, I will send it. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Patches to improve pseudocost initialisatiion speed
Andrew, Since you are preparing a new GLPK release, I'm sending you three patches to consider, that improve the speed of pseudocost initialization. The first reuses the same glp_prob in each round to avoid unnecessary copying, the second introduces a bfd_copy function and the third uses bfd_copy to avoid recalculating the exact same factorisation in every simplex call during each initialisation round. These patches do not affect the execution order of the code, only the initialisation speed: in all tests I did, I get the exact same number of nodes and simplex iterations Best Regards, Chris Matrakidis diff --git a/src/glpios09.c b/src/glpios09.c index d87578c..b9e6b5a 100644 --- a/src/glpios09.c +++ b/src/glpios09.c @@ -403,6 +403,8 @@ struct csa double *up_sum; /* double up_sum[1+n]; */ /* up_sum[j] is the sum of per unit degradations of the objective over all up_cnt[j] subproblems */ + glp_prob *work; + /* working problem to avoid unnecessary initializations */ }; void *ios_pcost_init(glp_tree *tree) @@ -418,24 +420,44 @@ void *ios_pcost_init(glp_tree *tree) { csa->dn_cnt[j] = csa->up_cnt[j] = 0; csa->dn_sum[j] = csa->up_sum[j] = 0.0; } + csa->work = NULL; return csa; } -static double eval_degrad(glp_prob *P, int j, double bnd) +static double eval_degrad(glp_tree *T, int j, double bnd) { /* compute degradation of the objective on fixing x[j] at given value with a limited number of dual simplex iterations */ /* this routine fixes column x[j] at specified value bnd, solves resulting LP, and returns a lower bound to degradation of the objective, degrad >= 0 */ - glp_prob *lp; + struct csa *csa = T->pcost; + glp_prob *lp = csa->work, *P = T->mip; glp_smcp parm; - int ret; + int i, jjj, ret; double degrad; - /* the current basis must be optimal */ - xassert(glp_get_status(P) == GLP_OPT); - /* create a copy of P */ - lp = glp_create_prob(); - glp_copy_prob(lp, P, 0); + /* prepare lp */ + if (lp == NULL) + { /* the current basis must be optimal */ + xassert(glp_get_status(P) == GLP_OPT); + /* create a copy of mip */ + lp = glp_create_prob(); + glp_copy_prob(lp, P, 0); + csa->work = lp; + } + else + { /* restore original values */ + for (i = 1; i <= P->m; i++) + { lp->row[i]->stat = P->row[i]->stat; +lp->row[i]->prim = P->row[i]->prim; +lp->row[i]->dual = P->row[i]->dual; + } + for (jjj = 1; jjj <= P->n; jjj++) + { lp->col[jjj]->stat = P->col[jjj]->stat; +lp->col[jjj]->prim = P->col[jjj]->prim; +lp->col[jjj]->dual = P->col[jjj]->dual; + } + lp->valid = 0; + } /* fix column x[j] at specified value */ glp_set_col_bnds(lp, j, GLP_FX, bnd, bnd); /* try to solve resulting LP */ @@ -478,8 +500,9 @@ static double eval_degrad(glp_prob *P, int j, double bnd) { /* the simplex solver failed */ degrad = 0.0; } - /* delete the copy of P */ - glp_delete_prob(lp); + /* restore column x[j] type and bounds */ + glp_set_col_bnds(lp, j, P->col[j]->type, P->col[j]->lb, + P->col[j]->ub); return degrad; } @@ -550,7 +573,7 @@ static double eval_psi(glp_tree *T, int j, int brnch) if (csa->dn_cnt[j] == 0) { /* initialize down pseudocost */ beta = T->mip->col[j]->prim; -degrad = eval_degrad(T->mip, j, floor(beta)); +degrad = eval_degrad(T, j, floor(beta)); if (degrad == DBL_MAX) { psi = DBL_MAX; goto done; @@ -565,7 +588,7 @@ static double eval_psi(glp_tree *T, int j, int brnch) if (csa->up_cnt[j] == 0) { /* initialize up pseudocost */ beta = T->mip->col[j]->prim; -degrad = eval_degrad(T->mip, j, ceil(beta)); +degrad = eval_degrad(T, j, ceil(beta)); if (degrad == DBL_MAX) { psi = DBL_MAX; goto done; @@ -604,9 +627,11 @@ int ios_pcost_branch(glp_tree *T, int *_next) #endif int j, jjj, sel; double beta, psi, d1, d2, d, dmax; + struct csa *csa; /* initialize the working arrays */ if (T->pcost == NULL) T->pcost = ios_pcost_init(T); + csa = T->pcost; /* nothing has been chosen so far */ jjj = 0, dmax = -1.0; /* go through the list of branching candidates */ @@ -658,6 +683,11 @@ int ios_pcost_branch(glp_tree *T, int *_next) jjj = branch_mostf(T, &sel); } done: *_next = sel; + if (csa->work != NULL) + { /* clean up work
[Help-glpk] Patches for simplex routines
Andrew, I'm attaching two patches for the simplex routines. The first one is just your idea [1] for restoring the objective limit check in dual simplex when perturbation is enabled, which considerably improves branch and bound performance. This is just to make sure it is not forgotten. The second patch changes two asserts into errors (one in primal and one in dual). I managed to trigger the second one, but I'm changing the first one just in case. Best Regards, Chris Matrakidis PS. In addition to the patch [2] you mentioned a few days ago, in May I sent another patch as well [3] for an mps reading bug. [1] http://lists.gnu.org/archive/html/help-glpk/2016-04/msg6.html [2] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg6.html [3] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg1.html diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c index e41baf2..d33ebb1 100644 --- a/src/simplex/spydual.c +++ b/src/simplex/spydual.c @@ -1374,13 +1374,15 @@ loop: /* main loop starts here */ check_accuracy(csa); #endif /* check if the objective limit has been reached */ -#if PERTURB - /* FIXME */ - if (!perturb) -#endif if (csa->phase == 2 && csa->obj_lim != DBL_MAX && spx_eval_obj(lp, beta) >= csa->obj_lim) - { if (csa->beta_st != 1) + { if (perturb) + { /* remove perturbation */ +perturb = 0; +memcpy(csa->lp->c, csa->orig_c, (1+n) * sizeof(double)); +csa->phase = csa->d_st = 0; + } + if (csa->beta_st != 1) csa->beta_st = 0; if (csa->d_st != 1) csa->d_st = 0; diff --git a/src/simplex/spxprim.c b/src/simplex/spxprim.c index 4a5e7aa..1f4aac8 100644 --- a/src/simplex/spxprim.c +++ b/src/simplex/spxprim.c @@ -963,7 +963,13 @@ loop: /* main loop starts here */ else spx_nt_prod(lp, nt, trow, 1, -1.0, rho); /* FIXME: tcol[p] and trow[q] should be close to each other */ - xassert(trow[csa->q] != 0.0); + if (trow[csa->q] == 0.0) + { if (msg_lev >= GLP_MSG_ERR) +xprintf("Error: trow[q] == 0.0\n"); + csa->p_stat = csa->d_stat = GLP_UNDEF; + ret = GLP_EFAIL; + goto fini; + } /* update reduced costs of non-basic variables for adjacent * basis */ if (spx_update_d(lp, d, csa->p, csa->q, trow, tcol) <= 1e-9) diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c index d33ebb1..c8350d2 100644 --- a/src/simplex/spydual.c +++ b/src/simplex/spydual.c @@ -1632,7 +1632,13 @@ loop: /* main loop starts here */ t_pivcol += timer() - t_start; #endif /* FIXME: tcol[p] and trow[q] should be close to each other */ - xassert(csa->tcol.vec[csa->p] != 0.0); + if (csa->tcol.vec[csa->p] == 0.0) + { if (msg_lev >= GLP_MSG_ERR) +xprintf("Error: tcol[p] == 0.0\n"); + csa->p_stat = csa->d_stat = GLP_UNDEF; + ret = GLP_EFAIL; + goto fini; + } /* update values of basic variables for adjacent basis */ k = head[csa->p]; /* x[k] = xB[p] */ p_flag = (l[k] != u[k] && beta[csa->p] > u[k]); ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch to configure a reentrant version of GLPK
Heinrich, > Why should this option be disabled by default? I have only really tested the patch on Linux so I thought it safer to have it disabled by default for the time being. This way, whoever really needs it can try it and won't be worse off if it doesn't work. > For all applications that up to now were only able to use GLPK with one > thread the patch makes no difference. Well, I noticed a very minor slowdown when enabled but nothing to worry about (at least on my system). > If we have such a switch a program calling the library will need a means > of determining if the library is thread-safe or not. This may still be required to help with code portability to systems with old glpk libraries (although a version check may be enough). > So it would be preferable not to have any switch at all but simply make > the library thread safe in all cases. I agree it makes sense to have it enabled by default eventually, but I think the switch is still necessary to ease configuring a single threaded version. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch to configure a reentrant version of GLPK
Hi Andrew, > Chris, I also would like to thank you for the patch regarding to a bug > in dual simplex phase posted on May, 2016. Sorry for a very long delay > in my response (just returned from the salt mines :). Hope to fix that > bug and make a new release. I have a few more patches almost ready for submission. What sort of time frame do you have in mind for the next release? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Patch to configure a reentrant version of GLPK
Andrew, The attached patch adds the --enable-reentrant option to configure (disabled by default) as suggested by David Monniaux a few days ago [1]. When selected, the appropriate thread local storage class specifier is identified, added to config.h and used in tls.c. The patch is based on the work of Dmitry Nadezhin [2] and the ax_tls macro form the autoconf archive [3] simplified to match the configure.ac style, The code remains C89 if the option is not selected. I have tested this extensively but only on Linux with gcc, so additional testing and feedback is welcome. Best Regards, Chris Matrakidis [1] http://lists.gnu.org/archive/html/help-glpk/2016-12/msg00023.html [2] https://github.com/nadezhin/thermocompensation [3] http://www.gnu.org/software/autoconf-archive/ax_tls.html diff --git a/config.h.in b/config.h.in index 2849bf9..bf8dac2 100644 --- a/config.h.in +++ b/config.h.in @@ -24,4 +24,7 @@ #undef MYSQL_DLNAME /* MySQL shared library name if this feature is enabled */ +#undef TLS +/* thread local storage class specifier for reentrancy (if any) */ + /* eof */ diff --git a/configure.ac b/configure.ac index 0f57268..1688720 100644 --- a/configure.ac +++ b/configure.ac @@ -46,6 +46,16 @@ AC_HELP_STRING([--enable-mysql], esac], [enable_mysql=no]) +AC_ARG_ENABLE(reentrant, +AC_HELP_STRING([--enable-reentrant], + [enable reentrancy support [[default=no]]]), + [case $enableval in + yes | no) ;; + *) AC_MSG_ERROR( + [invalid value `$enableval' for --enable-reentrant]);; + esac], + [enable_reentrant=no]) + dnl Disable unnecessary libtool tests define([AC_LIBTOOL_LANG_CXX_CONFIG], [:]) define([AC_LIBTOOL_LANG_F77_CONFIG], [:]) @@ -141,6 +151,30 @@ else AC_MSG_RESULT([no]) fi +AC_MSG_CHECKING([whether to enable reentrancy support]) +if test "$enable_reentrant" = "yes"; then + AC_MSG_RESULT([yes]) + AC_MSG_CHECKING([for thread local storage (TLS) class specifier]) + keywords="_Thread_local __thread __declspec(thread)" + tls=none + for tls_keyword in $keywords; do + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ + #include + static void foo(void) + { static ] $tls_keyword [ int bar; +exit(1); + }])], [tls=$tls_keyword; break], []) + done + AC_MSG_RESULT($tls) + if test "$tls" != "none"; then + AC_DEFINE_UNQUOTED([TLS], $tls, [N/A]) + else + AC_MSG_ERROR([Reentrancy needs complier support for TLS]) + fi +else + AC_MSG_RESULT([no]) +fi + AC_MSG_CHECKING( [if libtool needs -no-undefined flag to build shared libraries]) case "${host}" in diff --git a/src/env/tls.c b/src/env/tls.c index 3ffa114..2a74837 100644 --- a/src/env/tls.c +++ b/src/env/tls.c @@ -23,9 +23,17 @@ #include "env.h" -static void *tls = NULL; -/* NOTE: in a re-entrant version of the package this variable should be - * placed in the Thread Local Storage (TLS) */ +#ifdef HAVE_CONFIG_H +#include +#endif + +#ifndef TLS +#define TLS +#endif + +static TLS void *tls = NULL; +/* NOTE: TLS is defined in config.h by specifying the --enable-reentrant + * option to configure */ /*** * NAME ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] indetifying an unbounded problem
Joseph, > However, when I attempt to solve this problem using the > fortran-glpk interface, the glp_simplex call returns 0. This is normal, 0 means that the call terminated successfully. > How do I identify > an unbounded problem when calling glpk via the glp_simplex function call. Calling glp_get_stat() after glp_simplex() returns 0 will give GLP_UNBND for an unbounded problem. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] counteracting infinite loops
Zephod, Indeed, this looks like an instance of cycling. However you don't provide enough information to give you specific answers. In particular you don't say whether you are solving a MIP or an LP and whether you are using the standalone solver or the API. What you can try in any case is to use the experimental long-step ratio test that was introduced in version 4.60 (see the NEWS file) which should help with the numerical stability of the solving process. Assuming you are using the API (you mentioned #define statements in your original mail) you can use something like: smcp.r_test = GLP_RT_FLIP; for an LP or iocp.flip = GLP_ON; for a MIP. Other things to try are changing the preprocessing and scaling options. Do let us know whether any of this helped with your problem. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Ruby LP Solver issues - "row name too long" for more than 29 items
Lukas, There is a spelling error in the attached file. The correct should be "budget: 400x1 +..." and "fte: 0.0x1 +...". Also note that you don't have to specify terms where the coefficient is zero, like "0.0x1" above . Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Ruby LP Solver issues - "row name too long" for more than 29 items
Lukas, Note that the example you provided specifies names for each constraint (c1 and c2): > Constraints: > c1: 398 x1 + 151 x2 + 129 x3 + 275 x4 + 291 x5 <= 800 > c2: 111 x1 + 139 x2 + 56 x3 + 54 x4 + 123 x5 <= 200 In contrast, the test code you attached has no names for the constraints. What happens is that OPL searches for a colon in each constraint and assumes that anything before it is the name. When no colon is found, the whole line is used as the name, which is limited to 255 characters in GLPK. This is a bug in OPL, and you should report it. However the obvious workaround of adding a name in your constraint should work. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.60 release information
Hi Andrew, > I think that it is sufficient just to remove perturbation and repeat the > iteration like in other cases (iteration limit, time limit, etc.), I agree, this is a better approach - the solver is faster with this change, requiring less iterations than with my patches. On a related note, in order to build a version with perturbation disabled, the attached trivial patch is required. Best Regards, Chris Matrakidis spydual.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.60 release information
Andrew, > Some improvements were made in the primal and dual simplex > solvers to make the solution process more numerically stable. Indeed, the latest version is very stable: I tried several problems that had issues before without any problems. However, the perturbation code disables the check whether the objective limit has been reached, which results in a lot more iterations. In order to address this, I tried to keep track whether objective coefficients are modified and only disable the check in this case. I attach two patches that achieve this: -The fist one adds all potential coefficient changes away from the original, and subtracts only the ones that definitely restore the original coefficient. This is an upper bound to the number of modified coefficients and as such disables the check a few times more than strictly necessary. -The second patch (relative to the first one) works a bit harder to count the exact number of modified coefficients at every point. A test case that nicely shows the improvement is with rmatr100-p5 from miplib (using a saved solution): glpsol --pcost rmatr100-p5.mps.gz --use rmatr100-p5.sol.gz All cases finish the search with 3577 nodes, but the number of iterations needed are: original 960889 iterations first patch 480941 iterations second patch 468640 iterations Best Regards, Chris Matrakidis 0001-keep-track-of-perturbed-coefficients-in-dual-simplex.patch Description: Binary data 0002-keep-track-of-perturbed-coefficients-in-dual-simplex.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.59.2 non-official test release
Andrew, >> Another thing that I noticed (but is probably normal behaviour) is >> that --proxy takes some time to find a solution when compiled with >> optimisations and x87 floating point, where using only --bestp a first >> solution is found quickly with both sse and x87 floating point. > > To find a first integer feasible solution it is better to use --bestp > rather than --bestb (the latter is default option). The best projection > heuristic (--bestp) selects a subproblem whose solution to lp relaxation > is close to an integral point while the best bound heuristic (--bestb) > attempts to minimize the size of the search tree. What I was trying to say is that the first stage of proximity search (as implemented) is using the solver with best projection search to find an initial solution, so I was (naively) expecting similar performance when using --bestp on the command line. However the proximity search one takes an order of magnitude more iterations for the first solution. I understand that the search is probably just taking a different path, but maybe it offers a hint. Best Regards Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.59.2 non-official test release
Andrew, > I see. Which glpsol options are you using? I'm unable to reproduce this > effect with just --proxy: No other options. This happens with a 32 bit compile of glpsol using "-msse3 -mfpmath=sse" with or without optimisations (up to -O2). I tried with normal x87 compilation and it continues without cycling. I also upgraded gcc to 4.9.3 without any change. Another thing that I noticed (but is probably normal behaviour) is that --proxy takes some time to find a solution when compiled with optimisations and x87 floating point, where using only --bestp a first solution is found quickly with both sse and x87 floating point. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.59.2 non-official test release
Andrew, > I tried solving it in the following way. First I used --bestp to find a > feasible solution quickly and save it to a file: ... > And then I used that solution as an incumbent value trying to "prove" > its optimality: This is essentially what --proxy does when searching for a first solution. However this doesn't work now, while in the previous version it was finding solutions. I added the line: #define glp_term_out(x) x at the beginning of proxy.c and found this: [...] Applying PROXY heuristic... Proxy's time limit set to 60 seconds. Proxy's relative improvement set to 1.00 %. Searching for a feasible solution... GLPK Simplex Optimizer, v4.59 394 rows, 321 columns, 1213 non-zeros * 0: obj = 8.685404001e+004 inf = 0.000e+000 (0) OPTIMAL LP SOLUTION FOUND GLPK Integer Optimizer, v4.59 394 rows, 321 columns, 1213 non-zeros 154 integer variables, all of which are binary Integer optimization begins... + 0: mip = not found yet >= -inf(1; 0) Warning: numerical instability (dual simplex, phase II) 242500: obj = 2.414880323e+009 inf = 7.186e+007 (25) 243000: obj = 2.414880323e+009 inf = 7.186e+007 (25) 243500: obj = 2.414880323e+009 inf = 7.186e+007 (25) 244000: obj = 2.414880323e+009 inf = 7.186e+007 (25) [...] This was with just "glpsol --proxy water.mps" and is essentially the same failure as the one I reported earlier: >> + 86090: mip = not found yet >= 1.160667584e+005(3265; 251) >> Warning: numerical instability (dual simplex, phase II) >> 294000: obj = 3.121033256e+008 inf = 5.425e+006 (14) >> 294500: obj = 3.121033256e+008 inf = 5.425e+006 (14) >> 295000: obj = 3.121033256e+008 inf = 5.425e+006 (14) >> 295500: obj = 3.121033256e+008 inf = 5.425e+006 (14) >> 296000: obj = 3.121033256e+008 inf = 5.425e+006 (14) >> 296500: obj = 3.121033256e+008 inf = 5.425e+006 (14) Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.59.2 non-official test release
inf = 5.271e-011 (449) 5 # 18000: obj = 1.5e+001 inf = 2.697e-012 (268) 5 # 18500: obj = 1.5e+001 inf = 7.744e-013 (336) 5 # 19000: obj = 1.5e+001 inf = 9.831e-014 (257) 5 # 19500: obj = 1.5e+001 inf = 2.614e-011 (238) 5 # 2: obj = 1.5e+001 inf = 8.323e-013 (340) 5 ... #263500: obj = 1.5e+001 inf = 1.244e-010 (3) 5 #264000: obj = 1.5e+001 inf = 1.400e-012 (6) 5 #264500: obj = 1.5e+001 inf = 1.128e-013 (55) 5 #265000: obj = 1.5e+001 inf = 8.249e-014 (140) 5 #265500: obj = 1.5e+001 inf = 1.594e-014 (91) 4 #266000: obj = 1.5e+001 inf = 6.091e-013 (9) 5 #266316: obj = 1.5e+001 inf = 6.831e-014 (0) 3 +266316: mip = not found yet >= 2.0e+000(3; 0) Time used: 364.7 secs. Memory used: 8.8 Mb. +270473: mip = not found yet >= 2.0e+000(5; 0) #278500: obj = 1.5e+001 inf = 2.407e-009 (273) 78 #279000: obj = 1.5e+001 inf = 7.827e-015 (128) 5 #279500: obj = 1.5e+001 inf = 7.788e-014 (263) 5 #28: obj = 1.5e+001 inf = 9.684e-012 (324) 5 #280500: obj = 1.5e+001 inf = 2.295e-012 (422) 5 #281000: obj = 1.5e+001 inf = 1.970e-011 (251) 5 #281500: obj = 1.5e+001 inf = 1.269e-012 (162) 4 ... #290500: obj = 1.5e+001 inf = 6.692e-014 (150) 5 #291000: obj = 1.5e+001 inf = 1.176e-014 (264) 4 #291500: obj = 1.57229e+001 inf = 1.459e-012 (152) 5 #291810: obj = 1.57283e+001 inf = 3.066e-013 (0) 3 +291810: mip = not found yet >= 2.0e+000(6; 0) +292194: mip = not found yet >= 2.0e+000(13; 0) +292307: mip = not found yet >= 2.0e+000(20; 0) +292325: mip = not found yet >= 2.0e+000(27; 0) ... ns1688347 was one of the problems that had issues with the previous simplex code but not at this point: ... Integer optimization begins... + 623: mip = not found yet >= -inf(1; 0) + 1911: mip = not found yet >= 2.0e+000(2; 0) + 3684: mip = not found yet >= 2.0e+000(2; 0) + 6701: mip = not found yet >= 2.0e+000(2; 0) + 10099: mip = not found yet >= 2.0e+000(6; 0) + 10131: mip = not found yet >= 2.0e+000 (15; 0) + 10141: mip = not found yet >= 2.0e+000(24; 0) ... Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] (no subject)
Andrew, Following yesterday's email, I decided to implement an error recovery procedure that allows integer optimisation to continue after an error in a heuristic (proximity search in this case). This is shown in the two attached patches: env.patch implements the necessary infrastructure to clean up after an error and proxy.patch shows how proximity search can be modified to take advantage of this. Specifically, two new functions are introduced, push_env and pop_env. push_env saves a copy of the environment block that will be used for error recovery. pop_env resets the error hook and terminal output state to the conditions they were in when push_env was called. In addition, if there was an error all memory allocated after the call to push_env is freed and the error state is cleared. These functions can be used in the following way: jmp_buf jump; ENV ctx; ... push_env(&ctx); if(setjmp(jump)) goto finish; glp_error_hook(hook, jump); The hook function just calls longjmp. >From this point on, any memory allocation will be freed on error, so it is important to avoid calling functions that can modify pre-existing problem objects. However, something like prob = glp_create_prob(); glp_copy_prob(prob, old_prob, 0); is OK (otherwise the whole mechanism would be pointless). Then before the end of the function, pop_env needs to be called: finish: pop_env(&ctx); All memory allocated after push_env needs to be freed before the call to pop_env (actually the label before it) otherwise it will be freed a second time in case of error. Overall, the mechanism is a bit limited, and not appropriate for general use. However it can be useful during integer optimisation to guard against errors in heuristics or maybe cut generation and pseudocost initialisation using strong branching. Best Regards, Chris Matrakidis env.patch Description: Binary data proxy.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Improve branch & bound time handring
Andrew, >> There have been made some other numerous changes in the source code, >> so I think to make a maintainer release, and then consider other four >> patches you proposed: > > I'll test whether the patches still apply after the release and send > updated versions if necessary. All four patches apply cleanly to the new version. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Improve branch & bound time handring
Andrew, > There have been made some other numerous changes in the source code, > so I think to make a maintainer release, and then consider other four > patches you proposed: I'll test whether the patches still apply after the release and send updated versions if necessary. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Improve branch & bound time handring
Andrew, The first patch sets the time limit for the simplex calls during branch & bound so that the overall time limit is respected. The second patch fixes a typo in dual simplex, where the wrong value is returned when the time limit expires (GLP_EITLIM instead of GLP_ETMLIM). Best Regards, Chris Matrakidis time.patch Description: Binary data dual_fix.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Try to recover from simplex errors during integer optimisation
Andrew, The attached patch implements a simple recovery procedure for simplex errors during integer optimisation. This is done by constructing a new basis and and trying to solve the LP relaxation once more. When this happens something like the following is shown: Error: unable to factorize the basis matrix (1) Constructing initial basis... which may not be optimal but I think is acceptable. Best Regards, Chris Matrakidis new_basis.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Mir cut generation performance improvement
Andrew, I noticed that mir cut generation takes considerable time on some large problems (like rocII-4-11 from miplib). The attached patch makes two improvements that considerably improve performance in such instances: 1. A lot of time was spent on generating a temporary vector in function aggregate_row. It is a lot faster to reuse an existing vector. 2. A search for an element in the same function was done in row order, where using the elements in the order they are in the column is more efficient. This changes the generated cuts in some cases, but seems neutral overall (0.3% less cuts in a test set of 64 miplib instances). Best Regards, Chris Matrakidis mir.patch Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch to add tan() to MathProg
Thank you Andrew, > Thank you for your contribution. > I have a few more patches ready. Is it better to send them to the list or to you directly? Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Patch to add tan() to MathProg
Andrew, The attached patch adds a tan() function to MathProg. I was quite surprised when I tried to use it and got an error message, so I decided to implement it. Best Regards, Chris Matrakidis tan.patch Description: Binary data ___ 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] [Fwd: glp_intopt conversion of solutions via callback]
On 17 January 2016 at 15:57, Sascha Brügmann < sascha.bruegm...@googlemail.com> wrote: > > First writing the problem/solution to disk and instantly reading it seems > a bit weird. But if this is the only way to provide an inital solution... > The only other way I know to provide an initial solution I find even more awkward... You call glp_intopt(), with presolving disabled, with a callback that calls glp_ios_heur_sol() followed by glp_ios_terminate(). Then you can call glp_intopt() a second time with presolving enabled and the use_sol parameter set. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: glp_intopt conversion of solutions via callback]
On 16 January 2016 at 17:17, Sascha Brügmann wrote: > Michael Hennebry web.cs.ndsu.nodak.edu> writes: > > Perhaps it would be a good idea to make the presolving and > > scaling transformation available to the user program. > > It could just be a matter of documentation. > > The information must already be somewhere, > > otherwise glpsol could not invert it. > Yes, thats what I'm talking about! Unfortunately it's not just a matter of documentation: internally, only the transformations to convert solutions of the preprocessed problem back to the original problem are available. Presumably, you want to use the solution you have to accelerate the solution process. There is a way to do that, but it involves using an undocumented option, so there may be some side effects. You have to set the mip solution values and status for the original problem, which can be done using a file and glp_read_mip() and then set the undocumented option use_sol before calling glp_intopt(), like in this C example: glp_read_mip(mip, "solution_file"); parm.use_sol = GLP_ON; glp_intopt(mip, &parm); Beware: the solution will not be correct for the preprocessed problem until a new one is found. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] reincarnation of tspsol
> > Why should we disable the rounding heuristic? > > Shouldn't instead the callback be called after an integer solution is > found by the rounding heuristic to verify if the new > integer solution is valid? > This is definitely a choice, but requires a bigger change to the callback API and additional effort in callback development. Therefore I still think that the option to disable the rounding heuristic (as well as every other heuristic) should be available. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] reincarnation of tspsol
> > > To avoid this, the rounding heuristic should be disabled. > > Unfortunately, there is no control parameter for this in glp_iocp, so > > I'm attaching an awful hack to disable it from the tspsol callback. > > This is only in case anyone gets an "Assertion failed: kk <= n" error > > and wants to check if this is the reason, I would advise against using > > it for any other reason. > > > > Probably the fact of specifying the callback routine can be used as a > flag to disable primal heuristics, because the callback routine itself > is able to apply heuristics performing necessary feasibility checks. > I don't like the idea of disabling primal heuristics when a callback routine is used: This is the only case where I can see a problem, while I can think of many scenarios where the heuristics are desirable together with a callback. My preference is to have a flag in glp_iocp to enable the rounding heuristic (like fp_heur and ps_heur) that would be enabled by glp_init_iocp() but the user can then disable. Alternatively (or perhaps additionally), there could be a global flag to disable all heuristics. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] reincarnation of tspsol
Hello, I think there is an issue with the way tspsol works: The rounding heuristic of glp_intopt runs after row generation (when no row was added) and may give an integer solution with subtours. The heuristic only checks that the solution satisfies the original problem, so no subtour elimination constraints are checked. Moreover, an appropriate constraint may not have been added yet. To avoid this, the rounding heuristic should be disabled. Unfortunately, there is no control parameter for this in glp_iocp, so I'm attaching an awful hack to disable it from the tspsol callback. This is only in case anyone gets an "Assertion failed: kk <= n" error and wants to check if this is the reason, I would advise against using it for any other reason. Best Regards, Chris Matrakidis --- main.c.org 2015-10-15 10:00:00.0 +0300 +++ main.c 2015-10-19 00:46:37.5 +0300 @@ -417,12 +417,28 @@ * the branch-and-cut algorithm. */ void cb_func(glp_tree *T, void *info) -{ xassert(info == info); +{ static int j, k; + if (k == 0) + k = glp_get_num_cols(P); + xassert(info == info); switch (glp_ios_reason(T)) { case GLP_IROWGEN: /* generate one violated subtour elimination constraint */ gen_subt(T); break; + case GLP_IHEUR: +for (j = 1; j <= k; j++) +{ if (glp_get_col_kind(P, j) == GLP_BV) + { glp_set_col_kind(P, j, GLP_CV); + break; + } +} +break; + case GLP_ICUTGEN: +if (j > 0 && j <= glp_get_num_cols(P)) + glp_set_col_kind(P, j, GLP_BV); +j = 0; +break; } return; } ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk