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]) >= 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 score = branch widget_array = branch 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:") 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:") 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:") 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:") 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  brute: " + widget_array_to_s(best_set_90) puts "Score brute: " + best_score_90.to_s
Thanks for the help!