How to interpret this output of 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).

Answer 1

[Alan Weiss]

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

[Bruce Wang]

hi, Alan, thanks for your response. I guessed so at the very beginning, and I tried [X,fVal,flag,output]=linprog(f,A,b,Aeq,beq,LX,UX);

instead of

[X,fVal,flag,output]=intlinprog(f,intcon,A,b,Aeq,beq,LX,UX);

everything is the same except the integer constraints. However, I got -68 with the LP, not the same as -51. And thus I thought -51 is not the result from LP relaxation.

Do you think anything is wrong with my trial? Thanks a lot.

[Alan Weiss]

The intlinprog preprocessing steps can introduce new bounds or linear constraints that tighten up the LP relaxation. So I was not completely accurate in my first explanation because I didn't take this preprocessing into account.

Alan Weiss

MATLAB mathematical toolbox documentation