class KnapsackSolver::BranchAndBound

This class implements methods for solving 0/1 knapsack problem using Branch and Bound method.

Public Class Methods

new(instance) click to toggle source

Initializes instance of Brand and Bound 0/1 knapsack problem solver.

@param instance [Instance] 0/1 knapsack problem instance

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 8
def initialize(instance)
  @instance = instance
  @config = Array.new(instance.things.size)
end

Public Instance Methods

run() click to toggle source

Solve the instance of 0/1 knapsack problem.

@return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 16
def run
  solve(0)
  { price: @best_price, config: @best_config }
end

Protected Instance Methods

config_price(start_index, end_index) click to toggle source

Gets price of set of things. The set is subset of the things ordered by their index.

@param start_index [Integer] index of the first thing included in the set @param end_index [Integer] index of the last thing included in the set @return [Integer] price of the things

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 91
def config_price(start_index, end_index)
  price = 0
  @config[start_index..end_index].each_with_index do |presence, index|
    price += presence * @instance.things[index].price
  end
  price
end
config_weight(start_index, end_index) click to toggle source

Gets weight of set of things. The set is subset of the things ordered by their index.

@param start_index [Integer] index of the first thing included in the set @param end_index [Integer] index of the last thing included in the set @return [Integer] weight of the things

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 77
def config_weight(start_index, end_index)
  weight = 0
  @config[start_index..end_index].each_with_index do |presence, index|
    weight += presence * @instance.things[index].weight
  end
  weight
end
get_price_of_remaining_things(from_index) click to toggle source

Gets sum of prices of things for which their presence in the knapsack was not decided yet.

@param from_index [Integer] index of the first undecided thing @return [Integer] price of the remaining things

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 104
def get_price_of_remaining_things(from_index)
  price = 0
  to_index = @instance.things.size - 1
  @instance.things[from_index..to_index].each { |t| price += t.price }
  price
end
solve(index) click to toggle source

Solve the problem starting at specified thing.

@param index [Integer] index of thing which will be decided (put in or out from the knapsack) the next

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 26
def solve(index)
  @config[index] = 0
  solve(index + 1) unless stop(index)
  @config[index] = 1
  solve(index + 1) unless stop(index)
end
stop(index) click to toggle source

Determine if solving of current branch should continue.

@param index [Integer] index of the last decided thing so far @return [true, false] weather to continue with solving current branch.

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 37
def stop(index)
  # Update of the best price so far
  weight = config_weight(0, index)
  price = config_price(0, index)
  update_best_price(price, weight, index)
  # No more things to put into the knapsack
  return true if index >= (@instance.things.size - 1)
  # The knapsack is overloaded, do not continue this branch
  return true if weight > @instance.weight_capacity
  if instance_variable_defined?('@best_price') &&
     ((price + get_price_of_remaining_things(index + 1)) <= @best_price)
    # Adding all the ramining things does not produce better price
    return true
  end
  false
end
update_best_price(price, weight, index) click to toggle source

Update the best price achieved so far.

@param price [Integer] price of the current configuration @param weight [Integer] weight of the current configuration @param index [Integer] index of the next thing presence of which will be decided

# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 59
def update_best_price(price, weight, index)
  if !instance_variable_defined?('@best_price') ||
     ((weight <= @instance.weight_capacity) && (price > @best_price))
    @best_price = price
    valid_len = index + 1
    remaining = @config.size - index - 1
    # All undecided things will not be put into the knapsack
    @best_config = @config.slice(0, valid_len).fill(0, valid_len, remaining)
    @best_config_index = index
  end
end