MATLAB: How to interpret this output of intlinprog

intlinprog

Can anybody tell me something about this output from intlinprog function when solving a MILP problem?
The point is, on the first line it's said that the optimal objective value is -51, but the fVal I obtained is -42 (this is the real optimal solution). Normally they should be the same, but how is the difference caused?
LP: Optimal objective value is -51.000000.
Cut Generation: Applied 2 Gomory cuts,
                   16 implication cuts, 14 zero-half cuts,                                          
                   and 1 cover cut.                                                                 
                   Lower bound is -42.000000.                                                       
                   Relative gap is 0.00%.
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0 (the default value). The intcon variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).

Best Answer

The first line gives you the value of the LP relaxation of the MILP problem, which is never larger than the ultimate MILP solution, and is usually smaller.
The LP relaxation is the LP with the same bounds and linear constraints, but no integer constraints. See MILP Algorithms.
Alan Weiss
MATLAB mathematical toolbox documentation
Related Question