Ruby Branch and Bound Algorithm implementation?

Question

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.
 def add_branch(widget_array, branches)
 score_hash = @scorer.get_score_hash(widget_array)
 score = @scorer.get_total_score(score_hash)
 added = false
 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])
 added = true
 end
 branches_index += 1
 end
 if not added
 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]
 add_branch(branch_array, branches) 
 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

I'm also concerned about this specific code block:

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!

• tokland: 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.
• Flambino: 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.
• Mike Szyndel: 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: Is there any case when this will be false (or nil)? continue_branch_investigation

Answer 1

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
 # That way, you have access to scorer without calling @scorer.
 def add_branch(widget_array, branches)
 score_hash = scorer.get_score_hash(widget_array)
 score = scorer.get_total_score(score_hash)
 ...
 unless added
 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.

Answer 2

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.