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.

Instance Method Summary collapse

Instance Method Details

#active_space ⇒ Object

Retrieves the currently active space (the one which variables refer to).



76
77
78
 
# File 'lib/gecoder/interface/model.rb', line 76

def active_space
  @active_space ||= base_space
end

#add_constraint(constraint) ⇒ Object

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



87
88
89
90
 
# File 'lib/gecoder/interface/model.rb', line 87

def add_constraint(constraint)
  constraints << constraint
  return constraint
end

#base_space ⇒ Object

Retrieves the base from which searches are made.



81
82
83
 
# File 'lib/gecoder/interface/model.rb', line 81

def base_space
  @base_space ||= Gecode::Raw::Space.new
end

#bool_var(*domain_args) ⇒ Object

Creates a new boolean variable.



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

def bool_var(*domain_args)
  index = active_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.



54
55
56
57
58
59
60
 
# File 'lib/gecoder/interface/model.rb', line 54

def bool_var_array(count)
  variables = []
  active_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.



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

def bool_var_matrix(row_count, col_count)
  indices = active_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

: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

: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.



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/gecoder/interface/branch.rb', line 80

def branch_on(variables, options = {})
  # Extract optional arguments.
  var_strat = options.delete(:variable) || :none
  val_strat = options.delete(:value) || :min

  # Check that the options are correct.
  unless options.empty?
    raise ArgumentError, 'Unknown branching option given: ' + 
      options.keys.join(', ')
  end
  unless BRANCH_VAR_CONSTANTS.include? var_strat
    raise ArgumentError, "Unknown variable selection strategy: #{var_strat}"
  end
  unless BRANCH_VALUE_CONSTANTS.include? val_strat
    raise ArgumentError, "Unknown value selection strategy: #{val_strat}"
  end

  # Add the branching.
  Gecode::Raw.branch(active_space, variables.to_var_array, 
    BRANCH_VAR_CONSTANTS[var_strat], BRANCH_VALUE_CONSTANTS[val_strat])
end

#each_solution(&block) ⇒ Object

Yields each solution that the model has.



39
40
41
42
43
44
45
 
# File 'lib/gecoder/interface/search.rb', line 39

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

#int_var(*domain_args) ⇒ Object

Creates a new integer variable with the specified domain. The domain can either be a range or a number of elements.



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

def int_var(*domain_args)
  range = domain_range(*domain_args)
  index = active_space.new_int_vars(range.begin, range.end).first
  construct_int_var(index, *domain_args)
end

#int_var_array(count, *domain_args) ⇒ Object

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



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

def int_var_array(count, *domain_args)
  # TODO: Maybe the custom domain should be specified as an array instead? 
  
  range = domain_range(*domain_args)
  variables = []
  active_space.new_int_vars(range.begin, range.end, count).each do |index|
    variables << construct_int_var(index, *domain_args)
  end
  return wrap_enum(variables)
end

#int_var_matrix(row_count, col_count, *domain_args) ⇒ 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 or a number of elements.



32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/gecoder/interface/model.rb', line 32

def int_var_matrix(row_count, col_count, *domain_args)
  # TODO: Maybe the custom domain should be specified as an array instead? 
  
  range = domain_range(*domain_args)
  indices = active_space.new_int_vars(range.begin, range.end, 
    row_count*col_count)
  rows = []
  row_count.times do |i|
    rows << indices[(i*col_count)...(i.succ*col_count)].map! do |index|
      construct_int_var(index, *domain_args)
    end
  end
  return wrap_enum(Util::EnumMatrix.rows(rows, false))
end

#reset! ⇒ Object

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



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

def reset!
  @active_space = base_space
  return self
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).



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

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.



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

def solve!
  space = dfs_engine.next
  return nil if space.nil?
  @active_space = space
  return self
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
 
# 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.map{ |var| var.kind_of? FreeIntVar }.all?
    class <<enum
      include Gecode::IntEnumMethods
    end
  elsif elements.map{ |var| var.kind_of? FreeBoolVar }.all?
    class <<enum
      include Gecode::BoolEnumMethods
    end
  elsif elements.map{ |var| var.kind_of? Fixnum }.all?
    class <<enum
      include Gecode::FixnumEnumMethods
    end
  else
    raise TypeError, "Enumerable doesn't contain variables #{enum.inspect}."
  end
  
  enum.model = self
  return enum
end