Re: [Help-glpk] Exact conditions for start of and sequence of MIP solver

[Matteo Fischetti]

Hi. In your problem there are alternative LP optimal solutions (due to dual 
degeneracy). So any change in the environment (in your case, the --nomip option 
that likely changes preprocessing) can randomly yield a different LP solution 
at the root node.

Note that deciding whether there exist an optimal LP solution at the root node 
that is integer is NP-hard in general, i.e., there is no easy way to tell the 
LP solver to take an integer solution in case of ties.

Matteo

Inviato da iPad

> Il giorno 15/gen/2014, alle ore 19:54, Marc Goetschalckx <address@hidden> ha 
> scritto:
> 
> I have an binary model (all variables are binary)
> For one particular instance, the LP relaxation generates a binary solution.  
> I checked this with the --nomip option and verified the solution is 
> completely binary.
> The LP relaxation is solved first inside the MIP solver.
> However, the branch and cut part of the MIP solver gets called and the 
> callback function gets called with the reason CUTGEN.
> I list next the logfile of this run.  Note that solution values of LP 
> relaxation and MIP are identical.
> 
>      0: obj =  1.009800000e+004  infeas = 1.800e+003 (0)
>    500: obj =  1.049500000e+004  infeas = 1.800e+002 (0)
> *   988: obj =  1.063500000e+004  infeas = 0.000e+000 (0)
> *  1000: obj =  1.054200000e+004  infeas = 0.000e+000 (0)
> *  1500: obj =  8.642500000e+003  infeas = 3.151e-014 (0)
> *  2000: obj =  5.304500000e+003  infeas = 1.226e-016 (0)
> *  2500: obj =  3.092666667e+003  infeas = 4.914e-016 (0)
> *  3000: obj =  1.524000000e+003  infeas = 2.498e-015 (0)
> *  3385: obj =  1.041000000e+003  infeas = 0.000e+000 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +  3385: mip =     not found yet >=              -inf        (1; 0)
> +  3401: >>>>>  1.041000000e+003 >= 1.041000000e+003   0.0% (2; 0)
> +  3401: mip =  1.041000000e+003 >=     tree is empty   0.0% (0; 3)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   1.6 secs
> Memory used: 10.4 Mb (10947806 bytes)
> 
> Why is the branch and cut section of the MIP solver even called.
> How can the unnecessary call to the cut generation routine be avoided?
> 
> -- 
> Marc Goetschalckx
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk