#16714: Add a matrix of constraints in a LP
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.3
Component: linear | Resolution:
programming | Merged in:
Keywords: | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | 846cba629c68e46f274de8d6cbbaabd3cdbb0a99
u/vbraun/add_a_matrix_of_constraints_in_a_lp| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Replying to [comment:10 dimpase]:
> Replying to [comment:9 ncohen]:
> > Hellooooo !
> >
> > > This needs to be fixed, probably best by making MIPvariables the
elements of the parent !MixedIntegerLinearProgram.
> >
> > Can it result in any slowdown for the usual usage of those variables ?
> I'd be surprised.
> The real bottleneck is in interacting with the solver and solving
itself, anyway.
Well, I need to compute a max matching on a large bipartite graph for some
designs I build these days, and ...
{{{
sage: g=graphs.CompleteBipartiteGraph(100,200)
sage: %time _=g.matching(algorithm="LP", verbose=2)
...
Root node processing (before b&c):
Real time = 0.17 sec. (104.83 ticks)
Parallel b&c, 4 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.17 sec. (104.83 ticks)
CPU times: user 1.25 s, sys: 24 ms, total: 1.28 s
Wall time: 1.06 s
}}}
Sage reports more than 1second and the solver report 0.17. I don't really
know where the computations go to be honest at %prun does not say much.
And I suspect that it does not say much because the code that takes time
is written in Cython, i.e. the LP variables. But I haven't found a proof
yet.
> Besides, the current prevalent use of MIP frontend is very inefficient,
as you collect the linear system into a matrix, internally, and the
backend is called each time a new constraint is added, right? It's
certainly quicker to pass the matrix directly and call the backend once.
It may be faster, but the two must be possible. You don't want to have to
build a matrix for any of these problems, the code would be ugly as hell.
Being able to index variables with "anything" certainly adds something,
and not only for readability.
http://steinertriples.fr/ncohen/tut/LP_examples/
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/16714#comment:11>
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.
