#18735: MixedIntegerLinearProgram: Reconstruct exact rational basic solution
----------------------------------+------------------------
Reporter: mkoeppe | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: numerical | Resolution:
Keywords: lp | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #18685, #18688 | Stopgaps:
----------------------------------+------------------------
Comment (by mkoeppe):
Replying to [comment:6 dimpase]:
> Would you mind providing an example of PPL choking on an LP doable in
exact arithmetic by another solver? We use PPL's LP solver in
`codesize_upper_bound(...,algorithm="LP")` and never saw a problem...
(Although perhaps the difficulty from entry sizes dominate the the one
from the dimension in this case).
In our experiments here, we don't actually have numerical difficulties
with floating-point based solvers; we just want to be sure that we have an
exact optimal solution. With #18764 (glp_exact; please review) we have now
run some tests to compare performance:
{{{
glp_simplex
glp_simplex+glp_exact
glp_simplex glp_exact +glp_exact ppl +
reconstruction in Sage
10 4.20 51.92 7.78 207.07 289.00
11 5.08 58.49 9.43 3451.42 574.72
12 7.55 101.72 11.32 1252.91 808.73
13 7.21 279.08 13.57 1424.28 1019.95
14 8.41 562.97 15.91 1628.54
15 13.10 550.46 18.48 2550.94
}}}
As you can see, PPL is much slower than pure glp_exact, and orders of
magnitudes slower than glp_simplex followed by glp_exact.
However, currently when we try to reconstruct the solution from the
combinatorial basis information, Sage's super slow matrix functions over
the rationals get us back to the same order of magnitude as PPL.
It would be interesting to know how the solvers perform on the kind of LPs
that you have in mind.
--
Ticket URL: <http://trac.sagemath.org/ticket/18735#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
