[Bug-glpk] Re: [Help-glpk] Is this a bug I see before me?

[Andrew Makhorin]

> Is this a bug I see before me, or the mere manifestation of a new
> feature?

> Running a variation on my favorite mathprog:

> param a, integer;
> param b, integer;
> param guess, integer;
> var x, integer;
> var y, integer;

> s1:  1 <= a*x+b*y <= guess;

> solve;

> printf "x= %i y= %i a*x+b*y= %i\n",x,y,a*x+b*y;

> data;

> param a := 75;
> param b := 15;
> param guess := 14;

> end;

> Produces:

> address@hidden:~/myGLPK/mods$ /opt/glpk.4.36/bin/glpsol --math t1.mod 
> Reading model section from t1.mod...
> Reading data section from t1.mod...
> 20 lines were read
> Generating s1...
> Model has been successfully generated
> ipp_basic_tech:  0 row(s) and 0 column(s) removed
> ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
> ipp_basic_tech:  0 row(s) and 0 column(s) removed
> ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
> glp_intopt: presolved MIP has 1 row, 2 columns, 2 non-zeros
> glp_intopt: 2 integer columns, none of which are binary
> Scaling...
>  A: min|aij| =  1.500e+01  max|aij| =  7.500e+01  ratio =  5.000e+00
> GM: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> EQ: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> 2N: min|aij| =  9.375e-01  max|aij| =  1.172e+00  ratio =  1.250e+00
> Crashing...
> Size of triangular part = 1
> Solving LP relaxation...
> *     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +     0: mip =     not found yet >=              -inf        (1; 0)
> +398442: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +797967: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +1194797: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +1593432: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +1991942: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +2389899: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +2788043: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +3186585: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +3584825: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +3982340: mip =     not found yet >=   0.000000000e+00        (2; 0)
> +3997277: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (2; 0)
> +3997277: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 3)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   50.2 secs
> Memory used: 0.1 Mb (146581 bytes)
> x= 1333334 y= -6666670 a*x+b*y= 0
> Model has been successfully processed
> address@hidden:~/myGLPK/mods$ 

> Ever since 0 has been considered a number, 1 <= 0 <= 14 has been
> considered false.

> As the only constraint is that 1 <= a*x+b*y <= 14, and a*x+b*y = 0
> is not so constrained, is the optimistic conclusion of the model
> misconceived?

This is an annoying defect in the mip solver, which may appear due
to round-off errors when there are unbounded integer variables in the
model and the model either has no integer feasible solution or such
variables have large values at the integer optimum.

For example, if x and y are bounded as follows:

var x, integer, >= -10000, <= +10000;
var y, integer, >= -10000, <= +10000;

the solver quickly detects that there is no integer feasible solution.

For you original model the solver reports the (wrong) optimum:

   x = 1333334 and y = -6666670.

It is wrong, because the constraint

   1 <= a*x+b*y <= guess;

is violated; in fact:

   a*x+b*y = 75 * 1333334 - 15 * 6666670 = 100000050 - 100000050 = 0

However, the violation, which is 1, is relatively small to the large
magnitude of constraint terms, which are of order 1e8. For example,
if you would compute the violation with 6 decimal figures, it could
be *zero*. In other words, the error appears, because your model is
badly formulated.


Andrew Makhorin