>>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...
+ 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
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...
+ 10037: mip = not found yet >= -inf (1; 0)
+ 10389: mip = not found yet >= 1.500000000e+01 (3; 0)
+ 10870: mip = not found yet >= 1.500000000e+01 (4; 0)
+ 11361: mip = not found yet >= 1.500000000e+01 (5; 0)
+ 11856: mip = not found yet >= 1.500000000e+01 (6; 0)
| 13000: obj = 1.435649521e+01 infeas = 0.000e+00 (0)
| 13188: obj = 1.435652266e+01 infeas = 0.000e+00 (0)
+ 13188: mip = not found yet >= 1.500000000e+01 (7; 0)
+ 14132: mip = not found yet >= 1.500000000e+01 (8; 0)
+ 14965: mip = not found yet >= 1.500000000e+01 (9; 0)
+ 15761: mip = not found yet >= 1.500000000e+01 (10; 0)
Time used: 68.1 secs. Memory used: 71.7 Mb.
+ 15761: mip = not found yet >= 1.500000000e+01 (10; 0)
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 <[email protected]>
> 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_read_mip(mip, "initialsolution");
> >
> > 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
> > solution is not loaded.
>
> 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
>
>
>
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
