[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Exact conditions for start of and sequence of MIP solver
From: |
Matteo Fischetti |
Subject: |
Re: [Help-glpk] Exact conditions for start of and sequence of MIP solver |
Date: |
Thu, 16 Jan 2014 07:56:19 +0100 |
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