1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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
|
