[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Numerical instability
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] Numerical instability |
Date: |
Tue, 15 Apr 2008 15:57:49 +0400 |
> 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