#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | fdfe120bc438b041a7ff480a288f29d6c73b17e5
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647b |
Dependencies: |
#17665 |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooo again,
- What is the purpose of `lower_bound`? The documentation says that the
code is
trying to find an ordering whose cost is *lower* than `lower_bound`? On
what
exactly is it a lower bound?
Do you mean that the code will "return any ordering whose cost is lower
than
`lower_bound`, even if it has no proof that it is optimal?
- Do you think that you actually need `loc_b_neighborhood`? It feels like
all
you need is what you store in `bits_tmp`, i.e. the union of the prefix
and the
neighborhood. And you could drop one of your two tmp bitets.
- Are those two lines needed?
{{{
delta_i = max(current_cost, delta_i)
if delta_i < upper_bound:
}}}
It seems that you can already suppose that `current_cost<upper_bound`,
and you
checked several lines above that `delta_i < upper_bound`.
- I do not agree with this comment
{{{
if upper_bound <= lower_bound:
# Either we have optimal solution, or we are satisfied with
# current solution.
}}}
it seems that this code only deals with the case when 'we are satisfied
with
the current solution'.
- Is there any reason why you did not expose your function in the main
`vertex_separation` function? If you do, is there any reason why it
should not
be the default one? (if it is faster?..). Finally, note that if you do
make it
the default some doctests of your functions will have to be updated, as
you
would be comparing the BAB function with `vertex_separation` (which
would also
call the BAB).
With those comments and those from my previous message, I would say that
my
review is finished. We only have to settle those last remarks.
Thanks for your work!
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:36>
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.
