help-glpk
[Top][All Lists]

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

 From: Giorgio Sartor Subject: Re: [Help-glpk] How to provide to the GLPK MIP solver a integer feasible solution Date: Mon, 15 Apr 2013 16:40:17 +0200

>>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.

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...
+ 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

Sometimes it didn't even find an integer solution. Below an example.

0: obj =   0.000000000e+00  infeas =  4.095e+03 (0)
500: obj =   3.000000000e+00  infeas =  2.739e+03 (0)
1000: obj =   5.497354497e+00  infeas =  1.883e+03 (0)
1500: obj =   6.558965534e+00  infeas =  1.670e+03 (0)
2000: obj =   7.670952399e+00  infeas =  1.404e+03 (0)
2500: obj =   8.716450569e+00  infeas =  1.085e+03 (0)
3000: obj =   9.918056465e+00  infeas =  7.848e+02 (0)
3500: obj =   1.075182396e+01  infeas =  5.865e+02 (0)
4000: obj =   1.155616794e+01  infeas =  4.404e+02 (0)
4500: obj =   1.213734019e+01  infeas =  3.410e+02 (0)
5000: obj =   1.281056295e+01  infeas =  2.458e+02 (0)
5500: obj =   1.352593144e+01  infeas =  1.668e+02 (0)
6000: obj =   1.420632314e+01  infeas =  1.021e+02 (0)
6500: obj =   1.462023209e+01  infeas =  6.315e+01 (0)
7000: obj =   1.493993559e+01  infeas =  2.987e+01 (0)
7500: obj =   1.505026628e+01  infeas =  1.319e+01 (0)
8000: obj =   1.512207384e+01  infeas =  2.933e+00 (0)
*  8497: obj =   1.505221376e+01  infeas =  0.000e+00 (0)
*  8500: obj =   1.505085512e+01  infeas =  0.000e+00 (0)
*  9000: obj =   1.464374700e+01  infeas =  0.000e+00 (0)
*  9500: obj =   1.444370039e+01  infeas =  0.000e+00 (0)
* 10000: obj =   1.430000000e+01  infeas =  6.580e-13 (0)
* 10037: obj =   1.430000000e+01  infeas =  1.859e-13 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
| 13000: obj =   1.435649521e+01  infeas =  0.000e+00 (0)
| 13188: obj =   1.435652266e+01  infeas =  0.000e+00 (0)
Time used: 68.1 secs.  Memory used: 71.7 Mb.

Almost all the models that I tried to solve did the same thing: the presolver finds an optimal solution but the MIP solver doesn't even find an integer solution in a decent amount of time. That's way I want to provide the solver an initial solution, but apparently it isn't possibile with these conditions.
Probably I would need an additional reason code.

Gio

2013/4/14 Andrew Makhorin
On Mon, 2013-04-08 at 18:45 +0200, Giorgio Sartor wrote:
> I have a model to which I can provide a initial feasible solution.
> How can I do that?
> The GLPK reference manual offers two different methods: one is by
> using the routine glp_read_mip and the second is by using the callback
> routine glp_ios_heur_sol in response to the reason GLP_IHEUR.
> Am i right?
> First of all I can't find the differences between them. Moreover, it
> seems that none of them can help me.
> Initially I tried with glp_read_mip:
> ...
> glp_iocp parm;
> glp_init_iocp(&parm); default values
>
> glp_simplex(mip, NULL);
> glp_intopt(lp, &parm)
> ...
> but it doesn't work and the MIP solver doesn't start from
> "initialsolution" (the solution is certainly integer feasible).
> Am I using it in the correct way?

No. This feature is mainly intended to use a previously obtained
solution for further processing in MathProg models, because the solution
process may take a long time. Currently the mip solver does not use it.

> The second attempt was with the callback routine:
>
>
> void callback(glp_tree *tree, void *info){
>     switch(glp_ios_reason(tree)) {
>         case GLP_IHEUR: glp_ios_heur_sol(tree, initsol);break;
>         default: break;
>     }
> }
>
>
> where initsol was the integer feasible array solution. The code was:
> ...
> glp_iocp parm;
> glp_init_iocp(&parm);
> parm.cb_func = callback;
> glp_simplex(mip, NULL);
> glp_intopt(lp, &parm)
> ...
>
>
> The GLPK manual says:
> The callback routine is called with the reason code GLP_IHEUR if LP
> relaxation of the current subproblem being solved to optimality is
> integer infeasible...
>
>
> But in my situation glp_simplex always founds the optimal solution to
> the LP relaxation so the GLP_IHEUR flag is never called and my initial

This may only mean that optimal solution to the root lp relaxation is
integer feasible, and therefore the mip has been solved.

>
>
> How can I solve this problem? Is there anyone that can explain to me
> the difference between the two methods and how to use them?
>
>
> Gioker