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_source=link_campaign=sig-email_content=webmail>
Virus-free.www.avg.com
<http://www.avg.com/email-signature?utm_medium=email_source=link_campaign=sig-email_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_source=link_campaign=sig-email_content=webmail> Virus-free. www.avg.com <http://www.avg.com/email-signature?utm_medium=email_source=link_campaign=sig-email_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 0x55581855 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 effec
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 <xypron.g...@gmx.de> 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, <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
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 enlight13,28,71,153.6,42008,3
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 <pietro.scio...@archinet.it> 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 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
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] 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] [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
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] 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] [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 <cmatr...@gmail.com>
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 <cmatr...@gmail.com>
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, [1], [1+len]));
+ if (!solver_addclause(s, [1], [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 <cmatr...@gmail.com>
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",
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 <m...@gnu.org> 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, > 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
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 <cmatr...@gmail.com>
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, );
+ if (bfcp.type & GLP_BF_FT)
+ { bfcp.type &= ~GLP_BF_FT;
+bfcp.type |= GLP_BF_BG;
+ }
+ glp_set_bfcp(lp, );
/* factorize and store */
glp_factorize(lp);
csa->bfd = bfd_create_it();
commit d9944e1c142a09e20ee0cf58fa660b3d09206475
Author: Chris Matrakidis <cmatr...@gmail.com>
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);
/
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
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, );
}
done: *_next = sel;
+ if (csa->work != NULL)
+ { /* clean up working probl
[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
[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] 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
8000: 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(); 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(); 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
[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 <sascha.bruegm...@gmail.com> 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, ); 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
> > > 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
