1 files changed, 118 insertions, 0 deletions
diff --git a/lib/knapsack_solver/solver.rb b/lib/knapsack_solver/solver.rb
new file mode 100644
index 0000000..c392d69
--- /dev/null
+++ b/lib/knapsack_solver/solver.rb
@@ -0,0 +1,118 @@
+require 'benchmark'
+
+require 'knapsack_solver/dataset'
+require 'knapsack_solver/solving_methods/heuristic_price_weight'
+require 'knapsack_solver/solving_methods/branch_and_bound'
+require 'knapsack_solver/solving_methods/dynamic_programming'
+require 'knapsack_solver/solving_methods/fptas'
+
+module KnapsackSolver
+  # 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.
+  class Solver
+    # 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
+    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
+
+    # 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
+    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
+    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
+
+    # Computes average values from the results.
+    #
+    # @param res [Hash] results for one dataset and one method
+    # @return [Array<Hash>] array of computed average values
+    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
+
+    # 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
+    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
+
+    # 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
+    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.
+    def relative_error(opt, apx)
+      (opt.to_f - apx.to_f) / opt.to_f
+    end
+  end
+end