I have an algorithm that iteratively runs an LP until a stability condition is met. It is guaranteed to stabilize in theory, and in practice it almost always does as well. However, sometimes the rounding error generated by whatever LP-solver I am using is high enough to prevent the stability condition from being met, so the LP runs over and over again forever.
This problem would be solved by using an exact solver that uses rational numbers instead of floats like Exact-SCIP. But I want this code to be easy for other people to run, and want to avoid installing software outside the Julia environment. I am under the impression that using Exact-SCIP would require installing SCIP on my computer. If I’m wrong I would love to corrected about that.
Is there any package in the Julia ecosystem that has an exact LP solver?
Thanks! I just tried using CDDLip with their exact solver and it technically works. However it is so slow as to be useless. It is several thousand times slower than SCIP. I expected a slow down, but that is way too much. Is there information anywhere on which solvers have exact solvers, and do you happen to know if any of them are reasonably fast?
I think that cdd might be our only exact solver that is currently connected to JuMP.
I would change your algorithm to use a less exact stopping condition. Solvers return solutions with a tolerance, and you can typically work around that in larger algorithms.
Have you considered just using a higher-precision floating-point type, instead of going exact? The Tulip solver package, among others, supports arbitrary floating-point types, so you could use BigFloat, or perhaps the ArbFloat type from the ArbFloats package (as it’s supposed to be faster than BigFloat).
We tried using a less exact condition and either it didnt work or our epsilon was so big it generated sub-optimal solutions. But we have decided to just perturb the inputs to the LP when it gets stuck, it will still converge, it just needs a little help
The problem is Simple Stochastic Games, and the algorithm is an implementation of Hoffman-Karp from this paper.
We are close to publishing our own paper about it, and we are interested in the behavior of Hoffman-Karp. For generating data we are just identifying numerical instability and chucking those are having nothing to do with the theory, and for getting a solution, we just perturb. It will work well enough for our purposes. We tried various epsilon strategies to fix the problem, but none of them worked.