Re: [Help-glpk] How to provide to the GLPK MIP solver a integer feasible solution

[Andrew Makhorin]

> >>This may only mean that optimal solution to the root lp relaxation
> is
> >>integer feasible, and therefore the mip has been solved.
> 
> 
> Well, I thought that it wasn't true, in fact the manual says:
> 
> 
> The difference between optimal solution to LP relaxation and
> corresponding MIP solution is that in the former case some structural
> variables of integer kind (namely, basic variables) may have values,
> which are close to nearest integers within the working precision,
> while in the latter case all such variables have exact integral
> values.
> 
> 
> Hence, an optimal solution to the LP relaxation doesn't imply that it
> corresponds to the integer optimal solution.
> Below I show an example. The presolver finds an optimal solution but
> the first solution found by the MIP solver is not the optimal one and
> it has to continue searching for the optimal one.

Probably there is some misunderstanding. The message "optimal solution
found" prior to beginning of integer optimization means that the lp
solver (not the presolver!) found an optimal solution to lp relaxation
of the root problem, and that solution was integer infeasible, since the
mip solver performed branching. In particular, this means that before
branching the mip solver called the user's callback with GLP_IHEUR
request.

> 
> 
>   24944: obj =   1.620000000e+02  infeas =  6.720e+02 (0)
>   25000: obj =   1.640000000e+02  infeas =  5.880e+02 (0)
>   25500: obj =   2.004514286e+02  infeas =  1.707e+02 (0)
> * 25922: obj =   1.999972598e+02  infeas =  0.000e+00 (0)
> * 26000: obj =   1.807113515e+02  infeas =  8.842e-15 (0)
> * 26500: obj =   2.212500000e+01  infeas =  1.566e-13 (0)
> * 27000: obj =   3.000000000e+00  infeas =  1.176e-13 (0)
> * 27159: obj =   3.000000000e+00  infeas =  2.988e-14 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> + 27159: mip =     not found yet >=              -inf        (1; 0)
> + 27362: >>>>>   5.000000000e+00 >=   3.000000000e+00  40.0% (4; 0)
> + 27362: mip =   5.000000000e+00 >=   3.000000000e+00  40.0% (2; 3)
> RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
>