#10341: make MIP backend interface more Python-ic
----------------------------------------------+-----------------------------
Reporter: malb | Owner: ncohen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.6.1
Component: linear programming | Keywords: LP, MIP
Author: Martin Albrecht, Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------------------+-----------------------------
Comment(by ncohen):
Oh ! To compare performances, you could just try a sage -t on graph.py
digraph.py and generic_graph.py.
I guess the performances would then depend on the kind of problem : all
the solvers I tried until now are just awful for the minor method :
{{{
#!python
sage: %time graphs.Grid2dGraph(5,5).minor(graphs.CompleteGraph(4), solver
= "GLPK")
CPU times: user 10.59 s, sys: 0.01 s, total: 10.60 s
Wall time: 10.62 s
{0: [(1, 3), (1, 2), (3, 3), (4, 4), (1, 4), (2, 3), (3, 4)], 1: [(2, 1),
(2, 2), (3, 2), (4, 2), (2, 0)], 2: [(0, 0), (1, 0), (0, 1), (0, 2)], 3:
[(1, 1)]}
}}}
The methods raises an exception when 4 becomes 5, which is natural as the
problem has no solution, but it takes one lifetime to get this answer from
GLPK. If SCIP can get it quickly, that's just a miracle `:-D`
Another problem of the same kind :
{{{
#!python
n = 7
graphs.Grid2dGraph(n,n).disjoint_routed_paths([((0,0), (n-1,n-1)), ((0,
n-1), (n-1, 0))])
}}}
This already takes 10 seconds with CPLEX. Try n=8 if you are patient !
The answer is also an infeasibility, and the solvers are having a hard
time proving it.. But I guess it just comes from my bad LP formulation
`^^;`
A different type of LP formulation, on random graphs :
{{{
#!python
from sage.graphs.graph_coloring import edge_coloring
%timeit edge_coloring(graphs.RandomGNP(30,.3), solver = "GLPK", verbose =
2)
5 loops, best of 3: 4.47 s per loop
}}}
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10341#comment:28>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
