bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-glpk] glp_intopt recovery feature added


From: Chris Matrakidis
Subject: Re: [Bug-glpk] glp_intopt recovery feature added
Date: Sun, 21 Feb 2016 23:57:20 +0200

Andrew,

> Also attached is a model in free mps format that illustrates the effect.
> (This model looks "innocent", but it has some pathological properties
> that makes it very hard to solve with glpk.)

This model is quite useful to demonstrate issues with the solver.

With glpk compiled using "-O1 -msse3 -mfpmath=sse" on a 32 bit system
with gcc 4.6.1 and running:
glpsol --bestp --nointopt water.mps
I was able to reproduce an error that was reported earlier:
http://lists.gnu.org/archive/html/bug-glpk/2016-01/msg00000.html

The last lines of output were:
Integer optimization begins...
+   198: mip =     not found yet >=              -inf        (1; 0)
Error: unable to factorize the basis matrix (1)
Constructing initial basis...
Size of triangular part is 521
+ 23751: mip =     not found yet >=  8.372570868e+004        (916; 2246)
+ 49757: mip =     not found yet >=  8.372570868e+004        (1518; 4753)
+ 75846: mip =     not found yet >=  8.372570868e+004        (2031; 7453)
Assertion failed: tcol[csa->p] != 0.0
Error detected in file simplex/spydual.c at line 999

Moreover, when running:
glpsol --pcost --cuts water.mps
the solver goes starts cycling. The last lines of output in this case were:
Integer optimization begins...
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
Conflict graph has 63 + 0 = 63 vertices
+   218: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: gmi = 10; mir = 31;
+ 16665: mip =     not found yet >=  1.152053280e+005        (693; 32)
Warning: numerical instability (dual simplex, phase II)
 166000: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 166500: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 167000: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 167500: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 168000: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 168500: obj =  1.343528712e+009 inf =  1.593e+007 (27)
 169000: obj =  1.343528712e+009 inf =  1.593e+007 (27)
...

Cycling also happens with glpk compiled with -O1 only, with the same
command line, but at a different point:
Integer optimization begins...
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
Conflict graph has 63 + 0 = 63 vertices
+   219: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: gmi = 7; mir = 26;
Error: unable to factorize the basis matrix (1)
Constructing initial basis...
Size of triangular part is 438
Error: basis matrix is singular to working precision (cond = 1.56e+019)
 182500: obj =  2.344435065e+018 inf =  8.057e+016 (22)
 183000: obj =  2.344435065e+018 inf =  8.057e+016 (22)
 183500: obj =  2.344435065e+018 inf =  8.057e+016 (22)
 184000: obj =  2.344435065e+018 inf =  8.057e+016 (22)
 184500: obj =  2.344435065e+018 inf =  8.057e+016 (22)
 185000: obj =  2.344435065e+018 inf =  8.057e+016 (22)
...

Best Regards,

Chris Matrakidis



reply via email to

[Prev in Thread] Current Thread [Next in Thread]