4
$\begingroup$

So I'm solving bigger instances of some binary-linear-program using cplex. The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root node. Additionally I have a pretty good heuristic for calculating solutions. The heuristic is quite fast and nearly always gives the globally optimal solution.

When combining cplex with the heuristic I do not achieve the performance gains I expected. I feed the globally optimal solution to cplex as a "warm-start-solution", but it still takes quite some time for cplex to proof its optimality (cplex chooses the dual-simplex for the relaxation).

I might lack some theoretical understanding, but why can't the dual-simplex just build a basis for the supplied optimal solution and show that there is nothing else to do?

$\endgroup$
2
$\begingroup$

An IP-solver can use relaxations of variants of the integer program (that is, the linear program where the integrality constraints are dropped) among other steps to compute the final solution.

For these individual relaxations, the solver can indeed efficiently verify that it has an optimal basis. However, solving a relaxation is only a subproblem of solving the original IP. Therefore, even if you give an optimal solution to the original IP, this does not (necessarily) directly correspond to a basis in a relaxed LP, and the solver has to inspect other solutions than checking a basis.


There is one case in which providing an IP solution does allow for a fast check of optimality: when the relaxation of the IP is guaranteed to have the same solution as the original IP. (This is the case when the matrix describing the IP is totally unimodular or equivalently when the solution space is an integral polyhedron)

However, it is unlikely that the solver will be able to detect when this is the case. So, you will have to do that by some other means, and if the relaxed solution indeed solves the IP, you can let the solver solve the relaxed instance, and then the LP solver can quickly verify if your solution is optimal.

$\endgroup$

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.