Originally posted by: SystemAdmin

Earlier I described my current application of CPLEX Dual Simplex LP optimizer, which is essentially to load a large model and then continually change bounds and re-solve, extracting a Farkas proof when infeasible or dual values for sensitivity analysis when feasible. Sometimes I also add/remove rows. I do not use presolving or scaling.

The first numerical issue I encountered was a status of CPX_STAT_OPTIMAL_INFEAS which I believe means that Dual Simplex ran normally to completion but a post-optimality check revealed some x-values slightly outside their bounds. This was easy to work around: Simply call CPXdualopt() again and the problem goes away, for me at least. I'm not sure if this second call to CPXdualopt() actually involves any pivoting but I would imagine it simply refactors the basis and re-checks x against bounds and finds it's OK.

Now I have a new issue which is somewhat more troubling: False reports of infeasibility. This occurs on a model where I have somewhat larger variable bounds than previously, e.g. x ranges from 0 to 800 whereas on previous models most x were Boolean or small integers (usually < 50). I find that making a second call to CPXdualopt() again solves the problem. In this case the first call to CPXdualopt() has aborted too early and the second call to CPXdualopt() continues optimizing for some time.

Unfortunately while the workaround in the first case was acceptable (CPX_OPTIMAL_INFEAS does not occur very often) the workaround in the second case is totally unacceptable to me, because CPX_STAT_INFEASIBLE occurs all the time and the second call to CPXdualopt() will be too expensive in the general case, given that it (apparently) refactors the basis before attempting any iterations.

I found that turning on numerical emphasis or changing Markowitz tolerance to 0.1 or changing feasibility tolerance to 1e-3 or 1e-9 did not change the situation, however, changing optimality tolerance to 1e-9 does apparently help (1e-3 does not). This seems surprising as I wouldn't think the optimality tolerance would play any role in false reports of infeasibility? I am suspicious that I am simply avoiding the problem (on this instance) by taking a different path to the solution and that it will recur in future with equal probability on different instances. Also I am a bit confused about the role of feasibility and optimality tolerance with the Dual Simplex optimizer, though I understand what they would do with the Primal Simplex optimizer. Are the roles simply swapped with dual Simplex?

While writing this message I was also doing some other checks in the background and I now discover that when it falsely reports infeasibility the "proof" value returned by CPXdualfarkas() is negative, in the case I am looking at, significantly negative: I see -509.999999999999886 when it is supposed to be strictly positive... I could use this information to implement a workaround and I will certainly attempt to do so. But surely this indicates something is wrong? Could it be a bug in CPLEX?

cheers, Nick
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If you could post a SAV file for an instance with a false signal of infeasibility, someone here might be able to poke at it and derive an insight.

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

Good news! Since I changed a lot of stuff I reran all results while making it print a warning message if a CPLEX workaround was activated, I was planning to take some particular instance which gave a warning and dissect it to produce a minimal example for you, but it appears the problem has gone away. The workaround for false report of infeasibility was activated once, but since the "proof" value returned from CPXdualfarkas was very close to zero, this appears to be a question of tolerances so nothing much to worry about (though the workaround probably does help). I did fix one problem which could have led to memory corruption (although this would happen incredibly rarely) so maybe it was my fault. I will keep an eye on it, just in case. Thanks for listening.
#CPLEXOptimizers
#DecisionOptimization