# How to get bounds on ILP optimal solution quality

Often, ILP formulations are just too complicated to solve optimally in reasonable time. In those cases, you can still run a solver for some fixed time and simply take the best solution that the solver found.

However, I want to obtain upper bounds on the optimal solution quality (for maximisation problems, obviously) from an ILP solver after only running for a fixed time. This should be possible in theory, as a solver should maintain such a bound in some form (as far as I'm aware).

Is this functionality implemented in common solvers such as CPLEX or Gurobi? If so, how is this functionality called? (so that I can find how to do this in a manual of a solver) An example of how to do this in a solver of your choice is also appreciated.

• @MichaelFeldmeier Are you sure? Suppose $V$ is the value of an optimal solution. Then for any feasible solution, its value is $\leq V$ and therefore a lower bound of the optimal solution value. I'm looking for an upper bound, for which likely there is no solution corresponding to it (else that solution would be optimal!) Jun 1, 2019 at 11:53
• It's a bit unclear what you are after. Reading out "current" bounds is for free and you should go for the solver docs, e.g. Gurobi's ObjBound. But it seems this is not enough for you: it sounds as you are more interested in those bounds than a feasible solution. Usually, this might call for more cuts and less primal heuristics; but things are complex and solvers allow to some kind of profiles for this. Again for Gurobi: MIPFocus Jun 1, 2019 at 11:54
• sorry, had it the wrong way round. You are maximizing. Solving the LP relaxation (ignoring integrality constraints) gives an upper bound for the integer programme. This is usually referred to as dual bound. Jun 1, 2019 at 11:56
• @sascha My main question is how to read out the bound that does not correspond to a feasible solution. I'm not looking to prioritize finding this bound over finding a solution. I think you can expand that comment into an answer. Feel free to edit the question if you think you can make it more clear. Jun 1, 2019 at 11:56
• As Michael says; one solves ILP by branch and bound; in every node the integrality restrictions are relaxed and an LP is solved. The solution of this LP is called the dual bound, and is by definition an upper bound ( in a maximization problem ) Jun 1, 2019 at 12:43