Re: [Bug-glpk] Numerical instability

[Andrew Makhorin]

> tho following error occured wile version 4.26 on attached ILP problem.

> Any advice how to avoid such problems is welcome.

> GLPK internal error: x <= ub; file ..\src\glpios03.c, line 265

Thank you for the bug report.

This error appears, because the glpk mip solver is not sufficiently
robust. As a rule the error is caused by ill-conditioned basis matrix
that, in turn, leads to excessive round-off errors in solution of
current lp relaxation. Probably you instance has large (in magnitude)
constraint coefficients at integer variables. Please see:
http://lists.gnu.org/archive/html/bug-glpk/2007-12/msg00005.html

Nevertheless, I managed to solve your instance to optimality with
glpsol --noscale --cuts:

+590928: mip =   1.738300000e+04 >=   1.544270065e+04  11.2% (3019; 27700)
+592476: mip =   1.738300000e+04 >=   1.554327064e+04  10.6% (2851; 28427)
+593947: mip =   1.738300000e+04 >=   1.560953674e+04  10.2% (2608; 29436)
+595559: mip =   1.738300000e+04 >=   1.580084072e+04   9.1% (2352; 30322)
+596987: mip =   1.738300000e+04 >=   1.592364844e+04   8.4% (2128; 31041)
+598429: mip =   1.738300000e+04 >=   1.611015105e+04   7.3% (1880; 31985)
+600160: mip =   1.738300000e+04 >=   1.618175000e+04   6.9% (1627; 32967)
+601728: mip =   1.738300000e+04 >=   1.633417578e+04   6.0% (1364; 33864)
+603034: mip =   1.738300000e+04 >=   1.653693735e+04   4.9% (1069; 35097)
+604279: mip =   1.738300000e+04 >=   1.680371170e+04   3.3% (722; 36692)
+605552: mip =   1.738300000e+04 >=   1.700495011e+04   2.2% (460; 38099)
+606579: mip =   1.738300000e+04 >=   1.730659137e+04   0.4% (63; 40855)
+606712: mip =   1.738300000e+04 >=     tree is empty   0.0% (0; 41563)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   857.1 secs
Memory used: 30.4 Mb (31907668 bytes)

Result of optimisation
Objective criterion:
17383
Start times s:
1080 628 1080 360 1080 1080 1080 695 648 360 
960 793 960 960 960 960 780 960 780 780 
840 998 840 840 840 1080 840 840 840 840 
480 480 480 480 480 480 480 480 660 480 
840 840 1080 1080 840 840 840 840 1080 840 
660 660 660 660 660 660 660 660 660 920 
1080 1080 1080 360 1080 1080 1080 1000 687 1495 
Variable x:
0 0 0 0 0 0 1 
0 0 0 0 0 0 0
. . .
0 0 0 0 0 0 1
0 0 0 0 0 0 0 
Used vehicles:
4
Model has been successfully processed


Interesting to note that the mip solver found optimial solution
at once, and the rest time was spent to prove its optimality.

Andrew Makhorin