Class: KnapsackSolver::Solver

Inherits:
Object
  • Object
show all
Defined in:
lib/knapsack_solver/solver.rb

Overview

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.

Instance Method Summary collapse

Constructor Details

#initialize(opts, datasets) ⇒ Solver

Initializes solver for use of user selected solving methods.

Parameters:

  • opts (Hash) —

    parser command-line options

  • datasets (Hash) —

    parsed sets of 0/1 knapsack problem instances



18
19
20
21
22
23
24
25
26
27
28
 
# 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

Instance Method Details

#run ⇒ Hash

Solve datasets using all selected method of solving, measure their execution time and compute relative errors if some exact method was requested.

Returns:

  • (Hash) —

    results of dataset solving



35
36
37
38
39
40
41
42
43
44
45
46
 
# 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

#stats(results) ⇒ Hash

Creates statistics (average price, execution times, relative error) from results of solving.

Parameters:

  • results (Hash) —

    solving results of datasets and solving methods

Returns:

  • (Hash) —

    statistics for datasets and solving methods



53
54
55
56
57
58
59
 
# 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