Class: Gecode::Model
- Inherits:
-
Object
- Object
- Gecode::Model
- 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
Constant Summary collapse
- MAX_INT =
The largest integer allowed in the domain of an integer variable.
Gecode::Raw::IntLimits::MAX
- MIN_INT =
The smallest integer allowed in the domain of an integer variable.
Gecode::Raw::IntLimits::MIN
- SET_MAX_INT =
The largest integer allowed in the domain of a set variable.
Gecode::Raw::SetLimits::MAX
- SET_MIN_INT =
The smallest integer allowed in the domain of a set variable.
Gecode::Raw::SetLimits::MIN
- LARGEST_INT_DOMAIN =
The largest possible domain for an integer variable.
MIN_INT..MAX_INT
- NON_NEGATIVE_INT_DOMAIN =
The largest possible domain, without negative integers, for an integer variable.
0..MAX_INT
- LARGEST_SET_BOUND =
The largest possible bound for a set variable.
SET_MIN_INT..SET_MAX_INT
Class Method Summary collapse
-
.constrain(home, best) ⇒ Object
Called by spaces when they want to constrain as part of BAB-search.
-
.constrain_proc=(proc) ⇒ Object
Sets the proc that should be used to handle constrain requests.
Instance Method Summary collapse
-
#active_space ⇒ Object
Retrieves the currently used space.
-
#add_constraint(constraint) ⇒ Object
Adds the specified constraint to the model.
-
#add_interaction(&block) ⇒ Object
Adds a block containing something that interacts with Gecode to a queue where it is potentially executed.
-
#allow_space_access(&block) ⇒ Object
Allows the model’s active space to be accessed while the block is executed.
-
#bool_var ⇒ Object
Creates a new boolean variable.
-
#bool_var_array(count) ⇒ Object
Creates an array containing the specified number of boolean variables.
-
#bool_var_matrix(row_count, col_count) ⇒ Object
Creates a matrix containing the specified number rows and columns of boolean variables.
-
#branch_on(variables, options = {}) ⇒ Object
Specifies which variables that should be branched on (given as an enum of variables or as a single variable).
-
#each_solution(&block) ⇒ Object
Yields each solution that the model has.
-
#int_var(domain = LARGEST_INT_DOMAIN) ⇒ Object
Creates a new integer variable with the specified domain.
-
#int_var_array(count, domain = LARGEST_INT_DOMAIN) ⇒ Object
Creates an array containing the specified number of integer variables with the specified domain.
-
#int_var_matrix(row_count, col_count, domain = LARGEST_INT_DOMAIN) ⇒ Object
Creates a matrix containing the specified number rows and columns of integer variables with the specified domain.
-
#maximize!(var) ⇒ Object
Finds the solution that maximizes a given integer variable.
-
#minimize!(var) ⇒ Object
Finds the solution that minimizes a given integer variable.
-
#optimize!(&block) ⇒ Object
Finds the optimal solution.
-
#reset! ⇒ Object
Returns to the original state, before any search was made (but propagation might have been performed).
-
#search_stats ⇒ Object
Returns search statistics providing various information from Gecode about the search that resulted in the model’s current variable state.
-
#set_var(glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) ⇒ Object
Creates a set variable with the specified domain for greatest lower bound and least upper bound (specified as either a fixnum, range or enum).
-
#set_var_array(count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) ⇒ Object
Creates an array containing the specified number of set variables.
-
#set_var_matrix(row_count, col_count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) ⇒ Object
Creates a matrix containing the specified number of rows and columns filled with set variables.
-
#solution(&block) ⇒ Object
Yields the first solution (if any) to the block.
-
#solve! ⇒ Object
Finds the first solution to the modelled problem and updates the variables to that solution.
-
#track_variable(variable) ⇒ Object
Starts tracking a variable that depends on the space.
-
#wrap_enum(enum) ⇒ Object
Wraps a custom enumerable so that constraints can be specified using it.
Class Method Details
.constrain(home, best) ⇒ Object
Called by spaces when they want to constrain as part of BAB-search.
161 162 163 164 165 166 167 |
# File 'lib/gecoder/interface/search.rb', line 161 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.
156 157 158 |
# File 'lib/gecoder/interface/search.rb', line 156 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.
115 116 117 118 119 120 121 |
# File 'lib/gecoder/interface/model.rb', line 115 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.
125 126 127 128 129 130 |
# File 'lib/gecoder/interface/model.rb', line 125 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.
134 135 136 |
# File 'lib/gecoder/interface/model.rb', line 134 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.
144 145 146 147 148 149 150 151 152 153 |
# File 'lib/gecoder/interface/model.rb', line 144 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.
54 55 56 |
# File 'lib/gecoder/interface/model.rb', line 54 def bool_var FreeBoolVar.new(self, variable_creation_space.new_bool_var) end |
#bool_var_array(count) ⇒ Object
Creates an array containing the specified number of boolean variables.
59 60 61 62 63 |
# File 'lib/gecoder/interface/model.rb', line 59 def bool_var_array(count) build_var_array(count) do FreeBoolVar.new(self, variable_creation_space.new_bool_var) end end |
#bool_var_matrix(row_count, col_count) ⇒ Object
Creates a matrix containing the specified number rows and columns of boolean variables.
67 68 69 70 71 |
# File 'lib/gecoder/interface/model.rb', line 67 def bool_var_matrix(row_count, col_count) build_var_matrix(row_count, col_count) do FreeBoolVar.new(self, variable_creation_space.new_bool_var) end end |
#branch_on(variables, options = {}) ⇒ Object
Specifies which variables that should be branched on (given as an enum of variables or as a single variable). 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:
- :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 76 77 78 79 |
# File 'lib/gecoder/interface/branch.rb', line 64 def branch_on(variables, = {}) if variables.respond_to? :bind variables = wrap_enum [variables] end if variables.respond_to? :to_int_var_array or variables.respond_to? :to_bool_var_array add_branch(variables, , Constants::BRANCH_INT_VAR_CONSTANTS, Constants::BRANCH_INT_VALUE_CONSTANTS) elsif variables.respond_to? :to_set_var_array add_branch(variables, , 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.
34 35 36 37 38 39 40 41 42 43 |
# File 'lib/gecoder/interface/search.rb', line 34 def each_solution(&block) dfs = dfs_engine next_solution = nil while not (next_solution = dfs.next).nil? self.active_space = next_solution @statistics = dfs.statistics yield self end self.reset! end |
#int_var(domain = LARGEST_INT_DOMAIN) ⇒ 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.
26 27 28 29 |
# File 'lib/gecoder/interface/model.rb', line 26 def int_var(domain = LARGEST_INT_DOMAIN) args = domain_arguments(domain) FreeIntVar.new(self, variable_creation_space.new_int_var(*args)) end |
#int_var_array(count, domain = LARGEST_INT_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. If no domain is specified then the largest possible domain is used.
35 36 37 38 39 40 |
# File 'lib/gecoder/interface/model.rb', line 35 def int_var_array(count, domain = LARGEST_INT_DOMAIN) args = domain_arguments(domain) build_var_array(count) do FreeIntVar.new(self, variable_creation_space.new_int_var(*args)) end end |
#int_var_matrix(row_count, col_count, domain = LARGEST_INT_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. If no domain is specified then the largest possible domain is used.
46 47 48 49 50 51 |
# File 'lib/gecoder/interface/model.rb', line 46 def int_var_matrix(row_count, col_count, domain = LARGEST_INT_DOMAIN) args = domain_arguments(domain) build_var_matrix(row_count, col_count) do FreeIntVar.new(self, variable_creation_space.new_int_var(*args)) end end |
#maximize!(var) ⇒ Object
Finds the solution that maximizes a given integer variable. The name of the method that accesses the variable from the model should be given. To for instance maximize a variable named “profit”, that’s accessible through the model, one would use the following.
model.maximize! :profit
Returns nil if there is no solution.
124 125 126 127 128 129 130 131 132 133 |
# File 'lib/gecoder/interface/search.rb', line 124 def maximize!(var) variable = self.method(var).call unless variable.kind_of? Gecode::FreeIntVar raise ArgumentError.new("Expected integer variable, got #{variable.class}.") end optimize! do |model, best_so_far| model.method(var).call.must > best_so_far.method(var).call.value end end |
#minimize!(var) ⇒ Object
Finds the solution that minimizes a given integer variable. The name of the method that accesses the variable from the model should be given. To for instance minimize a variable named “cost”, that’s accessible through the model, one would use the following.
model.minimize! :cost
Returns nil if there is no solution.
143 144 145 146 147 148 149 150 151 152 |
# File 'lib/gecoder/interface/search.rb', line 143 def minimize!(var) variable = self.method(var).call unless variable.kind_of? Gecode::FreeIntVar raise ArgumentError.new("Expected integer variable, got #{variable.class}.") end optimize! do |model, best_so_far| model.method(var).call.must < best_so_far.method(var).call.value end 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.
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 |
# File 'lib/gecoder/interface/search.rb', line 78 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| self.active_space = best_space @variable_creation_space = home_space yield(self, self) self.active_space = home_space @variable_creation_space = nil perform_queued_gecode_interactions end # Perform the search. = Gecode::Raw::Search::Options.new .c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE .a_d = Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE .stop = nil bab = Gecode::Raw::BAB.new(selected_space, ) result = nil previous_solution = nil until (previous_solution = bab.next).nil? result = previous_solution end @statistics = bab.statistics # Reset the method used constrain calls and return the result. Model.constrain_proc = nil return nil if result.nil? # Switch to the result. self.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.
17 18 19 20 21 |
# File 'lib/gecoder/interface/search.rb', line 17 def reset! self.active_space = base_space @statistics = nil return self end |
#search_stats ⇒ Object
Returns search statistics providing various information from Gecode about the search that resulted in the model’s current variable state. If the model’s variables have not undegone any search then nil is returned. The statistics is a hash with the following keys:
- :propagations
-
The number of propagation steps performed.
- :failures
-
The number of failed nodes in the search tree.
- :clones
-
The number of clones created.
- :commits
-
The number of commit operations performed.
- :memory
-
The peak memory allocated to Gecode.
54 55 56 57 58 59 60 61 62 63 64 |
# File 'lib/gecoder/interface/search.rb', line 54 def search_stats return nil if @statistics.nil? return { :propagations => @statistics.propagate, :failures => @statistics.fail, :clones => @statistics.clone, :commits => @statistics.commit, :memory => @statistics.memory } end |
#set_var(glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) ⇒ Object
Creates a set variable with the specified domain for greatest lower bound and least upper bound (specified as either a fixnum, range or enum). If no bounds are specified then the empty set is used as greatest lower bound and the largest possible set 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.
82 83 84 85 86 |
# File 'lib/gecoder/interface/model.rb', line 82 def set_var(glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range) FreeSetVar.new(self, variable_creation_space.new_set_var(*args)) end |
#set_var_array(count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, 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 .
90 91 92 93 94 95 96 |
# File 'lib/gecoder/interface/model.rb', line 90 def set_var_array(count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range) build_var_array(count) do FreeSetVar.new(self, variable_creation_space.new_set_var(*args)) end end |
#set_var_matrix(row_count, col_count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, 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 .
101 102 103 104 105 106 107 |
# File 'lib/gecoder/interface/model.rb', line 101 def set_var_matrix(row_count, col_count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range) build_var_matrix(row_count, col_count) do FreeSetVar.new(self, variable_creation_space.new_set_var(*args)) end 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).
26 27 28 29 30 31 |
# File 'lib/gecoder/interface/search.rb', line 26 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 12 13 |
# File 'lib/gecoder/interface/search.rb', line 6 def solve! dfs = dfs_engine space = dfs.next @statistics = dfs.statistics return nil if space.nil? self.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.
157 158 159 |
# File 'lib/gecoder/interface/model.rb', line 157 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 37 38 39 |
# 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 if enum.kind_of? Gecode::EnumMethods raise ArgumentError, 'The enumration is already 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 |