Re: [Help-glpk] MIP gap tolerance

[Andrew Makhorin]

> I have an issue with the "mipgap" parameter in GLPK.
> I have a mixed integer linear programming problem with (only) binary
> integer variables. And I am using GLPK in MATLAB/Octave.
> As I understood from the the help, setting the parameter "mipgap" to some
> value, e.g., 0.1, should terminate the search "if the 
> relative mip gap for currently known best integer feasible solution falls
> below this tolerance". 
> I need the solver to return a feasible solution when the gap is below a
> certain value. However, in my example when the search is terminated,
> although the output messages show some value for the objective value, the
> solver returns "zero" for the objective value and all variables, and the
> Status is 114 (which I did not find in the help). 
> Any idea what is the problem?
> 
> Here is the output messages of GLPK (for mipgap=0.1):
> ----------------------------------------------------
> GLPK Integer Optimizer, v4.42
> 2502 rows, 629 columns, 11129 non-zeros
> 625 integer variables, all of which are binary
> Preprocessing...
> 1728 constraint coefficient(s) were reduced
> 2073 rows, 629 columns, 9695 non-zeros
> 625 integer variables, all of which are binary
> Scaling...
>  A: min|aij| = 1.269e-003  max|aij| = 1.851e+000  ratio = 1.459e+003
> GM: min|aij| = 1.887e-001  max|aij| = 5.300e+000  ratio = 2.810e+001
> EQ: min|aij| = 3.766e-002  max|aij| = 1.000e+000  ratio = 2.655e+001
> 2N: min|aij| = 2.261e-002  max|aij| = 1.725e+000  ratio = 7.629e+001
> Constructing initial basis...
> Size of triangular part = 2073
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.42
> 2073 rows, 629 columns, 9695 non-zeros
> *     0: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
> *    11: obj = -4.000000000e+000  infeas = 3.195e-035 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +    11: mip =     not found yet >=              -inf        (1; 0)
> +   797: >>>>> -3.837866915e+000 >= -3.990637406e+000   4.0% (146; 121)
> +   797: mip = -3.837866915e+000 >= -3.990637406e+000   4.0% (134; 145)
> RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
> --------------------------------------------------------- 
> status = 114
> 

Looks like the matlab/octave interface module does not copy back the
solution, i.e. the bug occurs in the interface module. Try to write your
instance in cplex lp format and solve it with glpsol using the same
mipgap.

Status value 114 is 100 + GLP_EMIPGAP, I guess.