-
Notifications
You must be signed in to change notification settings - Fork 0
/
entities.html
332 lines (281 loc) · 16.6 KB
/
entities.html
1
2
3
4
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
40
41
42
43
44
45
46
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
73
74
75
76
77
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8" />
<title>Entities — OR-Testbed 1.0.2 documentation</title>
<link rel="stylesheet" href="_static/alabaster.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="_static/language_data.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="Solvers" href="solvers.html" />
<link rel="prev" title="Tutorial" href="tutorial.html" />
<link rel="stylesheet" href="_static/custom.css" type="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
</head><body>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="entities">
<span id="id1"></span><h1>Entities<a class="headerlink" href="#entities" title="Permalink to this headline">¶</a></h1>
<div class="section" id="instance">
<h2>Instance<a class="headerlink" href="#instance" title="Permalink to this headline">¶</a></h2>
<span class="target" id="module-or_testbed.entities.instance"><span id="entities-instance"></span></span><dl class="class">
<dt id="or_testbed.entities.instance.Instance">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.entities.instance.</code><code class="sig-name descname">Instance</code><span class="sig-paren">(</span><em class="sig-param">name</em>, <em class="sig-param">data=None</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.instance.Instance" title="Permalink to this definition">¶</a></dt>
<dd><p>Instance objects hold information for concrete problem instances, like the input data.
It also provides a basic loader from JSON coded input data.</p>
<dl class="method">
<dt id="or_testbed.entities.instance.Instance.data">
<em class="property">property </em><code class="sig-name descname">data</code><a class="headerlink" href="#or_testbed.entities.instance.Instance.data" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Basic getter for instance input data</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>Instance input data, its concrete structure is up to the developer.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.instance.Instance.from_file">
<code class="sig-name descname">from_file</code><span class="sig-paren">(</span><em class="sig-param">path</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.instance.Instance.from_file" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Basic data loader. It loads a json file and stores it in self.data attribute. For more complex loadings, overriding this method is recommended.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>path</strong> – Path of the JSON file</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.instance.Instance.name">
<em class="property">property </em><code class="sig-name descname">name</code><a class="headerlink" href="#or_testbed.entities.instance.Instance.name" title="Permalink to this definition">¶</a></dt>
<dd><p>Basic getter for instance name</p>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>Instance name</p>
</dd>
</dl>
</dd></dl>
</dd></dl>
</div>
<div class="section" id="solution">
<h2>Solution<a class="headerlink" href="#solution" title="Permalink to this headline">¶</a></h2>
<span class="target" id="module-or_testbed.entities.solution"><span id="entities-solution"></span></span><dl class="class">
<dt id="or_testbed.entities.solution.Solution">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.entities.solution.</code><code class="sig-name descname">Solution</code><span class="sig-paren">(</span><em class="sig-param">objective=0</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution" title="Permalink to this definition">¶</a></dt>
<dd><p>Solution objects store the proper solution structure of the problem being solved. Also, some logic is implemented, like checking if the solution
is feasible and calculating the objective value (usually the cost function).</p>
<p>Two solutions can be compared in terms of their objective values with compare_to method.</p>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.calculate_objective">
<em class="property">abstract </em><code class="sig-name descname">calculate_objective</code><span class="sig-paren">(</span><em class="sig-param">in_instance</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.calculate_objective" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Calculates the objective value of a solution (usually a cost function), developer must override this method so it can fit the problem.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>in_instance</strong> – Problem instance with useful information.</p>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>Objective value.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.compare_to">
<code class="sig-name descname">compare_to</code><span class="sig-paren">(</span><em class="sig-param">in_solution</em>, <em class="sig-param">sense='MIN'</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.compare_to" title="Permalink to this definition">¶</a></dt>
<dd><p>Compares two solutions based on their objective values. This basic comparison supposes that the objective is a numeric value and a MINIMIZE type function.
This method should be overriden if the objective is more complex than a single numeric value.</p>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><ul class="simple">
<li><p><strong>in_solution</strong> – Another solution to compare with self one.</p></li>
<li><p><strong>sense</strong> – Indicates if we want to minimize (MIN) or maximize (MAX) the objective function.</p></li>
</ul>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>Positive number if ‘self’ solution is better (less cost if MIN, greater cost if MAX). Negative number is ‘self’ solution is worse (greater cost if MIN, less cost if MAX). Zero if both solutions are equal (equal cost).</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.get_objective">
<code class="sig-name descname">get_objective</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.get_objective" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Simple getter for the objective value of the solution.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>Objective value</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.is_feasible">
<em class="property">abstract </em><code class="sig-name descname">is_feasible</code><span class="sig-paren">(</span><em class="sig-param">in_instance</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.is_feasible" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Checks if a solution is feasible or not, developer must override this method so it can fit the problem.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>in_instance</strong> – Problem instance with useful information.</p>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>True if solutino is feasible, False if it doesn’t.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.set_objective">
<code class="sig-name descname">set_objective</code><span class="sig-paren">(</span><em class="sig-param">in_objective</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.set_objective" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Simple setter for the objective value of the solution.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>in_objective</strong> – objective value.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.to_dict">
<code class="sig-name descname">to_dict</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.to_dict" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Tries to convert a solution to a dictionary. In case of complex solutions this method should be overriden.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>The solution structure as a python dict.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.entities.solution.Solution.to_json">
<code class="sig-name descname">to_json</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.solution.Solution.to_json" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Tries to convert a solution to a JSON string. In case of complex solutions this method should be overriden.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>The solution structure as a JSON string.</p>
</dd>
</dl>
</dd></dl>
</dd></dl>
</div>
<div class="section" id="candidate">
<h2>Candidate<a class="headerlink" href="#candidate" title="Permalink to this headline">¶</a></h2>
<span class="target" id="module-or_testbed.entities.candidate"><span id="entities-candidate"></span></span><p>Candidate implementation for OR-Testbed.</p>
<dl class="class">
<dt id="or_testbed.entities.candidate.Candidate">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.entities.candidate.</code><code class="sig-name descname">Candidate</code><a class="headerlink" href="#or_testbed.entities.candidate.Candidate" title="Permalink to this definition">¶</a></dt>
<dd><p>in OR-Testbed a candidate is used to model potential moves in trajectory solvers, such as simulated annealing or tabu search.
Concrete attributes of a candidate depend on the problem being solved.</p>
<dl class="method">
<dt id="or_testbed.entities.candidate.Candidate.fitness">
<em class="property">abstract </em><code class="sig-name descname">fitness</code><span class="sig-paren">(</span><em class="sig-param">solution</em>, <em class="sig-param">instance</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.entities.candidate.Candidate.fitness" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Fitness function of a candidate. Usually this means the improvement of selecting this candidate to the actual solution.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><ul class="simple">
<li><p><strong>solution</strong> – Actual solution that the candidate will modify.</p></li>
<li><p><strong>instance</strong> – Instance being solved, may be needed to check special requirements or data.</p></li>
</ul>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>Fitness of the candidate, usually a numeric value.</p>
</dd>
</dl>
</dd></dl>
</dd></dl>
</div>
<div class="section" id="neighborhood">
<h2>Neighborhood<a class="headerlink" href="#neighborhood" title="Permalink to this headline">¶</a></h2>
<span class="target" id="module-or_testbed.entities.neighborhood"><span id="entities-neighborhood"></span></span><p>This module implements utilities to deal with neighborhoods in OR-Testbed.</p>
<p>Usually, in terms of combinatorial optimization, given a solution <code class="docutils literal notranslate"><span class="pre">s</span></code>, a neighborhood of <code class="docutils literal notranslate"><span class="pre">s</span></code> is the set of solutions close to <code class="docutils literal notranslate"><span class="pre">s</span></code> (called candidates).
Two solutions <code class="docutils literal notranslate"><span class="pre">s</span></code> an <code class="docutils literal notranslate"><span class="pre">s'</span></code> are close if there’s a movement that, applied to <code class="docutils literal notranslate"><span class="pre">s</span></code>, gives <code class="docutils literal notranslate"><span class="pre">s'</span></code>. The movement itself depends on the problem, but examples are swapping cities
in TSP, removing or adding items in knapsack, etc.</p>
<dl class="simple">
<dt>When selecting a candidate of a neighborhood, multiple strategies may be used:</dt><dd><ul class="simple">
<li><p>Random. Just select one random candidate from neighborhood</p></li>
<li><p>First improving. Iterate through all candidates in neighborhood and select the first candidate that improves the actual solution.</p></li>
<li><p>Best. Get the best candidate in the neighborhood. Even though this one seems the optimal, it needs to compute the cost of every candidate, which may be a problem in large neighborhoods.</p></li>
<li><p>Aspiration Plus. Iterate through all candidates, selecting the one that gives the best result but assuring that a minimum of candidates will be examined.</p></li>
</ul>
</dd>
</dl>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h1 class="logo"><a href="index.html">OR-Testbed</a></h1>
<h3>Navigation</h3>
<ul>
<li class="toctree-l1"><a class="reference internal" href="install.html">Installation Guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="tutorial.html">Tutorial</a></li>
</ul>
<ul class="current">
<li class="toctree-l1 current"><a class="current reference internal" href="#">Entities</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#instance">Instance</a></li>
<li class="toctree-l2"><a class="reference internal" href="#solution">Solution</a></li>
<li class="toctree-l2"><a class="reference internal" href="#candidate">Candidate</a></li>
<li class="toctree-l2"><a class="reference internal" href="#neighborhood">Neighborhood</a></li>
</ul>
</li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="solvers.html">Solvers</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="logging.html">Logging</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="changelog.html">Change log</a></li>
</ul>
<div class="relations">
<h3>Related Topics</h3>
<ul>
<li><a href="index.html">Documentation overview</a><ul>
<li>Previous: <a href="tutorial.html" title="previous chapter">Tutorial</a></li>
<li>Next: <a href="solvers.html" title="next chapter">Solvers</a></li>
</ul></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©2019, Diego Noceda.
|
Powered by <a href="http://sphinx-doc.org/">Sphinx 2.2.0</a>
& <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.12</a>
|
<a href="_sources/entities.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>