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.

$\endgroup$
  • $\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 '19 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 '19 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 '19 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 '19 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 '19 at 12:43
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
    $\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 '19 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 '19 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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