#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Nathann Cohen
theory | Work issues:
Keywords: | Commit:
Authors: David | 2f0bf7a386eff5ff28a9ce87106ab50ab5c5488a
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647b |
Dependencies: |
#17665 |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hello,
> Apparently your care a lot about reducing mallocs.
Having a short code that only does what is needed helps a lot when you try
to understand someboy else's code.
> > 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?
> Exactly.
Okay I understand. That helps when you split your first graph into
subproblems. This being said, the term `lower_bound` seems to indicate
that the user can provide a lower bound on the optimal value of the graph,
which confused me when I read code that dealt with returning any "solution
below the lower bound". What would you think of renaming it to something
like "accept_any_below=4"? That's the best keyword I found, but if you
have in mind something which could represent a bit better what it does...
I find this name confusing.
> > - Are those two lines needed?
> >
> > {{{
> > delta_i = max(current_cost, delta_i)
> > if delta_i < upper_bound:
> > }}}
> If we reduce the upper bound during the recursive call of the kth
element of the list, we want to prune (cut) branches that are no longer
useful.
> So yes, these lines are needed.
Oh I see. I had not noticed that `upper_bound` was updated at every loop.
Consequently, wouldn't it be better to do something like that instead?
{{{
if delta_i >= upper_bound:
break
<continue exploring>
}}}
> Yep, I have many reasons for not exposing the BAB in the main
`vertex_separation` function yet.
> 1. this patch is already quite long and technical. Since you often
complain about patch bombs, I did my best to decompose the work
> 2. I plan to add pre-processing rules. The first one is to decompose the
input digraph into strongly connected components, but I have others, more
complex. I will work on this part only when the BAB will be finalized
(including memoization of prefixes). I believe its better to wok this way.
Okay, as you like. As long as you plan to do it in the short future, you
can manage the patches as you like.
Nathann_from_Nantes
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:40>
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.
