#15514: adding option for computing a total dominating set
-------------------------------------+-------------------------------------
Reporter: azi | Owner:
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/azi/adding_option_for_computing_a_total_dominating_set|
c78fd31b92c415500b98c10b47d3fde0b51cda11
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Excellent ! Well, it all looks good except your optimization for the
objective function.
1) Really, you are solving a NP-Hard problem and you are saving on a list
? `:-P`
2) Actually, this code is slower than the previous one:
{{{
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable(binary=True)
sage: %timeit sum(b[x] for x in range(1000))
10 loops, best of 3: 77.1 ms per loop
sage: %timeit p.sum(b[x] for x in range(1000))
1000 loops, best of 3: 1.09 ms per loop
}}}
This is because a "sum of LP variables" is a "linearfunction" object, and
that adding to it another LP variable creates a second linearfunction
object, which is mostly a copy of the previous one. Thus,
`b[0]+b[1]+....+b[n]` creates `n` linearfunction objects and has a
quadratic complexity.
That's why `p.sum` was created: as p.sum is dedicated to linearfunctions,
it handles the, in the best way, without creating useless intermediate
objects.
Nathann
P.S. : If you fix this in a third commit, you will haev commits which undo
what the previous commits do. It is actually possibly, using git, to merge
them all into one (called "squash" in git slang).
Two ways:
1) Look at "git rebase -i"
2) If you run "git reset HEAD~1", the last commit is "destroyed" and the
changes it contains become "unstaged" chages. This, together with "git
commit --amend" is another way to merge the commits.
--
Ticket URL: <http://trac.sagemath.org/ticket/15514#comment:23>
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.
