#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 dcoudert):
> > > 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.
It is used for both usage: If a lower bound is known, then the user can
provide it to the BAB to stop if a solution reaches this bound. It can
also be used to say "I'm happy with any solution with cost less than k".
I propose to rename it `cut_off` as for shortests paths algorithms.
I have updated the doc and tests accordingly
> > > - 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>
> }}}
Right, done.
> > 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
Let us know if you meet Lulu ;)
Thank you again for the review.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:41>
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.
