class KnapsackSolver::Solver
This class solves datasets of 0/1 knapsack problem instances using a requested solving methods. It measures execution time of a solving and computes relative error if some exact solving method is requested.
Public Class Methods
Initializes solver for use of user selected solving methods.
@param opts [Hash] parser command-line options @param datasets [Hash] parsed sets of 0/1 knapsack problem instances
# File lib/knapsack_solver/solver.rb, line 18 def initialize(opts, datasets) @opts = opts @datasets = datasets @solver_objects = {} { branch_and_bound: 'KnapsackSolver::BranchAndBound', dynamic_programming: 'KnapsackSolver::DynamicProgramming', heuristic: 'KnapsackSolver::HeuristicPriceToWeight', fptas: 'KnapsackSolver::Fptas' }.each do |symbol, class_name| @solver_objects[symbol] = Object.const_get(class_name) if opts[symbol] end end
Public Instance Methods
Solve datasets using all selected method of solving, measure their execution time and compute relative errors if some exact method was requested.
@return [Hash] results of dataset solving
# File lib/knapsack_solver/solver.rb, line 35 def run results = @datasets.each_with_object({}) do |dataset, res| res[dataset.id] = @solver_objects.each_with_object({}) do |(solver, object), r| r[solver] = dataset.instances.each_with_object([]) do |inst, a| o = object.new(inst) unless solver == :fptas o = object.new(inst, @opts[:fptas_epsilon]) if solver == :fptas a << execution_time { o.run } end end end add_relative_error(results) end
Creates statistics (average price, execution times, relative error) from results of solving.
@param results [Hash] solving results of datasets and solving methods @return [Hash] statistics for datasets and solving methods
# File lib/knapsack_solver/solver.rb, line 53 def stats(results) results.each_with_object({}) do |(dataset_id, method_results), q| q[dataset_id] = method_results.each_with_object({}) do |(met, res), p| p[met] = averages(res) end end end
Protected Instance Methods
Adds relative error to results of solving if some exact method of solving was requested.
@param results [Hash] results of solving using requested methods @return [Hash] the results with relative error added
# File lib/knapsack_solver/solver.rb, line 79 def add_relative_error(results) return results unless @opts[:branch_and_bound] || @opts[:dynamic_programming] exact_method = @opts[:branch_and_bound] ? :branch_and_bound : :dynamic_programming results.each_value do |method_results| method_results.each_value do |res| res.each_with_index do |r, i| r[:relative_error] = relative_error(method_results[exact_method][i][:price], r[:price]) end end end results end
Computes average values from the results.
@param res [Hash] results for one dataset and one method @return [Array<Hash>] array of computed average values
# File lib/knapsack_solver/solver.rb, line 67 def averages(res) [res.first.keys.reject { |k| k == :config }.each_with_object({}) do |v, o| values = res.map { |i| i[v] } o[('avg_' + v.to_s).to_sym] = values.reduce(:+).to_f / values.size end] end
Measure execution time of provided block so that measured time is non-zero.
@yieldparam block for which execution time will be measured @return [Hash] solving results with cpu time and wall clock time of execution
# File lib/knapsack_solver/solver.rb, line 96 def execution_time exec_count = 1 result = nil cpu_time = wall_clock_time = 0.0 while cpu_time.zero? || wall_clock_time.zero? b = Benchmark.measure { exec_count.times { result = yield } } cpu_time += b.total wall_clock_time += b.real exec_count *= 2 end result.merge(cpu_time: cpu_time, wall_clock_time: wall_clock_time) end
Computes relative error of approximate solution.
@param opt [Numeric] Optimal price. @param apx [Numeric] Approximate price. @return [Float] Relative error.
# File lib/knapsack_solver/solver.rb, line 114 def relative_error(opt, apx) (opt.to_f - apx.to_f) / opt.to_f end