Name | Total Lines | Lines of Code | Total Coverage | Code Coverage |
---|---|---|---|---|
lib/gecoder/interface/search.rb | 229 | 131 | 100.00%
|
100.00%
|
Code reported as executed by Ruby looks like this...and this: this line is also marked as covered.Lines considered as run by rcov, but not reported by Ruby, look like this,and this: these lines were inferred by rcov (using simple heuristics).Finally, here's a line marked as not executed.
1 module Gecode |
2 # An exception raised when a search failed because there are no |
3 # solutions. |
4 class NoSolutionError < RuntimeError |
5 def initialize #:nodoc: |
6 super('No solution could be found.') |
7 end |
8 end |
9 |
10 # An exception raised when a search has been aborted due to e.g. |
11 # hitting the time limit specified when initiating the search. |
12 class SearchAbortedError < RuntimeError |
13 def initialize #:nodoc: |
14 super('The search was aborted before a solution could be found.') |
15 end |
16 end |
17 |
18 module Mixin |
19 # Finds the first solution to the modelled problem and updates the variables |
20 # to that solution. The found solution is also returned. Raises |
21 # Gecode::NoSolutionError if no solution can be found. |
22 # |
23 # The following options can be specified in a hash with symbols as |
24 # keys when calling the method: |
25 # |
26 # [:time_limit] The number of milliseconds that the solver should be |
27 # allowed to use when searching for a solution. If it can |
28 # not find a solution fast enough, then |
29 # Gecode::SearchAbortedError is raised. |
30 def solve!(options = {}) |
31 dfs = dfs_engine(options) |
32 space = dfs.next |
33 @gecoder_mixin_statistics = dfs.statistics |
34 raise Gecode::SearchAbortedError if dfs.stopped |
35 raise Gecode::NoSolutionError if space.nil? |
36 self.active_space = space |
37 return self |
38 end |
39 |
40 # Returns to the original state, before any search was made (but |
41 # propagation might have been performed). Returns the reset model. |
42 def reset! |
43 self.active_space = base_space |
44 @gecoder_mixin_statistics = nil |
45 return self |
46 end |
47 |
48 # Yields the first solution (if any) to the block. If no solution is found |
49 # then the block is not used. Returns the result of the block (nil in case |
50 # the block wasn't run). |
51 def solution(&block) |
52 begin |
53 solution = self.solve! |
54 res = yield solution |
55 self.reset! |
56 return res |
57 rescue Gecode::NoSolutionError |
58 return nil |
59 end |
60 end |
61 |
62 # Yields each solution that the model has. |
63 def each_solution(&block) |
64 dfs = dfs_engine |
65 next_solution = nil |
66 while not (next_solution = dfs.next).nil? |
67 self.active_space = next_solution |
68 @gecoder_mixin_statistics = dfs.statistics |
69 yield self |
70 end |
71 self.reset! |
72 end |
73 |
74 # Returns search statistics providing various information from Gecode about |
75 # the search that resulted in the model's current variable state. If the |
76 # model's variables have not undergone any search then nil is returned. The |
77 # statistics is a hash with the following keys: |
78 # [:propagations] The number of propagation steps performed. |
79 # [:failures] The number of failed nodes in the search tree. |
80 # [:clones] The number of clones created. |
81 # [:commits] The number of commit operations performed. |
82 # [:memory] The peak memory allocated to Gecode. |
83 def search_stats |
84 return nil if @gecoder_mixin_statistics.nil? |
85 |
86 return { |
87 :propagations => @gecoder_mixin_statistics.propagate, |
88 :failures => @gecoder_mixin_statistics.fail, |
89 :clones => @gecoder_mixin_statistics.clone, |
90 :commits => @gecoder_mixin_statistics.commit, |
91 :memory => @gecoder_mixin_statistics.memory |
92 } |
93 end |
94 |
95 # Finds the optimal solution. Optimality is defined by the provided |
96 # block which is given two parameters, the model and the best |
97 # solution found so far to the problem. The block should constrain |
98 # the model so that that only "better" solutions can be new |
99 # solutions. For instance if one wants to optimize a variable named |
100 # price (accessible from the model) to be as low as possible then |
101 # one should write the following. |
102 # |
103 # model.optimize! do |model, best_so_far| |
104 # model.price.must < best_so_far.price.value |
105 # end |
106 # |
107 # Raises Gecode::NoSolutionError if no solution can be found. |
108 def optimize!(&block) |
109 # Execute constraints. |
110 perform_queued_gecode_interactions |
111 |
112 # Set the method used for constrain calls by the BAB-search. |
113 Mixin.constrain_proc = lambda do |home_space, best_space| |
114 self.active_space = best_space |
115 @gecoder_mixin_variable_creation_space = home_space |
116 yield(self, self) |
117 self.active_space = home_space |
118 @gecoder_mixin_variable_creation_space = nil |
119 |
120 perform_queued_gecode_interactions |
121 end |
122 |
123 # Perform the search. |
124 options = Gecode::Raw::Search::Options.new |
125 options.c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE |
126 options.a_d = Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE |
127 options.stop = nil |
128 bab = Gecode::Raw::BAB.new(selected_space, options) |
129 |
130 result = nil |
131 previous_solution = nil |
132 until (previous_solution = bab.next).nil? |
133 result = previous_solution |
134 end |
135 @gecoder_mixin_statistics = bab.statistics |
136 |
137 # Reset the method used constrain calls and return the result. |
138 Mixin.constrain_proc = nil |
139 raise Gecode::NoSolutionError if result.nil? |
140 |
141 # Switch to the result. |
142 self.active_space = result |
143 return self |
144 end |
145 |
146 # Finds the solution that maximizes a given integer variable. The name of |
147 # the method that accesses the variable from the model should be given. To |
148 # for instance maximize a variable named "profit", that's accessible |
149 # through the model, one would use the following. |
150 # |
151 # model.maximize! :profit |
152 # |
153 # Raises Gecode::NoSolutionError if no solution can be found. |
154 def maximize!(var) |
155 variable = self.method(var).call |
156 unless variable.kind_of? Gecode::IntVar |
157 raise ArgumentError.new("Expected integer variable, got #{variable.class}.") |
158 end |
159 |
160 optimize! do |model, best_so_far| |
161 model.method(var).call.must > best_so_far.method(var).call.value |
162 end |
163 end |
164 |
165 # Finds the solution that minimizes a given integer variable. The name of |
166 # the method that accesses the variable from the model should be given. To |
167 # for instance minimize a variable named "cost", that's accessible through |
168 # the model, one would use the following. |
169 # |
170 # model.minimize! :cost |
171 # |
172 # Raises Gecode::NoSolutionError if no solution can be found. |
173 def minimize!(var) |
174 variable = self.method(var).call |
175 unless variable.kind_of? Gecode::IntVar |
176 raise ArgumentError.new("Expected integer variable, got #{variable.class}.") |
177 end |
178 |
179 optimize! do |model, best_so_far| |
180 model.method(var).call.must < best_so_far.method(var).call.value |
181 end |
182 end |
183 |
184 class <<self |
185 # Sets the proc that should be used to handle constrain requests. |
186 def constrain_proc=(proc) #:nodoc: |
187 @constrain_proc = proc |
188 end |
189 |
190 # Called by spaces when they want to constrain as part of BAB-search. |
191 def constrain(home, best) #:nodoc: |
192 if @constrain_proc.nil? |
193 raise NotImplementedError, 'Constrain method not implemented.' |
194 else |
195 @constrain_proc.call(home, best) |
196 end |
197 end |
198 end |
199 |
200 private |
201 |
202 # Creates a depth first search engine for search, executing any |
203 # unexecuted constraints first. |
204 def dfs_engine(options = {}) |
205 # Execute constraints. |
206 perform_queued_gecode_interactions |
207 |
208 # Begin constructing the option struct. |
209 opt_struct = Gecode::Raw::Search::Options.new |
210 opt_struct.c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE |
211 opt_struct.a_d = Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE |
212 |
213 # Decode the options. |
214 if options.has_key? :time_limit |
215 opt_struct.stop = Gecode::Raw::Search::Stop.new(-1, options.delete(:time_limit), -1) |
216 else |
217 opt_struct.stop = nil |
218 end |
219 |
220 unless options.empty? |
221 raise ArgumentError, 'Unrecognized search option: ' + |
222 options.keys.first.to_s |
223 end |
224 |
225 # Construct the engine. |
226 Gecode::Raw::DFS.new(selected_space, opt_struct) |
227 end |
228 end |
229 end |
Generated on Thu Jan 08 13:27:03 +0100 2015 with rcov 1.0.0