date:20170116

Re: [Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Mathieu Dutour

Yes, thank you.
Of course, that is not very nice, but better a realizable
solution to the problem than a non-existing ideal solution

Best,

  Mathieu

On 17 January 2017 at 08:41, Andrew Makhorin  wrote:

>
> > Well the behavior i would like to have is the program running and
> > givng
> > Result, OR failing to do so and reporting thar.
> > Infinite loop prevent script automation of the solver.
> >
>
> You may limit the solution time, say, to 10 secs:
>
> glpsol --tmlim 10 ...
>
>
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Andrew Makhorin


> Well the behavior i would like to have is the program running and
> givng
> Result, OR failing to do so and reporting thar.
> Infinite loop prevent script automation of the solver.
> 

You may limit the solution time, say, to 10 secs:

glpsol --tmlim 10 ...



___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Mathieu Dutour

Well the behavior i would like to have is the program running and givng
Result, OR failing to do so and reporting thar.
Infinite loop prevent script automation of the solver.

  Mathieu

On pon, 16. sij 2017. at 23:58, Andrew Makhorin  wrote:

>
>
> > the interesting thing about Matheu's example is that the infeasability
>
> > is constantly increasing over multiple orders of magnitude.
>
>
>
> I'm unable to reproduce the effect. Glpsol with default options has no
>
> problem on solving Mathieu's example. If --norelax option is specified,
>
> the primal simplex falls into infinite loop, but this might be expected,
>
> because Harris' ratio test (that is, --relax option used by default)
>
> decreases the number of degenerate steps and thus prevents cycling in
>
> many cases. If the primal simplex fails, I'd recommend using --dual and
>
> --flip options.
>
>
>
>
>
> Andrew Makhorin
>
>
>
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Heinrich Schuchardt

On 01/16/2017 11:59 PM, Andrew Makhorin wrote:
> 
>> the interesting thing about Matheu's example is that the infeasability
>> is constantly increasing over multiple orders of magnitude.
> 
> I'm unable to reproduce the effect. Glpsol with default options has no
> problem on solving Mathieu's example. If --norelax option is specified,
> the primal simplex falls into infinite loop, but this might be expected,
> because Harris' ratio test (that is, --relax option used by default)
> decreases the number of degenerate steps and thus prevents cycling in
> many cases. If the primal simplex fails, I'd recommend using --dual and
> --flip options.
> 
> 
> Andrew Makhorin
> 
> 

With GLPK 4.61 on Linux 64bit and --norelax it is not simply an infinite
loop. The infeasibility increases constantly as shown in the log below.

glpsol -m GLP_buggy_6d21.mod --norelax

*   500: obj =   1.262121212e+04 inf =   4.004e-15 (2)
*  1000: obj =   1.262121212e+04 inf =   1.052e-14 (2)
*  1500: obj =   1.262121212e+04 inf =   1.703e-14 (2)
*  2000: obj =   1.262121212e+04 inf =   2.355e-14 (2)
*  2500: obj =   1.262121212e+04 inf =   3.006e-14 (2)
*  3000: obj =   1.262121212e+04 inf =   3.658e-14 (2)
*  3500: obj =   1.262121212e+04 inf =   4.309e-14 (2)
*  4000: obj =   1.262121212e+04 inf =   4.961e-14 (2)
*  4500: obj =   1.262121212e+04 inf =   5.612e-14 (2)
*  5000: obj =   1.262121212e+04 inf =   6.264e-14 (2)
*  5500: obj =   1.262121212e+04 inf =   6.915e-14 (2)
*  6000: obj =   1.262121212e+04 inf =   7.567e-14 (2)
*  6500: obj =   1.262121212e+04 inf =   8.218e-14 (2)
*  7000: obj =   1.262121212e+04 inf =   8.870e-14 (2)
*  7500: obj =   1.262121212e+04 inf =   9.521e-14 (2)
*  8000: obj =   1.262121212e+04 inf =   1.017e-13 (2)
...
*177000: obj =   1.262121211e+04 inf =   2.304e-12 (2)
*177500: obj =   1.262121211e+04 inf =   2.310e-12 (2)
*178000: obj =   1.262121211e+04 inf =   2.317e-12 (2)
*178500: obj =   1.262121211e+04 inf =   2.323e-12 (2)
*179000: obj =   1.262121211e+04 inf =   2.330e-12 (2)
...
*826000: obj =   1.262121208e+04 inf =   1.076e-11 (2)
*826500: obj =   1.262121208e+04 inf =   1.077e-11 (2)
*827000: obj =   1.262121208e+04 inf =   1.077e-11 (2)
*827500: obj =   1.262121208e+04 inf =   1.078e-11 (2)
*828000: obj =   1.262121208e+04 inf =   1.079e-11 (2)
...
*10719000: obj =   1.262121156e+04 inf =   1.397e-10 (2)
*10719500: obj =   1.262121156e+04 inf =   1.397e-10 (2)
*1072: obj =   1.262121156e+04 inf =   1.397e-10 (2)
*10720500: obj =   1.262121156e+04 inf =   1.397e-10 (2)
*10721000: obj =   1.262121156e+04 inf =   1.397e-10 (2)


___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Andrew Makhorin


> the interesting thing about Matheu's example is that the infeasability
> is constantly increasing over multiple orders of magnitude.

I'm unable to reproduce the effect. Glpsol with default options has no
problem on solving Mathieu's example. If --norelax option is specified,
the primal simplex falls into infinite loop, but this might be expected,
because Harris' ratio test (that is, --relax option used by default)
decreases the number of degenerate steps and thus prevents cycling in
many cases. If the primal simplex fails, I'd recommend using --dual and
--flip options.


Andrew Makhorin


___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] Fwd: Re: Infinite cycles

2017-01-16 Thread Heinrich Schuchardt

Hello Andrew,

the interesting thing about Matheu's example is that the infeasability
is constantly increasing over multiple orders of magnitude.

Somewhere the restart is missing.

Best regards

Heinrich Schuchardt

 Forwarded Message 
Subject:Re: [Help-glpk] Infinite cycles
Date:   Mon, 16 Jan 2017 18:02:00 +0100
To: Heinrich Schuchardt 
CC: Help Glpk 



Dear Heinrich,

in attachment you can find a problem that runs into
infinite loops for
glpsol -m GLP_buggy_6d21.mod --norelax

and GLPSOL being version 4.61

  Mathieu

On 11 January 2017 at 19:52, Heinrich Schuchardt mailto:xypron.g...@gmx.de>> wrote:

glpsol -m GLP_buggy.mod  --norelax
runs fine.

glpsol -m GLP_buggy.mod
loops for ever.

I tested with the GLPK 4.61 prerelease.

Best regards

Heinrich Schuchardt

On 01/11/2017 12:14 PM, Mathieu Dutour wrote:
> Dear all,
>
> I obtained some infinite cycles when running the
> glpsol standalone solver on some instances.
> See two files in attachment.
>
> I had the instances of this phenomenon with
> version 4.57 which disappeared with version 4.60.
>
> Is there a way to avoid this phenomenon? I mean
> it is fully acceptable to me to have GLPK report
> that he cannot solve an instance due to numerical
> instability. What is not acceptable is the infinite
> cycles.
>
> Thanks in advance for any help.
> Sincerely,
>
>   Mathieu
>
>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org 
> https://lists.gnu.org/mailman/listinfo/help-glpk

>




GLP_buggy_6d21.mod
Description: audio/mod
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] LibreOffice example

2017-01-16 Thread Heinrich Schuchardt

Dear Andrew,

the appended archive contains an example for LibreOffice 32bit on
Windows. It requires the stdcall dll.

LibreOffice does not support calling native libraries on Linux yet.

Best regards

Heinrich Schuchardt


LibreOffice.tar.gz
Description: GNU Zip compressed data
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] Patch for pseudocost branching with product score

2017-01-16 Thread Chris Matrakidis

Hi Andrew,

This patch adds the option to select the branching variable using
pseudocosts with product score, as described in Tobias Achterberg's
thesis [1]. This is selected with a new br_tech option (GLP_BR_PMH)
and a new option in glpsol (--pcostmul), so the old default behaviour
is preserved. The patch also updates the manual accordingly.

The patch is on top of the three initial patches I sent for
speeding-up pseudocost initialisation, but should apply even without
them.

Using "glpsol --pcostmul --cuts" I was able to solve the following 32
problems from the MIPLIB 2010 benchmark set: acc-tight5, air04,
app1-2, ash608gpia-3col, biella1, bienst2, binkar10_1, core2536-691,
dfn-gwin-UUM, eil33-2, eilB101, lectsched-4-obj, map18, map20,
mcsched, mine-166-5, neos-1109824, neos13, neos18, neos-476283,
neos-686190, ns1766074, opm2-z7-s2, qiu, ran16x16, rmatr100-p10,
rmatr100-p5, rmine6, sp98ir, tanglegram1, tanglegram2 and triptim1.


Best Regards,

Chris Matrakidis

[1] T. Achterberg, "Constraint Integer Programming," PhD thesis, TU
Berlin, 2007.
commit 85cb76830f41e50c2a970f94b2da7efcf9a03cda
Author: Chris Matrakidis 
Date:   Wed Mar 9 03:06:23 2016 +0200

add --pcostmul product score option

diff --git a/doc/glpk02.tex b/doc/glpk02.tex
index 08a0219..a653a0e 100644
--- a/doc/glpk02.tex
+++ b/doc/glpk02.tex
@@ -2956,7 +2956,11 @@ Branching technique option:
 
 \verb|GLP_BR_DTH| --- heuristic by Driebeck and Tomlin;
 
-\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic.
+\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic;
+
+\verb|GLP_BR_PMH| --- hybrid pseudo-cost heuristic with product
+score\footnote{T. Achterberg, ``Constraint Integer Programming,''
+PhD thesis, TU Berlin, 2007.}.
 
 \bigskip\vspace*{-2pt}
 
diff --git a/doc/glpk10.tex b/doc/glpk10.tex
index 1943ef0..c3cc7ff 100644
--- a/doc/glpk10.tex
+++ b/doc/glpk10.tex
@@ -118,6 +118,7 @@ the problem, and write its solution to an output text file.
  (default)
--pcost   branch using hybrid pseudocost heuristic (may be
  useful for hard instances)
+   --pcostmulvariation of --pcost using product score
--dfs backtrack using depth first search
--bfs backtrack using breadth first search
--bestp   backtrack using the best projection heuristic
@@ -153,6 +154,8 @@ For description of the modeling language see the document ``Modeling
 Language GNU MathProg: Language Reference'' included in the GLPK
 distribution.
 
+\newpage
+
 For description of the DIMACS min-cost flow problem format and DIMACS
 maximum flow problem format see the document ``GLPK: Graph and Network
 Routines'' included in the GLPK distribution.
diff --git a/examples/glpsol.c b/examples/glpsol.c
index f4d4b1d..5adee8d 100644
--- a/examples/glpsol.c
+++ b/examples/glpsol.c
@@ -357,6 +357,8 @@ static void print_help(const char *my_name)
   xprintf("   --pcost   branch using hybrid pseudocost heur"
  "istic (may be\n");
   xprintf(" useful for hard instances)\n");
+  xprintf("   --pcostmulvariation of --pcost using product "
+ "score\n");
   xprintf("   --dfs backtrack using depth first search "
  "\n");
   xprintf("   --bfs backtrack using breadth first searc"
@@ -805,6 +807,8 @@ static int parse_cmdline(struct csa *csa, int argc, char *argv[])
 csa->iocp.br_tech = GLP_BR_DTH;
  else if (p("--mostf"))
 csa->iocp.br_tech = GLP_BR_MFV;
+ else if (p("--pcostmul"))
+csa->iocp.br_tech = GLP_BR_PMH;
  else if (p("--pcost"))
 csa->iocp.br_tech = GLP_BR_PCH;
  else if (p("--dfs"))
diff --git a/src/glpapi09.c b/src/glpapi09.c
index 8e5496c..cf08764 100644
--- a/src/glpapi09.c
+++ b/src/glpapi09.c
@@ -465,7 +465,8 @@ int glp_intopt(glp_prob *P, const glp_iocp *parm)
 parm->br_tech == GLP_BR_LFV ||
 parm->br_tech == GLP_BR_MFV ||
 parm->br_tech == GLP_BR_DTH ||
-parm->br_tech == GLP_BR_PCH))
+parm->br_tech == GLP_BR_PCH ||
+parm->br_tech == GLP_BR_PMH))
  xerror("glp_intopt: br_tech = %d; invalid parameter\n",
 parm->br_tech);
   if (!(parm->bt_tech == GLP_BT_DFS ||
diff --git a/src/glpios09.c b/src/glpios09.c
index 727761c..d4e1ba6 100644
--- a/src/glpios09.c
+++ b/src/glpios09.c
@@ -69,7 +69,8 @@ int ios_choose_var(glp_tree *T, int *next)
   {  /* branch using the heuristic by Dreebeck and Tomlin */
  j = branch_drtom(T, next);
   }
-  else if (T->parm->br_tech == GLP_BR_PCH)
+  else if (T->parm->br_tech == GLP_BR_PCH ||
+   T->parm->br_tech == GLP_BR_PMH)
   {  /* hybrid pseudocost heuristic */
  j = ios_pcost_branch(T, next);
   }
@@ -686,8 +687,14 @@ int ios_pcost_branch(glp_tree *T, int *_next)
  }
  /* estimate degradation of the objective for up-bra

Re: [Help-glpk] VBA examples

2017-01-16 Thread Andrew Makhorin

Hi Heinrich,

Thank you for your efforts.

> in https://github.com/xypron/glpk/tree/glpk-4.60-stdcall/examples/vba
> I have created some VBA examples. (Testing on 64bit Office is still needed.)
> 
> I also worked on LibreOffice Basic, but succeeded only on 32bit.
> 
> Are VBA examples something you would like to include in the GLPK
> source or should I add them to GLPK on Windows?

LibreOffice is free software while MS Office is not, so I'd include in
the glpk distribution only examples for LibreOffice Basic (AFAIK
LibreOffice Basic is not compatible with VBA, is it?). 

> 
> My understanding is that usage of GLPK in conjunction with a
> proprietary software is allowable but conveying both together is not
> allowable under GPL. Distributing an Excel spreadsheet sheet can be
> considered as distribution in source form when using an XML based file
> format like OpenDocument (odf) or open XML (xlsx) if the file is not
> password protected.
> 

I think GPL requirements are not related to examples.


Best regards,

Andrew Makhorin


___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Infinite cycles

2017-01-16 Thread Mathieu Dutour

Dear Heinrich,

in attachment you can find a problem that runs into
infinite loops for
glpsol -m GLP_buggy_6d21.mod --norelax

and GLPSOL being version 4.61

  Mathieu

On 11 January 2017 at 19:52, Heinrich Schuchardt  wrote:

> glpsol -m GLP_buggy.mod  --norelax
> runs fine.
>
> glpsol -m GLP_buggy.mod
> loops for ever.
>
> I tested with the GLPK 4.61 prerelease.
>
> Best regards
>
> Heinrich Schuchardt
>
> On 01/11/2017 12:14 PM, Mathieu Dutour wrote:
> > Dear all,
> >
> > I obtained some infinite cycles when running the
> > glpsol standalone solver on some instances.
> > See two files in attachment.
> >
> > I had the instances of this phenomenon with
> > version 4.57 which disappeared with version 4.60.
> >
> > Is there a way to avoid this phenomenon? I mean
> > it is fully acceptable to me to have GLPK report
> > that he cannot solve an instance due to numerical
> > instability. What is not acceptable is the infinite
> > cycles.
> >
> > Thanks in advance for any help.
> > Sincerely,
> >
> >   Mathieu
> >
> >
> > ___
> > Help-glpk mailing list
> > Help-glpk@gnu.org
> > https://lists.gnu.org/mailman/listinfo/help-glpk
> >
>
>


GLP_buggy_6d21.mod
Description: audio/mod
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Fwd: Re: Infinite cycles

Re: [Help-glpk] Fwd: Re: Infinite cycles

Re: [Help-glpk] Fwd: Re: Infinite cycles

Re: [Help-glpk] Fwd: Re: Infinite cycles

Re: [Help-glpk] Fwd: Re: Infinite cycles

[Help-glpk] Fwd: Re: Infinite cycles

[Help-glpk] LibreOffice example

[Help-glpk] Patch for pseudocost branching with product score

Re: [Help-glpk] VBA examples

Re: [Help-glpk] Infinite cycles

10 matches

Site Navigation

Mail list logo

Footer information