search

Wikunia / Bonobo.jl

A general branch and bound framework
https://wikunia.github.io/Bonobo.jl/dev
MIT License
31 stars 3 forks source link

Feature branching #11

Closed Wikunia closed 3 years ago

Wikunia commented 3 years ago

Implementation of #3

Currently there is one function get_branching_variable to obtain the branching variable itself and branch_on_variable! which creates and adds the new nodes to the tree.

The get_branching_variable defaults to call get_branching_variable(tree::BnBTree, ::FIRST, node::AbstractNode) which always returns the first discrete variable which is currently not approximately discrete. At the moment it returns -1 if no such variable can be found. Which should never happen but maybe it would be better to throw an error?

The index that is returned is then used by branch_on_variable! to create new nodes. As many nodes as wanted can be created this way. In the test cases only two nodes (standard left and right with setting lower/upper bound of the variable) is implemented currently.

I've also added the function get_discrete_indices which is called in the init step. It should simply return the list of indices which should be discrete in the end. Not sure whether it would make sense to let it default to all but it's also fairly simple to add the method.

codecov[bot] commented 3 years ago

Codecov Report

Merging #11 (634db48) into main (b134ba2) will increase coverage by 1.14%. The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##             main      #11      +/-   ##
==========================================
+ Coverage   95.94%   97.08%   +1.14%     
==========================================
  Files           3        4       +1     
  Lines          74      103      +29     
==========================================
+ Hits           71      100      +29     
  Misses          3        3
Impacted Files Coverage Δ
src/Bonobo.jl 98.03% <100.00%> (+0.12%) :arrow_up:
src/branching.jl 100.00% <100.00%> (ø)
src/util.jl 100.00% <100.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update b134ba2...634db48. Read the comment docs.

Wikunia commented 3 years ago

@matbesancon are you happy with the general structure of the branching methods? Thanks for grammar fixes :wink:

matbesancon commented 3 years ago

yes it's great, really clear now :)

Wikunia commented 3 years ago

It probably makes sense to split up the branch on variable part into two steps, right? One which creates the nodes and then they are getting added internally. This would simplify created something like strong branching which would create nodes and evaluate them without adding them to the tree.

Wikunia commented 3 years ago

Maybe this structure gives us more control.

matbesancon commented 3 years ago

a single add_node! function is probably fine for now

Wikunia commented 3 years ago

Anything else you would like to have in this PR @matbesancon ?

matbesancon commented 3 years ago

nope I think that's a great start!