why does the solver give the best found solution when it already knows the best possible solution? Topic is solved

Problems with modeling
Post Reply
vbravim
User
User
Posts: 7
Joined: 3 years ago

why does the solver give the best found solution when it already knows the best possible solution?

Post by vbravim »

Hi everyone. When solving a MIP sometimes the solver gives two solutions namely the Best Found (BF) and the Best Possible (BP).

Why does the solver (using CPLEX) give the Best Found when it already knows the Best Possible?

Is the reason because it is extremely difficult to solve and takes "enormous amounts of resources"?

In my cproblem I have:
BLOCKS OF EQUATIONS 21 SINGLE EQUATIONS 275
BLOCKS OF VARIABLES 13 SINGLE VARIABLES 188
NON ZERO ELEMENTS 848 DISCRETE VARIABLES 72

Besides that,

Consider that in my minimization problem I've got these results for optcr = 0.1:

Best Found = 100
Best Possible = 90
absolute gap = 10
relative gap = 0.1

In order to get the Best Possible I've set optcr = 0.0. I expected the following results:
Best Found = 90
Best Possible = 90
absolute gap = 0.0
relative gap = 0.0

However, I've got the following:
Best Found = 95
Best Possible = 95
absolute gap = 0.0
relative gap = 0.0

In this way, why did the Best Possible solution change according to optcr?
I mean, for optcr = 0.1 the Best Possible was 90. As optcr changed to optcr = 0.0 the Best Possible changed from 90 to 95.

Could you all help me? Any source of information would be very useful.

Thank you very much.
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: why does the solver give the best found solution when it already knows the best possible solution?

Post by bussieck »

Best possible is a bound, not a solution. The Gurobi folks explain this nicely: https://www.gurobi.com/resource/mip-basics/

Hope this helps,
Michael
vbravim
User
User
Posts: 7
Joined: 3 years ago

Re: why does the solver give the best found solution when it already knows the best possible solution?

Post by vbravim »

Thank you very much, Michael.

It helped me a lot. I could get so many other things that I had been struggling with.

Best regards.
Post Reply