9
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ @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!) $\endgroup$
    – Discrete lizard
    Jun 1, 2019 at 11:53
  • 1
    $\begingroup$ 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 $\endgroup$
    – sascha
    Jun 1, 2019 at 11:54
  • $\begingroup$ 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. $\endgroup$
    – Michael Feldmeier
    Jun 1, 2019 at 11:56
  • $\begingroup$ @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. $\endgroup$
    – Discrete lizard
    Jun 1, 2019 at 11:56
  • $\begingroup$ 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 ) $\endgroup$
    – Albert Schrotenboer
    Jun 1, 2019 at 12:43

1 Answer 1

Reset to default
11
$\begingroup$

I cannot speak for Gurobi, but CPLEX definitely has this capability, and my guess is that any solver library does. For a standalone solver (as opposed to one with an API), you might have to look for the best bound in the output log and do some text scraping to get it.

For the Java API to CPLEX, the function you want is IloCplex.getBestObjValue(), which gives you the best (LP relaxation) objective value of any node still alive in the search tree.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Adding to that: in Julia/JuMP which interfaces many solvers via MathOptInterface, you can get that value via objective_bound. $\endgroup$
    – Marcus Ritt
    Jun 2, 2019 at 8:16
  • $\begingroup$ Furthermore, CPLEX allows you to set the emphasis of you solving, so that it will focus on getting e.g. a stronger bound as fast as possible or a feasible solution. The parameter in CPLEX is called MIP_EMPHASIS (see ibm.com/support/knowledgecenter/SSSA5P_12.9.0/… ) $\endgroup$
    – Tue Christensen
    Jun 2, 2019 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.