# Ruby Branch and Bound Algorithm implementation?

I am relatively new to Ruby and am trying to get a handle on making my code more Ruby-esque. At the same time I am experimenting with the branch and bound algorithm to solve a problem that I outline in this blog post. I would also welcome any feedback on the quality of my implementation. The full source code is on my github here, but here is the code for the branch bound class:

require './widget'
require './requirements'
require 'benchmark'

class BranchBoundSearch
@best_score = nil
@best_combos = []

def initialize(scorer, main_requirement_label, all_possible)
@scorer = scorer
@main_requirement_label = main_requirement_label
@all_possible = all_possible
end

# Given a widget_array first calculate it's score, and add it as a branch in the
# list of branches based on the quality of it's score. Better scores are first.
# Branches that do not meet the size requirement are not added to the branches
# array. This effectively kills that branch.
score_hash = @scorer.get_score_hash(widget_array)
score = @scorer.get_total_score(score_hash)
branches_index = 0

if score_hash[@main_requirement_label] >= 0
while not added and branches_index < branches.length do
if @scorer.get_better_score(score, branches[branches_index][1]) >= 0
branches.insert(branches_index, [score_hash,score,widget_array])
end
branches_index += 1
end

branches.push([score_hash, score,widget_array])
end
end
end

# Branch and bound recursive search. Provided an in array which represents the
# node which will be branched off of. Roughly, the function first creates a list
# of potential branches which are ordered by the quality of their score.
# Potential branches are then looped through, if a potential branch is viable the
# function is called again with it as the root node. This continues until
# exhaustion of all possiblities.

def branch_and_bound(in_array)
branches = []
@all_possible.each do |widget|
branch_array = in_array + [widget]
end

branches.each do |branch|
score_hash = branch[0]
score = branch[1]
widget_array = branch[2]
score_comparison = @scorer.get_better_score(score, @best_score)

if score_comparison == 0
@best_combos.push(widget_array)
continue_branch_investigation = true
elsif score_comparison == 1
@best_combos = [widget_array]
@best_score = score
continue_branch_investigation = true
elsif score > 0
continue_branch_investigation = true
end

if continue_branch_investigation
branch_and_bound(widget_array)
end
end
end

def get_best_score()
return @best_score, @best_combos
end
end


best_score_90 = nil
best_set_90 = []
best_score_90_bb = nil
best_set_90_bb = []
best_score_400 = nil
best_set_400 = []
best_score_400_bb = nil
best_set_400_bb = []
time=Benchmark.bm(7) do |x|
x.report("brute[90]:") do
scorer = Scorer.new(requirements_90, :size)
brute = BruteSearch.new(scorer, :size)
possible_combos = brute.enumerate_possible([], all_widgets.dup)
best_score_90, best_set_90 = brute.get_best_score
end

x.report("brute[400]:") do
scorer = Scorer.new(requirements_400, :size)
brute = BruteSearch.new(scorer, :size)
possible_combos = brute.enumerate_possible([], all_widgets.dup)
best_score_400, best_set_400 = brute.get_best_score
end

x.report("b&b[90]:") do
scorer = Scorer.new(requirements_90, :size)
bb = BranchBoundSearch.new(scorer, :size, all_widgets)
bb.branch_and_bound([])
best_score_90_bb, best_set_90_bb = bb.get_best_score
end
x.report("b&b[400]:") do
scorer = Scorer.new(requirements_400, :size)
bb = BranchBoundSearch.new(scorer, :size, all_widgets)
bb.branch_and_bound([])
best_score_400_bb, best_set_400_bb = bb.get_best_score
end
end

puts "Best set [90] brute: " + widget_array_to_s(best_set_90)
puts "Score[90] brute: " + best_score_90.to_s


Thanks for the help!

• A note from experience: if you ask to review so many LOC, chances are nobody will answer, too much work. Maybe you can reduce it to a method you're specially worried about. – tokland May 16 '13 at 21:01
• This is just a style suggestion, but please do use the spacebar a little more. It is more "Ruby'esque" to write x = y and foo(bar, baz), instead of x=y, foo(bar,baz). Same with commented lines: # comment instead of #comment. Last tip: Generally speaking, array variables are plural nouns, so widgets instead of widget_array. This naming scheme is why Ruby's Array has a method called include?. The line widgets.include?(x) makes grammatical sense, while widget_array.include?(x) doesn't really. – Flambino May 16 '13 at 21:01
• Small thing but you don't need to write return in get_best_score. Result of last evaluation is returned by default in Ruby. – Mike Szyndel Jul 14 '13 at 20:07
• Is there any case when this will be false (or nil)? continue_branch_investigation – Mike Szyndel Jul 14 '13 at 20:22

One thing that will help a lot is using attr_accessor. You can use is so that you don't have so many instance variables littering your methods. You can also initialize best_score and best_combos and give them default values. (But generally, according to Sandi Metz, you should try to avoid passing in more than 4 arguments to any method.) Also, avoid if not. Opt instead for unless.

class BranchBoundSearch

attr_accessor :scorer, :main_requirement_label, :all_possible, :best_score, :best_combos

def initialize(scorer, main_requirement_label, all_possible, best_score=, best_combos)
@scorer = scorer
@main_requirement_label = main_requirement_label
@all_possible = all_possible
@best_score = nil
@best_combos = []
end
score_hash = scorer.get_score_hash(widget_array)
score      = scorer.get_total_score(score_hash)
...
branches.push([score_hash,score,widget_array])
end
...


That will get you at least some of the way, but you did post quite a bit of code.

Replace this

branches.each do |branch|
score_hash = branch[0]
score = branch[1]
widget_array = branch[2]
...


with

branches.each do |score_hash, score, widget_array|
...


This one

if score_comparison == 0
...
elsif score_comparison == 1
...
elsif score > 0
...
end


with

case score_comparison
when 0
...
when 1
...
else
...
end


You pass a param but there's no reason for it

add_branch(branch_array, branches)

because you may make branches an instance variable @branches.