Class: NoSE::Search::Problem

Inherits:
Object
  • Object
show all
Defined in:
lib/nose/search/problem.rb

Overview

A representation of a search problem as an ILP

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(queries, updates, data, objective = Objective::COST) ⇒ Problem

Returns a new instance of Problem.



33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/nose/search/problem.rb', line 33

def initialize(queries, updates, data, objective = Objective::COST)
  @queries = queries
  @updates = updates
  @data = data
  @indexes = @data[:costs].flat_map { |_, ic| ic.keys }.uniq
  @logger = Logging.logger['nose::search::problem']
  @status = nil
  @objective_type = objective

  setup_model
end

Instance Attribute Details

#data ⇒ Object (readonly)

Returns the value of attribute data.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def data
  @data
end

#index_vars ⇒ Object (readonly)

Returns the value of attribute index_vars.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def index_vars
  @index_vars
end

#indexes ⇒ Object (readonly)

Returns the value of attribute indexes.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def indexes
  @indexes
end

#model ⇒ Object (readonly)

Returns the value of attribute model.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def model
  @model
end

#objective_type ⇒ Object (readonly)

Returns the value of attribute objective_type.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def objective_type
  @objective_type
end

#objective_value ⇒ Object (readonly)

Returns the value of attribute objective_value.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def objective_value
  @objective_value
end

#queries ⇒ Object (readonly)

Returns the value of attribute queries.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def queries
  @queries
end

#query_vars ⇒ Object (readonly)

Returns the value of attribute query_vars.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def query_vars
  @query_vars
end

#status ⇒ Object (readonly)

Returns the value of attribute status.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def status
  @status
end

#updates ⇒ Object (readonly)

Returns the value of attribute updates.



29
30
31
 
# File 'lib/nose/search/problem.rb', line 29

def updates
  @updates
end

Instance Method Details

#result ⇒ Results

Return relevant data on the results of the ILP

Returns:



87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/nose/search/problem.rb', line 87

def result
  result = Results.new self, @data[:by_id_graph]
  result.enumerated_indexes = indexes
  result.indexes = selected_indexes

  # TODO: Update for indexes grouped by ID path
  result.total_size = selected_indexes.sum_by(&:size)
  result.total_cost = @objective_value

  result
end

#selected_indexes ⇒ Set<Index>

Return the selected indices

Returns:



76
77
78
79
80
81
82
83
 
# File 'lib/nose/search/problem.rb', line 76

def selected_indexes
  return if @status.nil?
  return @selected_indexes if @selected_indexes

  @selected_indexes = @index_vars.each_key.select do |index|
    @index_vars[index].value
  end.to_set
end

#solve(previous_type = nil) ⇒ void

This method returns an undefined value.

Run the solver and make the selected indexes available



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
 
# File 'lib/nose/search/problem.rb', line 47

def solve(previous_type = nil)
  return unless @status.nil?

  # Run the optimization
  @model.optimize
  @status = model.status
  fail NoSolutionException, @status if @status != :optimized

  # Store the objective value
  @objective_value = @obj_var.value

  if @objective_type != Objective::INDEXES && previous_type.nil?
    solve_next Objective::INDEXES
    return
  elsif !previous_type.nil? && previous_type != Objective::SPACE
    solve_next Objective::SPACE
    return
  elsif @objective_value.nil?
    @objective_value = @model.objective_value
  end

  @logger.debug do
    "Final objective value is #{@objective.inspect}" \
      " = #{@objective_value}"
  end
end

#total_cost ⇒ MIPPeR::LinExpr

Get the cost of all queries in the workload

Returns:

  • (MIPPeR::LinExpr) 


110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/nose/search/problem.rb', line 110

def total_cost
  cost = @queries.reduce(MIPPeR::LinExpr.new) do |expr, query|
    expr.add(@indexes.reduce(MIPPeR::LinExpr.new) do |subexpr, index|
      subexpr.add total_query_cost(@data[:costs][query][index],
                                   @query_vars[index][query],
                                   @sort_costs[query][index],
                                   @sort_vars[query][index])
    end)
  end

  cost = add_update_costs cost
  cost
end

#total_indexes ⇒ MIPPeR::LinExpr

The total number of indexes

Returns:

  • (MIPPeR::LinExpr) 


126
127
128
129
130
131
 
# File 'lib/nose/search/problem.rb', line 126

def total_indexes
  total = MIPPeR::LinExpr.new
  @index_vars.each_value { |var| total += var * 1.0 }

  total
end

#total_size ⇒ MIPPeR::LinExpr

Get the size of all indexes in the workload

Returns:

  • (MIPPeR::LinExpr) 


101
102
103
104
105
106
 
# File 'lib/nose/search/problem.rb', line 101

def total_size
  # TODO: Update for indexes grouped by ID path
  @indexes.map do |index|
    @index_vars[index] * (index.size * 1.0)
  end.reduce(&:+)
end