I have developed a model for my master thesis. The model runs and finds some integer solutions (these solutions are actually valid solutions), yet no optimal solution is found. The problem is that the best bound is always equal to 0, this leads to the value of the gap equal to 100% (the best solution is equal to 24.75). My question is whether this is a problem or not, and whether there is a way to increase the value of the best bound.

It seems to me that the problem is that there is no lower bound to the problem. For this reason, the best bound is not calculated. But I will leave it to you guys.

Thank you for all your help

Francesco

The best bound is based on the objective function value of the LP relaxation of your MIP. Since you have a best bound of zero throughout the solve, it suggest that relaxing the integrality requirement on some of your variables results in a relaxed problem whose objective function value is zero. Given enough solve time, you would eventually see the best bound move away from zero, or find a MIP solution with zero value.

You can try increasing the amount of cuts created by the Xpress-Optimizer, as Susanne suggested. There are a few different control parameters that could be useful here:

CUTSTRATEGY: Set it to 3 to allow for more cuts to be added to the problem

COVERCUTS, GOMCUTS: These two controls determine how many rounds of cuts to create for the root problem. The default is around 20 and 2. You can try larger values.

CUTFREQ: How frequently to create cuts during the branch-and-bound search. You can try setting this to something more aggressive, like every 2 nodes.

If you are using Mosel, to set a control like CUTFREQ=2 you would call

setparam("XPRS_CUTFREQ", 2)

I hope this helps, but vehicle routing problems can be very hard so it might not be possible to solve your current model to optimality in any reasonable amount of time.