Class: Gecode::Model

Inherits:
Object
  • Object
show all
Defined in:
lib/gecoder/interface/model.rb,
lib/gecoder/interface/branch.rb,
lib/gecoder/interface/search.rb,
lib/gecoder/interface/enum_wrapper.rb

Overview

Model is the base class that all models must inherit from.

Defined Under Namespace

Modules: Constants

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.constrain(home, best) ⇒ Object

Called by spaces when they want to constrain as part of BAB-search.



90
91
92
93
94
95
96
 
# File 'lib/gecoder/interface/search.rb', line 90

def constrain(home, best) #:nodoc:
  if @constrain_proc.nil?
    raise NotImplementedError, 'Constrain method not implemented.' 
  else
    @constrain_proc.call(home, best)
  end
end

.constrain_proc=(proc) ⇒ Object

Sets the proc that should be used to handle constrain requests.



85
86
87
 
# File 'lib/gecoder/interface/search.rb', line 85

def constrain_proc=(proc) #:nodoc:
  @constrain_proc = proc
end

Instance Method Details

#active_space ⇒ Object

Retrieves the currently used space. Calling this method is only allowed when sanctioned by the model beforehand, e.g. when the model asks a constraint to post itself. Otherwise an RuntimeError is raised.

The space returned by this method should never be stored, it should be rerequested from the model every time that it’s needed.



123
124
125
126
127
128
129
 
# File 'lib/gecoder/interface/model.rb', line 123

def active_space #:nodoc:
  unless @allow_space_access
    raise 'Space access is restricted and the permission to access the ' + 
      'space has not been given.'
  end
  selected_space
end

#add_constraint(constraint) ⇒ Object

Adds the specified constraint to the model. Returns the newly added constraint.



133
134
135
136
137
138
 
# File 'lib/gecoder/interface/model.rb', line 133

def add_constraint(constraint) #:nodoc:
  add_interaction do
    constraint.post
  end
  return constraint
end

#add_interaction(&block) ⇒ Object

Adds a block containing something that interacts with Gecode to a queue where it is potentially executed.



142
143
144
 
# File 'lib/gecoder/interface/model.rb', line 142

def add_interaction(&block) #:nodoc:
  gecode_interaction_queue << block
end

#allow_space_access(&block) ⇒ Object

Allows the model’s active space to be accessed while the block is executed. Don’t use this unless you know what you’re doing. Anything that the space is used for (such as bound variables) must be released before the block ends.

Returns the result of the block.



152
153
154
155
156
157
158
159
160
161
 
# File 'lib/gecoder/interface/model.rb', line 152

def allow_space_access(&block) #:nodoc:
  # We store the old value so that nested calls don't become a problem, i.e.
  # access is allowed as long as one call to this method is still on the 
  # stack.
  old = @allow_space_access
  @allow_space_access = true
  res = yield
  @allow_space_access = old
  return res
end

#bool_var ⇒ Object

Creates a new boolean variable.



42
43
44
45
 
# File 'lib/gecoder/interface/model.rb', line 42

def bool_var
  index = variable_creation_space.new_bool_vars.first
  FreeBoolVar.new(self, index)
end

#bool_var_array(count) ⇒ Object

Creates an array containing the specified number of boolean variables.



48
49
50
51
52
53
54
 
# File 'lib/gecoder/interface/model.rb', line 48

def bool_var_array(count)
  variables = []
  variable_creation_space.new_bool_vars(count).each do |index|
    variables << FreeBoolVar.new(self, index)
  end
  return wrap_enum(variables)
end

#bool_var_matrix(row_count, col_count) ⇒ Object

Creates a matrix containing the specified number rows and columns of boolean variables.



58
59
60
61
62
63
64
65
66
67
 
# File 'lib/gecoder/interface/model.rb', line 58

def bool_var_matrix(row_count, col_count)
  indices = variable_creation_space.new_bool_vars(row_count*col_count)
  rows = []
  row_count.times do |i|
    rows << indices[(i*col_count)...(i.succ*col_count)].map! do |index|
      FreeBoolVar.new(self, index)
    end
  end
  return wrap_enum(Util::EnumMatrix.rows(rows, false))
end

#branch_on(variables, options = {}) ⇒ Object

Specifies which variables that should be branched on. One can optionally also select which of the variables that should be used first with the :variable option and which value in that variable’s domain that should be used with the :value option. If nothing is specified then :variable uses :none and value uses :min.

The following values can be used with :variable for integer and boolean enums:

:none

The first unassigned variable.

:smallest_min

The one with the smallest minimum.

:largest_min

The one with the largest minimum.

:smallest_max

The one with the smallest maximum.

:largest_max

The one with the largest maximum.

:smallest_size

The one with the smallest size.

:largest_size

The one with the larges size.

:smallest_degree

The one with the smallest degree. The degree of a variable is defined as the number of dependant propagators. In case of ties, choose the variable with smallest domain.

:largest_degree

The one with the largest degree. The degree of a variable is defined as the number of dependant propagators. In case of ties, choose the variable with smallest domain.

:smallest_min_regret

The one with the smallest min-regret. The min-regret of a variable is the difference between the smallest and second-smallest value still in the domain.

:largest_min_regret

The one with the largest min-regret. The min-regret of a variable is the difference between the smallest and second-smallest value still in the domain.

:smallest_max_regret

The one with the smallest max-regret The max-regret of a variable is the difference between the largest and second-largest value still in the domain.

:largest_max_regret

The one with the largest max-regret. The max-regret of a variable is the difference between the largest and second-largest value still in the domain.

The following values can be used with :value for integer and boolean enums:

:min

Selects the smallest value.

:med

Select the median value.

:max

Selects the largest vale

:split_min

Selects the lower half of the domain.

:split_max

Selects the upper half of the domain.

The following values can be used with :variable for set enums:

:none

The first unassigned set.

:smallest_cardinality

The one with the smallest cardinality.

:largest_cardinality

The one with the largest cardinality.

:smallest_unknown

The one with the smallest number of unknown elements

:largest_unknown

The one with the largest number of unknown elements

The following values can be used with :value set enums: enums:

:min

Selects the smallest value in the unknown part of the set.

:max

Selects the largest value in the unknown part of the set.



64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/gecoder/interface/branch.rb', line 64

def branch_on(variables, options = {})
  if variables.respond_to? :to_int_var_array or 
      variables.respond_to? :to_bool_var_array
    add_branch(variables, options, Constants::BRANCH_INT_VAR_CONSTANTS, 
      Constants::BRANCH_INT_VALUE_CONSTANTS)
  elsif variables.respond_to? :to_set_var_array
    add_branch(variables, options, Constants::BRANCH_SET_VAR_CONSTANTS, 
      Constants::BRANCH_SET_VALUE_CONSTANTS)
  else
    raise TypeError, "Unknown type of variable enum #{variables.class}."
  end
end

#each_solution(&block) ⇒ Object

Yields each solution that the model has.



31
32
33
34
35
36
37
 
# File 'lib/gecoder/interface/search.rb', line 31

def each_solution(&block)
  dfs = dfs_engine
  while not (@active_space = dfs.next).nil?
    yield self
  end
  self.reset!
end

#int_var(domain = Gecode::Raw::Limits::Int::INT_MIN..Gecode::Raw::Limits::Int::INT_MAX) ⇒ Object

Creates a new integer variable with the specified domain. The domain can either be a range, a single element, or an enumeration of elements. If no domain is specified then the largest possible domain is used.



7
8
9
10
11
12
 
# File 'lib/gecoder/interface/model.rb', line 7

def int_var(domain = 
    Gecode::Raw::Limits::Int::INT_MIN..Gecode::Raw::Limits::Int::INT_MAX)
  enum = domain_enum(domain)
  index = variable_creation_space.new_int_vars(enum).first
  FreeIntVar.new(self, index)
end

#int_var_array(count, domain) ⇒ Object

Creates an array containing the specified number of integer variables with the specified domain. The domain can either be a range, a single element, or an enumeration of elements.



17
18
19
20
21
22
23
24
 
# File 'lib/gecoder/interface/model.rb', line 17

def int_var_array(count, domain)
  enum = domain_enum(domain)
  variables = []
  variable_creation_space.new_int_vars(enum, count).each do |index|
    variables << FreeIntVar.new(self, index)
  end
  return wrap_enum(variables)
end

#int_var_matrix(row_count, col_count, domain) ⇒ Object

Creates a matrix containing the specified number rows and columns of integer variables with the specified domain. The domain can either be a range, a single element, or an enumeration of elements.



29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/gecoder/interface/model.rb', line 29

def int_var_matrix(row_count, col_count, domain)
  enum = domain_enum(domain)
  indices = variable_creation_space.new_int_vars(enum, row_count*col_count)
  rows = []
  row_count.times do |i|
    rows << indices[(i*col_count)...(i.succ*col_count)].map! do |index|
      FreeIntVar.new(self, index)
    end
  end
  return wrap_enum(Util::EnumMatrix.rows(rows, false))
end

#optimize!(&block) ⇒ Object

Finds the optimal solution. Optimality is defined by the provided block which is given one parameter, a solution to the problem. The block should constrain the solution so that that only “better” solutions can be new solutions. For instance if one wants to optimize a variable named price (accessible from the model) to be as low as possible then one should write the following.

model.optimize! do |model, best_so_far|
  model.price.must < best_so_far.price.val
end

Returns nil if there is no solution.



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
 
# File 'lib/gecoder/interface/search.rb', line 51

def optimize!(&block)
  # Execute constraints.
  perform_queued_gecode_interactions

  # Set the method used for constrain calls by the BAB-search.
  Model.constrain_proc = lambda do |home_space, best_space|
    @active_space = best_space
    @variable_creation_space = home_space
    yield(self, self)
    @active_space = home_space
    @variable_creation_space = nil
    
    perform_queued_gecode_interactions
  end

  # Perform the search.
  result = Gecode::Raw::bab(selected_space, 
    Gecode::Raw::Search::Config::MINIMAL_DISTANCE, 
    Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE, 
    nil)
  
  # Reset the method used constrain calls and return the result.
  Model.constrain_proc = nil
  return nil if result.nil?
  
  # Refresh the solution.
  result.refresh
  refresh_variables
  @active_space = result
  return self
end

#reset! ⇒ Object

Returns to the original state, before any search was made (but propagation might have been performed). Returns the reset model.



15
16
17
18
 
# File 'lib/gecoder/interface/search.rb', line 15

def reset!
  @active_space = base_space
  return self
end

#set_var(glb_domain = [], lub_domain = Gecode::Raw::Limits::Set::INT_MIN..Gecode::Raw::Limits::Set::INT_MAX, cardinality_range = nil) ⇒ Object

Creates a set variable with the specified domain for greatest lower bound and least upper bound (specified as either a range or enum). If no bounds are specified then the empty set is used as greates lower bound and the universe as least upper bound. A range for the allowed cardinality of the set can also be specified, if none is specified, or nil is given, then the default range (anything) will be used. If only a single Fixnum is specified as cardinality_range then it’s used as lower bound.



76
77
78
79
80
81
82
83
84
 
# File 'lib/gecoder/interface/model.rb', line 76

def set_var(glb_domain = [], lub_domain = 
    Gecode::Raw::Limits::Set::INT_MIN..Gecode::Raw::Limits::Set::INT_MAX, 
    cardinality_range = nil)
  check_set_bounds(glb_domain, lub_domain)
  
  index = variable_creation_space.new_set_vars(glb_domain, lub_domain, 
    to_set_cardinality_range(cardinality_range)).first
  FreeSetVar.new(self, index)
end

#set_var_array(count, glb_domain, lub_domain, cardinality_range = nil) ⇒ Object

Creates an array containing the specified number of set variables. The parameters beyond count are the same as for #set_var .



88
89
90
91
92
93
94
95
96
97
 
# File 'lib/gecoder/interface/model.rb', line 88

def set_var_array(count, glb_domain, lub_domain, cardinality_range = nil)
  check_set_bounds(glb_domain, lub_domain)
  
  variables = []
  variable_creation_space.new_set_vars(glb_domain, lub_domain, 
      to_set_cardinality_range(cardinality_range), count).each do |index|
    variables << FreeSetVar.new(self, index)
  end
  return wrap_enum(variables)
end

#set_var_matrix(row_count, col_count, glb_domain, lub_domain, cardinality_range = nil) ⇒ Object

Creates a matrix containing the specified number of rows and columns filled with set variables. The parameters beyond row and column counts are the same as for #set_var .



102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/gecoder/interface/model.rb', line 102

def set_var_matrix(row_count, col_count, glb_domain, lub_domain, 
    cardinality_range = nil)
  check_set_bounds(glb_domain, lub_domain)
  
  indices = variable_creation_space.new_set_vars(glb_domain, lub_domain, 
    to_set_cardinality_range(cardinality_range), row_count*col_count)
  rows = []
  row_count.times do |i|
    rows << indices[(i*col_count)...(i.succ*col_count)].map! do |index|
      FreeSetVar.new(self, index)
    end
  end
  return wrap_enum(Util::EnumMatrix.rows(rows, false))
end

#solution(&block) ⇒ Object

Yields the first solution (if any) to the block. If no solution is found then the block is not used. Returns the result of the block (nil in case the block wasn’t run).



23
24
25
26
27
28
 
# File 'lib/gecoder/interface/search.rb', line 23

def solution(&block)
  solution = self.solve!
  res = yield solution unless solution.nil?
  self.reset!
  return res
end

#solve! ⇒ Object

Finds the first solution to the modelled problem and updates the variables to that solution. Returns the model if a solution was found, nil otherwise.



6
7
8
9
10
11
 
# File 'lib/gecoder/interface/search.rb', line 6

def solve!
  space = dfs_engine.next
  return nil if space.nil?
  @active_space = space
  return self
end

#track_variable(variable) ⇒ Object

Starts tracking a variable that depends on the space. All variables created should call this method for their respective models.



165
166
167
 
# File 'lib/gecoder/interface/model.rb', line 165

def track_variable(variable) #:nodoc:
  (@variables ||= []) << variable
end

#wrap_enum(enum) ⇒ Object

Wraps a custom enumerable so that constraints can be specified using it. The argument is altered and returned.



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
 
# File 'lib/gecoder/interface/enum_wrapper.rb', line 5

def wrap_enum(enum)
  unless enum.kind_of? Enumerable
    raise TypeError, 'Only enumerables can be wrapped.'
  end
  elements = enum.to_a
  if elements.empty?
    raise ArgumentError, 'Enumerable must not be empty.'
  end
  
  if elements.all?{ |var| var.kind_of? FreeIntVar }
    class <<enum
      include Gecode::IntEnumMethods
    end
  elsif elements.all?{ |var| var.kind_of? FreeBoolVar }
    class <<enum
      include Gecode::BoolEnumMethods
    end
  elsif elements.all?{ |var| var.kind_of? FreeSetVar }
    class <<enum
      include Gecode::SetEnumMethods
    end
  elsif elements.all?{ |var| var.kind_of? Fixnum }
    class <<enum
      include Gecode::FixnumEnumMethods
    end
  else
    raise TypeError, "Enumerable doesn't contain variables #{enum.inspect}."
  end
  
  enum.model = self
  return enum
end