Originally posted by: SystemAdmin

I am doing a branch-and-bound but unlike CPLEX MIP I do not maintain a node pool or a basis for each node, instead I keep only a single LP and at each node (possibly after backtracking) I update the bounds information and re-solve the LP. I do it like this because my algorithm requires a depth-first search of the solution space, so it should be reasonably efficient to re-use the same LP.

Under these circumstances I get some strange results. For example it can return CPX_STAT_OPTIMAL_INFEAS which seems to mean that the LP code completed successfully but a post-optimality check revealed that the proposed solution violates some constraints. Fair enough, I tried setting CPX_PARAM_EPRHS to 1e-3 which is ridiculously lenient, this for a while seemed to make the CPX_STAT_OPTIMAL_INFEAS go away but (as far as I can recall) seemed to reveal some new problems. I forget the exact sequence of experiments but I also remember a problem that it could fail with CPX_STAT_INFEASIBLE while refusing to generate a certificate with CPXdualfarkas(), and so on.

At least in the case of the last problem it appears that re-optimizing helps, this does seem rather strange to me, because it should know when it is optimal and a call to optimize should be a no-op in that case. So I have the feeling that CPLEX is treating a second call to optimize when already optimal as a request to re-factor the basis, perhaps? Is there an official way to request that CPLEX re-factor the basis? If so, I will call this periodically and hopefully my problems will go away. What would be a good way to determine when this needs to be called? Maybe just a counter so that every 100 calls to optimize it does a refactoring? Or can I somehow recover a condition number to warn me of impending precision problems?

The whole thing is a bit mystifying because I understood that CPLEX was capable of managing precision problems itself. But maybe it's just that my unusual use case is not thoroughly tested by the development team? When using the built-in MIP optimizer, do precision problems get handled by the MIP layer or by the underlying LP layer? Or maybe they don't occur due to short-lived LP objects?

cheers, Nick
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> nick_d wrote:

> At least in the case of the last problem it appears that re-optimizing helps, this does seem rather strange to me, because it should know when it is optimal and a call to optimize should be a no-op in that case. So I have the feeling that CPLEX is treating a second call to optimize when already optimal as a request to re-factor the basis, perhaps?

Assuming you have the advanced start indicator on (which it is by default), when you issue the second call to solve(), it attempts to hot-start from the last (putatively optimal) solution. I think it just reads the last basis, though, rather than retaining the last factorization -- which, if I'm correct, means it does a clean factorization (and then dual simplex pivots or something to repair the solution if it does not look feasible).

> Is there an official way to request that CPLEX re-factor the basis?

I don't think this can be done in a callback. After solve() returns, you can call solve() again, as you discovered.

> If so, I will call this periodically and hopefully my problems will go away. What would be a good way to determine when this needs to be called? Maybe just a counter so that every 100 calls to optimize it does a refactoring? Or can I somehow recover a condition number to warn me of impending precision problems?

Once solve() has returned, there is a getQuality() method which, with a type argument of Kappa (I think), will return the condition number of the last basis.
>
> The whole thing is a bit mystifying because I understood that CPLEX was capable of managing precision problems itself. But maybe it's just that my unusual use case is not thoroughly tested by the development team? When using the built-in MIP optimizer, do precision problems get handled by the MIP layer or by the underlying LP layer? Or maybe they don't occur due to short-lived LP objects?

CPLEX tries to cope with precision issues, but (a) you can't make a silk purse out of a sow's ear and (b) futzing with precision costs speed, so CPLEX tries to find a happy compromise.

You might consider tightening the Markowitz tolerance (EpMrk), which can improve numerical precision (at the cost of some speed). You can also turn on the numerical precision switch (NumericalEmphasis).

Also, you might take a look at the scaling of your model. Scaling isn't the sole cause of numerical wobbles, but I suspect it's the most common one.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

OK, well I understand from your answer that the basis factorization is not retained across calls to CPXdualopt(), but could you check this with the developers? Because it will be enormously slower for me when I make many calls to CPXdualopt() after changing maybe a single variable bound. So much so that maybe I should look into using a competing solver, even if the "running" phase is slower.

This raises two questions:
1. If it is really refactoring the basis on each call to CPXdualopt() then why do I get precision problems? I was convinced it was due to the long life of the CPLEX LP instance. I don't think it is due to scaling issues, although I could dump the LP after a CPX_STAT_OPTIMAL_INFEAS to check this.
2. Is it possible to have a "true" warm start?

cheers, Nick
#CPLEXOptimizers
#DecisionOptimization