-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsolvers.html
294 lines (245 loc) · 18.7 KB
/
solvers.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8" />
<title>Solvers — 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="Logging" href="logging.html" />
<link rel="prev" title="Entities" href="entities.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="solvers">
<span id="id1"></span><h1>Solvers<a class="headerlink" href="#solvers" title="Permalink to this headline">¶</a></h1>
<div class="section" id="base-solvers">
<h2>Base Solvers<a class="headerlink" href="#base-solvers" title="Permalink to this headline">¶</a></h2>
<span class="target" id="id2"></span><dl class="class">
<dt id="or_testbed.solvers.base.solver.Solver">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.base.solver.</code><code class="sig-name descname">Solver</code><span class="sig-paren">(</span><em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.base.solver.Solver" title="Permalink to this definition">¶</a></dt>
<dd><p>Base solver class.</p>
<p>Every solver in OR-Testbed extends this class. What is important is that it implements the <code class="docutils literal notranslate"><span class="pre">solve</span></code> method, which actually runs the solver.</p>
<p>To add new solvers, <code class="docutils literal notranslate"><span class="pre">optimize</span></code> method must be overriden, there’s where all the solver logic lives.</p>
</dd></dl>
<dl class="class">
<dt id="or_testbed.solvers.base.solver.MultiStartSolver">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.base.solver.</code><code class="sig-name descname">MultiStartSolver</code><span class="sig-paren">(</span><em class="sig-param">iters</em>, <em class="sig-param">inner_solver_factory</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.base.solver.MultiStartSolver" title="Permalink to this definition">¶</a></dt>
<dd><p>Base multistart solver class.</p>
<p>Every multistart solver in OR-Testbed extend this class, but just for commodity purposes, since this class works just fine by itself.</p>
<p>It just executes a solver any given amount of times (<code class="docutils literal notranslate"><span class="pre">iters</span></code> parameter) and returns the best result achieved.</p>
</dd></dl>
</div>
<div class="section" id="grasp">
<h2>GRASP<a class="headerlink" href="#grasp" title="Permalink to this headline">¶</a></h2>
<span class="target" id="grasp-solver"></span><dl class="class">
<dt id="or_testbed.solvers.grasp.GraspConstruct">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.grasp.</code><code class="sig-name descname">GraspConstruct</code><span class="sig-paren">(</span><em class="sig-param">instance</em>, <em class="sig-param">solution_factory</em>, <em class="sig-param">grasp_move</em>, <em class="sig-param">alpha</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.grasp.GraspConstruct" title="Permalink to this definition">¶</a></dt>
<dd><p>GRASP constructive version.</p>
<p>This class implements GRASP with parameter alpha, which handles the randomness related to the space exploration.</p>
<p>To construct a solution, what it does is basically 4 steps:</p>
<ol class="arabic simple">
<li><p>Defines candidates to add to the solution.</p></li>
<li><p>Applies a greedy function to each candidate to calculate the incurring cost of adding that candidate to the solution.</p></li>
<li><p>Ranks candidates according to this cost.</p></li>
<li><p>Filters candidates depending on their costs, depending on alpha parameter, this creates the Restricted Candidates List (RCL)</p></li>
<li><p>Adds one random candidate to the solution.</p></li>
</ol>
<p>The core of the algorithm is implemented in this class, see <code class="docutils literal notranslate"><span class="pre">optimize</span></code> method.
The developer needs to override the methods that handle the candidates and the greedy function, as that is what is needed to adapt GRASP to any problem.</p>
<p>Check examples folder to see how to define and interact with GRASP.</p>
<dl class="method">
<dt id="or_testbed.solvers.grasp.GraspConstruct._filter_candidate_list">
<code class="sig-name descname">_filter_candidate_list</code><span class="sig-paren">(</span><em class="sig-param">candidates</em>, <em class="sig-param">costs</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.grasp.GraspConstruct._filter_candidate_list" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>This method takes a candidates list and their related costs based on a greedy function, then it filters those candidates whose associated cost fits the following expression:</p>
<p><code class="docutils literal notranslate"><span class="pre">c_min</span> <span class="pre"><=</span> <span class="pre">c(e)</span> <span class="pre"><=</span> <span class="pre">c_min</span> <span class="pre">+</span> <span class="pre">alpha*(c_max</span> <span class="pre">-</span> <span class="pre">c_min)</span></code></p>
<dl class="simple">
<dt>Where:</dt><dd><ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">c(e)</span></code> is the cost of candidate <code class="docutils literal notranslate"><span class="pre">e</span></code></p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">c_min</span></code> is the minimum cost of all candidates</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">c_max</span></code> is the maximum cost of all candidates</p></li>
</ul>
</dd>
</dl>
<p>This means that when parameter alpha is 0, a pure greedy approach is followed, only taking into account those candidates with minimum cost. On the other hand, if alpha is 1, then a pure random approach is followed, taking into account all candidates. Optimal value usually is somewhere in between.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><ul class="simple">
<li><p><strong>candidates</strong> – List of candidates to filter.</p></li>
<li><p><strong>costs</strong> – List of costs associated with each candidate.</p></li>
</ul>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>Filtered list of candidates depending of their cost.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.solvers.grasp.GraspConstruct._make_rcl">
<code class="sig-name descname">_make_rcl</code><span class="sig-paren">(</span><em class="sig-param">candidates</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.grasp.GraspConstruct._make_rcl" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>This method creates the Restricted Candidates List (RCL). It gets all the candidates, calculate thier costs and filter them according to parameter alpha.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>Calculated RCL</p>
</dd>
</dl>
</dd></dl>
</dd></dl>
<dl class="class">
<dt id="or_testbed.solvers.grasp.MultiStartGraspConstruct">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.grasp.</code><code class="sig-name descname">MultiStartGraspConstruct</code><span class="sig-paren">(</span><em class="sig-param">iters</em>, <em class="sig-param">inner_grasp_factory</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.grasp.MultiStartGraspConstruct" title="Permalink to this definition">¶</a></dt>
<dd><p>MultiStart version of GRASP constructive.</p>
<p>This is just an extension of base multistart solver. It works fine out of the box.</p>
</dd></dl>
</div>
<div class="section" id="simulated-annealing">
<h2>Simulated Annealing<a class="headerlink" href="#simulated-annealing" title="Permalink to this headline">¶</a></h2>
<span class="target" id="simanneal-solver"></span><dl class="class">
<dt id="or_testbed.solvers.simanneal.SimAnneal">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.simanneal.</code><code class="sig-name descname">SimAnneal</code><span class="sig-paren">(</span><em class="sig-param">instance</em>, <em class="sig-param">initial_solution</em>, <em class="sig-param">available_movs</em>, <em class="sig-param">movs_weight</em>, <em class="sig-param">max_temp</em>, <em class="sig-param">min_temp</em>, <em class="sig-param">alpha</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.simanneal.SimAnneal" title="Permalink to this definition">¶</a></dt>
<dd><p>Simulated Annealing implementation.</p>
<p>Based on Kirkpatricks work, this solver takes an initial solution and tries to improve it. It cannot create a new solution.</p>
<p>Basically, simulated annealing uses an inspiration between the annealing process in metals and some topics in combinatorial optimization.
The algorithm defines the space solution in terms of a neighborhood, and explores solutions modifying small parts of a solution.
Then, the new solution is compared to the last one, if it is an improvement, new solution is accepted. If not, it’s discarded.</p>
<p>However, to avoid getting stuck in local optimal solutions, some worse solutions may be accepted (this is were the cooling parameter of the algorithm sets the probability of accepting a worse movement).</p>
<p>In this algorithm, the developer needs to implement his own set of movements, everything else of the logic of the algorithm is already implemented.</p>
<p>Check examples folder to see how to define and interact with simulated annealing.</p>
<dl class="method">
<dt id="or_testbed.solvers.simanneal.SimAnneal._make_move">
<code class="sig-name descname">_make_move</code><span class="sig-paren">(</span><em class="sig-param">next_mov</em>, <em class="sig-param">candidate</em>, <em class="sig-param">in_solution</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.simanneal.SimAnneal._make_move" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Executes a certain move, thus calculating a new neighbour 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>next_mov</strong> – A movement factory that the algorithm instantiates and executes.</p></li>
<li><p><strong>in_solution</strong> – The solution to make the move to and calculate a new neighbor.</p></li>
</ul>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><p>The new neighbor solution.</p>
</dd>
</dl>
</dd></dl>
<dl class="method">
<dt id="or_testbed.solvers.simanneal.SimAnneal._select_movement">
<code class="sig-name descname">_select_movement</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.simanneal.SimAnneal._select_movement" title="Permalink to this definition">¶</a></dt>
<dd><blockquote>
<div><p>Selects a new movement of the defined set, taking into account the weight of each movement.</p>
</div></blockquote>
<dl class="field-list simple">
<dt class="field-odd">Returns</dt>
<dd class="field-odd"><p>A movement to be made.</p>
</dd>
</dl>
</dd></dl>
</dd></dl>
<dl class="class">
<dt id="or_testbed.solvers.simanneal.MultiStartSimAnneal">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.simanneal.</code><code class="sig-name descname">MultiStartSimAnneal</code><span class="sig-paren">(</span><em class="sig-param">iters</em>, <em class="sig-param">inner_simanneal_factory</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.simanneal.MultiStartSimAnneal" title="Permalink to this definition">¶</a></dt>
<dd><p>MultiStart version of Simulated Annealing.</p>
<p>This is just an extension of base multistart solver. It works fine out of the box.</p>
</dd></dl>
</div>
<div class="section" id="tabu-search">
<h2>Tabu Search<a class="headerlink" href="#tabu-search" title="Permalink to this headline">¶</a></h2>
<span class="target" id="id3"></span><dl class="class">
<dt id="or_testbed.solvers.tabusearch.TabuSearch">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.tabusearch.</code><code class="sig-name descname">TabuSearch</code><span class="sig-paren">(</span><em class="sig-param">instance</em>, <em class="sig-param">initial_solution</em>, <em class="sig-param">available_movs</em>, <em class="sig-param">movs_weight</em>, <em class="sig-param">tabulen=10</em>, <em class="sig-param">iters=10</em>, <em class="sig-param">candidate_selection='first'</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em>, <em class="sig-param">log_level=<LogLevel.ALL: 4></em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.tabusearch.TabuSearch" title="Permalink to this definition">¶</a></dt>
<dd><p>Tabu Search (TS) implementation.</p>
<p>Based on Glover work, this solver takes an initial solution and tries to improve it. It cannot create a new solution.</p>
<p>Basically, tabu search explores the solution space the same way as other trajectory solvers. It defines the space solution in terms of a neighborhood,
and explores modifying small parts of a solution.</p>
<p>The main feature of TS is that, in order to avoid getting stuck, it uses a list where recent neighbors are stored, so it does not run in circles over the same
solutions over and over again.</p>
<p>When a candidate is accepted, it is added to the tabu list, sometimes, if no good solution is found, a bad solution can be taken to continue the exploration.
When the tabu list is full, elements get discarded in favor of new ones.</p>
<p>Check examples folder to see how to define and interact with tabu search.</p>
</dd></dl>
<dl class="class">
<dt id="or_testbed.solvers.tabusearch.MultiStartTabuSearch">
<em class="property">class </em><code class="sig-prename descclassname">or_testbed.solvers.tabusearch.</code><code class="sig-name descname">MultiStartTabuSearch</code><span class="sig-paren">(</span><em class="sig-param">iters</em>, <em class="sig-param">inner_tabusearch_factory</em>, <em class="sig-param">debug=True</em>, <em class="sig-param">log_file=None</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.tabusearch.MultiStartTabuSearch" title="Permalink to this definition">¶</a></dt>
<dd><p>MultiStart version of Tabu Search.</p>
<p>This is just an extension of base multistart solver. It works fine out of the box.</p>
</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>
<li class="toctree-l1"><a class="reference internal" href="entities.html">Entities</a></li>
</ul>
<ul class="current">
<li class="toctree-l1 current"><a class="current reference internal" href="#">Solvers</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#base-solvers">Base Solvers</a></li>
<li class="toctree-l2"><a class="reference internal" href="#grasp">GRASP</a></li>
<li class="toctree-l2"><a class="reference internal" href="#simulated-annealing">Simulated Annealing</a></li>
<li class="toctree-l2"><a class="reference internal" href="#tabu-search">Tabu Search</a></li>
</ul>
</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="entities.html" title="previous chapter">Entities</a></li>
<li>Next: <a href="logging.html" title="next chapter">Logging</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/solvers.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>