I have a problem for which there is a recursive branch and bound algorithm using exact arithmetic in a simplex solver (QSopt_ex). It is very slow even for small problems, and I was hoping to explore a heuristic to improve things but there are no obvious suitable solvers with interfaces to JuMP and Julia which might make things faster.
there are no native simplex solvers with JuMP interface
CDDlib uses global variables in the C code, so multiple instantiation is a problem
GLPK/exact does not appear to have an interface to JuMP
QSopt_ex does not have an interface to Julia/JuMP
The iterative refinement in SoPlex is reported to improve of QSOpt_ex, which may help. And SoPLex is being developed, whereas QSOpt_ex appears to have stopped. So I think moving to SoPlex is the right choice…
I note there is an interface to SCIP, but it seems to hide rather than expose SoPlex.
Can I use the exact solving capability of SoPlex through SCIP from JuMP ?
(Or would it be better to create a separate MathOptInterface to SoPlex ?)
Its not obvious how to replace CDDlib (using Rational{BigInt}) with SCIP for exact solution ?
The SoPlex documentation (SoPlex: How to use SoPlex as an exact LP solver) requires setting the following paramters:
# real:feastol = 0
# real:opttol = 0
# int:solvemode = 2
# int:syncmode = 1
The only one of these Im reasonably sure Ive mapped to SCP options is
set_attribute(model, “numerics/feastol”, 0)
But trying this with SCIP.Optimiser I get the error:
[paramset.c:166] ERROR: Invalid value <0> for real parameter <numerics/feastol>. Must be in range [1e-17,0.001].
You’re not missing anything, and unfortunately I have no pointers.
AFAIK, the only rational simplex solver hooked up to JuMP is cddlib.
I’m guessing you can’t just set numerics/feastol to 0 unless you compile SCIP differently. JuMP would also be passing the data as Float64, so it wouldn’t help very much.
Our SCIP expert is @mbesancon, who may have some other suggestions.
Hi @JonT, from the error, the tolerance must be positive, with a precision being at least 1e-17, so 0 is invalid.
We started developing SoPLEX.jl at ZIB but due to the lack of need from anyone working on exact solving, this hasn’t been pushed further yet. Note that this is meant to support exact soplex from the start.
Hi @JonT, as @mbesancon pointed out, the exact version of SCIP is not yet officially released, so going through SCIP.jl will not really help you. The error that you posted comes from the SCIP side, and there are many more problems using the current release of SCIP that will make your solution inexact (tolerances are used everywhere), even if you could solve the LP exactly using SoPlex.
SoPlex.jl seems to be your best bet, and from what I can see it should work (there is also a test that includes rational solving). If decide to try it and experience any problems or bugs, don’t hesitate to open an issue on the SoPlex.jl GitHub repo.
Since SoPlex version 7.0, SoPlex also uses a combination of LP iterative refinement and precision boosting (the algorithm that QSopet_ex is based on), which improves robustness while keeping the performance benefits of LP iterative refinement.