-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathexamples.html
299 lines (252 loc) · 30.7 KB
/
examples.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8" />
<title>Examples — OR-Testbed 0.1.0 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="Entities" href="entities.html" />
<link rel="prev" title="Installation Guide" href="install.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="examples">
<span id="id1"></span><h1>Examples<a class="headerlink" href="#examples" title="Permalink to this headline">¶</a></h1>
<p>This section acts as a tutorial and it will present some insights about how to use an adapt OR-Testbed to solve our problems.</p>
<div class="section" id="traveling-salesman-problem-tsp">
<h2>Traveling Salesman Problem (TSP)<a class="headerlink" href="#traveling-salesman-problem-tsp" title="Permalink to this headline">¶</a></h2>
<div class="section" id="introduction">
<h3>Introduction<a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h3>
<p>TSP is one of the best known combinatorial optimization problems, so it will serve perfectly to explain how to use OR-Testbed.
To summarize, our salesman must visit a certain number of cities, he wants to minimize the cost associated with his whole trip and, of course, he only
wants to visit each city once. So this gives us a graph where each node represents a city and an edge between cities represents the distance
between them. We want to give our salesman a sequence of cities he must visit that finishes in the starting city and minimizes the distance he must travel.</p>
<p>Check some resources if you are unfamiliar with TSP:</p>
<ul class="simple">
<li><p><a class="reference external" href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia</a></p></li>
</ul>
<ul class="simple">
<li><p><a class="reference external" href="https://www.explainxkcd.com/wiki/index.php/399:_Travelling_Salesman_Problem">xkcd</a></p></li>
</ul>
<ul class="simple">
<li><p><a class="reference external" href="https://developers.google.com/optimization/routing/tsp">google OR-Tools</a></p></li>
</ul>
<ul class="simple">
<li><p><a class="reference external" href="http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html">TSPLIB</a></p></li>
</ul>
<p>We can start modeling TSP in OR-Testbed and solving it the best we can. All the code in this example is avaiable on
<a class="reference external" href="http://github.com/Fynardo/OR-Testbed/tree/master/examples/tsp">Github</a>.</p>
</div>
<div class="section" id="problem-definition">
<h3>Problem Definition<a class="headerlink" href="#problem-definition" title="Permalink to this headline">¶</a></h3>
<p>In OR-Testbed, three things are needed to solve a problem:</p>
<p>1. A <strong>Solution</strong>. Solution objects store the obtained solution for some problem, its internal structure depends on the problem itself,
but all solutions in OR-Testbed share share a value called <strong>objective</strong>, that representes the quality of the solution. In TSP this objective
is the cost of the calculated trip.</p>
<p>2. An <strong>Instance</strong>. Instance objects store input data and some logic, for example is their responsibility to know how to check the feasibility
of a solution and calculating its objective. In TSP, instances will have information about cities and distances.</p>
<p>3. A <strong>Solver</strong>. The solver is the one that does the work, this is, the algorithm itself. Each solver implements one metaheuristic or a variation of
a metaheuristic. In TSP, we will need to implement some methods of the solvers in order to adapt their logic to TSP.</p>
</div>
<div class="section" id="defining-a-solution">
<h3>Defining a solution<a class="headerlink" href="#defining-a-solution" title="Permalink to this headline">¶</a></h3>
<p>All solution objects extend from an abstract class defined in OR-Testbed called, as you may imagine, Solution. This class sets the objective to 0 and provides
the common getter and setter methods to interact with the objective. Also, it provides a basic <code class="docutils literal notranslate"><span class="pre">compare_to</span></code> function, that compares two solutions based
on their objectives. Check <a class="reference internal" href="entities.html#entities-solution"><span class="std std-ref">solution</span></a> docs for more information.</p>
<p>So, in order to make our solution for TSP, we must extend this class. We can import the solution abstract class in the usual way, for example:</p>
<p>Now, for TSP we want two things: starting city and the sequence of cities that our salesman is going to visit. The following code does just that.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">TSPSolution</span><span class="p">(</span><span class="n">base_solution</span><span class="o">.</span><span class="n">Solution</span><span class="p">):</span>
<span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">initial_city</span><span class="p">):</span>
<span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__init__</span><span class="p">()</span>
<span class="bp">self</span><span class="o">.</span><span class="n">initial_city</span> <span class="o">=</span> <span class="n">initial_city</span>
<span class="bp">self</span><span class="o">.</span><span class="n">cities</span> <span class="o">=</span> <span class="p">[</span><span class="n">initial_city</span><span class="p">]</span>
</pre></div>
</div>
<p>What has been done here is just initialize the solution (the sequence of cities to visit) with the starting city. Note that since there is no need
to update the objective right now.</p>
<p>Next step consists on loading the input data and implementing some logic.</p>
</div>
<div class="section" id="defining-an-instance">
<h3>Defining an instance<a class="headerlink" href="#defining-an-instance" title="Permalink to this headline">¶</a></h3>
<p>As with the solution object, the instance object also extends some abstract class called Instance. This class provides some methods, some of them regarding logic
of the problem, are abstract so we must override them. Other methods provide some general functionality, like data setters and getters and a basic JSON loader. Check
Check <a class="reference internal" href="entities.html#entities-instance"><span class="std std-ref">instance</span></a> docs for more information.</p>
<p>We have to implement two methods: <code class="docutils literal notranslate"><span class="pre">is_feasible</span></code> and <code class="docutils literal notranslate"><span class="pre">calculate_objective</span></code>. The first one is responsible of checking whether a solution is feasible or not, based on concrete
problem requirements. In TSP, we just need to assure that all cities are visited once. The second one calculates the objective, i.e., the cost of the trip. Which in this
case will be measured by an integer number (the sum of distances between cities) but could be as complex as needed.</p>
<p>Lets check the code, first we must import abstract instance class like in the solution case.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">or_testbed.entities.instance</span> <span class="kn">as</span> <span class="nn">base_instance</span>
</pre></div>
</div>
<p>Now, we are going to define the data related to our problem. Instance objects need two pieces of information: the <strong>name</strong> of the instance and the <strong>data</strong> related to it. The name is used to refer to some
concrete data, for example, in TSPLIB all instances have a name (<em>a280</em>, <em>brazil58</em>, <em>ch130</em>, etc) and that represents the number of cities and other information.</p>
<p>On the other hand we have instance data, this is the information about the cities, their distances, etc.
Lets code a small TSP example with 5 cities (named from ‘A’ to ‘E’):</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">instance_name</span> <span class="o">=</span> <span class="s1">'tsp_example'</span>
<span class="n">cities</span> <span class="o">=</span> <span class="p">{</span><span class="s1">'A'</span><span class="p">:</span> <span class="p">{</span><span class="s1">'B'</span><span class="p">:</span> <span class="mi">3</span><span class="p">,</span> <span class="s1">'C'</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="s1">'D'</span><span class="p">:</span> <span class="mi">6</span><span class="p">,</span> <span class="s1">'E'</span><span class="p">:</span> <span class="mi">2</span><span class="p">},</span> <span class="s1">'B'</span><span class="p">:</span> <span class="p">{</span><span class="s1">'A'</span><span class="p">:</span> <span class="mi">3</span><span class="p">,</span> <span class="s1">'C'</span><span class="p">:</span> <span class="mi">25</span><span class="p">,</span> <span class="s1">'D'</span><span class="p">:</span> <span class="mi">10</span><span class="p">,</span> <span class="s1">'E'</span><span class="p">:</span> <span class="mi">5</span><span class="p">},</span> <span class="s1">'C'</span><span class="p">:</span> <span class="p">{</span><span class="s1">'A'</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="s1">'B'</span><span class="p">:</span> <span class="mi">25</span><span class="p">,</span> <span class="s1">'D'</span><span class="p">:</span> <span class="mi">3</span><span class="p">,</span> <span class="s1">'E'</span><span class="p">:</span> <span class="mi">4</span><span class="p">},</span> <span class="s1">'D'</span><span class="p">:</span> <span class="p">{</span><span class="s1">'A'</span><span class="p">:</span> <span class="mi">6</span><span class="p">,</span> <span class="s1">'B'</span><span class="p">:</span> <span class="mi">10</span><span class="p">,</span> <span class="s1">'C'</span><span class="p">:</span> <span class="mi">3</span><span class="p">,</span> <span class="s1">'E'</span><span class="p">:</span> <span class="mi">1</span><span class="p">},</span> <span class="s1">'E'</span><span class="p">:</span> <span class="p">{</span><span class="s1">'A'</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="s1">'B'</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="s1">'C'</span><span class="p">:</span> <span class="mi">4</span><span class="p">,</span> <span class="s1">'D'</span><span class="p">:</span> <span class="mi">1</span><span class="p">}}</span>
</pre></div>
</div>
<p>As you can see, cities information are codified with a adjacency list using a python dict, this may not be an optimal approximation but its fine for an example. Now we can instantiate our TSPInstance class as follows:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">TSPInstance</span><span class="p">(</span><span class="n">base_instance</span><span class="o">.</span><span class="n">Instance</span><span class="p">):</span>
<span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">,</span> <span class="n">data</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__init__</span><span class="p">(</span><span class="n">name</span><span class="p">,</span> <span class="n">data</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">is_feasible</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">in_solution</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">set</span><span class="p">(</span><span class="n">in_solution</span><span class="o">.</span><span class="n">cities</span><span class="p">)</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span>
<span class="k">def</span> <span class="nf">calculate_objective</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">in_solution</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">sum</span><span class="p">([</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">b</span><span class="p">]</span> <span class="k">for</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">in_solution</span><span class="o">.</span><span class="n">cities</span><span class="p">,</span> <span class="n">in_solution</span><span class="o">.</span><span class="n">cities</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">:]</span> <span class="o">+</span> <span class="n">in_solution</span><span class="o">.</span><span class="n">cities</span><span class="p">[:</span><span class="o">-</span><span class="mi">1</span><span class="p">])])</span>
</pre></div>
</div>
<p>Note that we override methods <code class="docutils literal notranslate"><span class="pre">is_feasible</span></code> and <code class="docutils literal notranslate"><span class="pre">calculate_objective</span></code>, and that they both have access to some solution.
First, to check the feasibility we just want to check if all cities ( <code class="docutils literal notranslate"><span class="pre">self.data.keys()</span></code> ) are present in the solution ( <code class="docutils literal notranslate"><span class="pre">in_solution.cities</span></code> ).
Second, for the objective we want to sum all distances between the sequence of cities (and between last city and the starting one). That’s a pretty
hard to read oneliner, but what it just sums distances between the cities present in the solution object.</p>
<p>Note that these two methods are going to be called by the solvers when needed.</p>
</div>
<div class="section" id="solving-an-instance">
<h3>Solving an instance<a class="headerlink" href="#solving-an-instance" title="Permalink to this headline">¶</a></h3>
<p>The last step is to get a solver working and create a trip for our salesman. In this tutorial we are going to use <a class="reference internal" href="solvers.html#grasp-solver"><span class="std std-ref">GRASP</span></a> to generate
a solution. There is more solvers implemented in the examples folder in Github repository.</p>
<p><a class="reference external" href="https://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure">GRASP</a> is a very simple, yet very powerful, optimization algorithm.
To construct a solution, what it does is basically 4 steps:</p>
<ol class="arabic simple">
<li><p>Define candidates (in TSP, these candidates are cities to visit)</p></li>
<li><p>Applies a greedy function to each candidate (in TSP, this may be distance between last city and the remaining non visited ones)</p></li>
<li><p>Ranks candidates according to this greedy function value (in TSP, closer cities will rank better than farther ones)</p></li>
<li><p>Adds best candidate to the solution (in TSP, closest solution)</p></li>
</ol>
<p>The power of GRASP comes when some randomness is applied in steps 3 and 4, this lets the algorithm to explore new solution space, therefore, achieving better solutions.</p>
<p>OR-Testbed implements the core of GRASP, and manages randomness with the parameter <strong>alpha</strong> (a float value between 0 and 1). In step 3, when ranking candidates we can take into account only a subset
of al possible candidates, this is what alpha does with the following equation:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>c_min <= c(e) <= c_min + alpha*(c_max - c_min)
</pre></div>
</div>
<p>Where <strong>c(e)</strong> is the cost of candidate <strong>e</strong> (based on the greedy function), <strong>c_min</strong> and <strong>c_max</strong> are the minimum and maximum costs of the remaining candidates, respectively.</p>
<p>What this means is that when alpha is 0 only candidates with minimum cost are taken into account (pure greedy approach). On the other hand, when
alpha is 1 all candidates are taken into account (pure randomness approach). What alpha does is to set the confidence we have in our greedy function.</p>
<p>Anyhow, to solve a problem like TSP we must implement some logic (like the greedy function). Basically we need to override the methods
that are not part of the core of GRASP (this happens with every metaheuristic in OR-Testbed). In this case, we must override
<code class="docutils literal notranslate"><span class="pre">initialize_solution</span></code> (though if you don’t need to initialize anything you may pass), <code class="docutils literal notranslate"><span class="pre">greedy_function</span></code>, <code class="docutils literal notranslate"><span class="pre">make_candidates_list</span></code>,
<code class="docutils literal notranslate"><span class="pre">add_candidate</span></code> and <code class="docutils literal notranslate"><span class="pre">are_candidates_left</span></code>. The code needed to implement GRASP for solving our TSP is the following</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">TSPGrasp</span><span class="p">(</span><span class="n">base_grasp</span><span class="o">.</span><span class="n">GraspConstruct</span><span class="p">):</span>
<span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">instance</span><span class="p">,</span> <span class="n">solution_factory</span><span class="p">,</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">debug</span><span class="o">=</span><span class="bp">True</span><span class="p">,</span> <span class="n">log_file</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__init__</span><span class="p">(</span><span class="n">instance</span><span class="p">,</span> <span class="n">solution_factory</span><span class="p">,</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">debug</span><span class="p">,</span> <span class="n">log_file</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">visited</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining</span> <span class="o">=</span> <span class="nb">set</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">instance</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span>
<span class="bp">self</span><span class="o">.</span><span class="n">last_visited</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">solution</span><span class="o">.</span><span class="n">initial_city</span>
<span class="k">def</span> <span class="nf">initialize_solution</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="bp">self</span><span class="o">.</span><span class="n">visited</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">solution</span><span class="o">.</span><span class="n">initial_city</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">solution</span><span class="o">.</span><span class="n">initial_city</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">greedy_function</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">candidate</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">instance</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">last_visited</span><span class="p">][</span><span class="n">candidate</span><span class="p">]</span>
<span class="k">def</span> <span class="nf">are_candidates_left</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">True</span> <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining</span> <span class="k">else</span> <span class="bp">False</span>
<span class="k">def</span> <span class="nf">add_candidate</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">candidate</span><span class="p">):</span>
<span class="bp">self</span><span class="o">.</span><span class="n">solution</span><span class="o">.</span><span class="n">cities</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">candidate</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">visited</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">candidate</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">last_visited</span> <span class="o">=</span> <span class="n">candidate</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">candidate</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">make_candidates_list</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="p">[</span><span class="n">c</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">instance</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">last_visited</span><span class="p">]</span><span class="o">.</span><span class="n">keys</span><span class="p">()</span> <span class="k">if</span> <span class="n">c</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">visited</span><span class="p">]</span>
</pre></div>
</div>
<p>At solver initialization, we set some helpful values like visited cities and remaining cities. Note that solvers have access to instance and solution objects.</p>
<p>Initializing the solution is not always needed, but makes sense in this one. The greedy function can be an extremely complicated one, in our case,
is a very naive function, it just takes the distance between the last visited solution and the candidate.
The other three functions are related to the candidates list, first to check if there are candidates left we just check it there’s some city
remaining to be visited. To add a candidate we append the candidate to the solution cities sequence and update our values accordingly. Last, to make
the candidates list we take into account all cities not visited (the remaining ones).</p>
</div>
<div class="section" id="executing-our-solver">
<h3>Executing our solver<a class="headerlink" href="#executing-our-solver" title="Permalink to this headline">¶</a></h3>
<p>All the three needed components are implemented now (solution, instance and solver), that means that there’s only one more step, executing it all.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">or_testbed.solvers.factory</span> <span class="kn">import</span> <span class="n">make_factory_from</span>
<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">'__main__'</span><span class="p">:</span>
<span class="n">my_tsp</span> <span class="o">=</span> <span class="n">TSPInstance</span><span class="p">(</span><span class="n">instance_name</span><span class="p">,</span> <span class="n">cities</span><span class="p">)</span>
<span class="n">tsp_solution_factory</span> <span class="o">=</span> <span class="n">make_factory_from</span><span class="p">(</span><span class="n">TSPSolution</span><span class="p">,</span> <span class="n">initial_city</span><span class="o">=</span><span class="s1">'A'</span><span class="p">)</span>
<span class="n">tsp_solver</span> <span class="o">=</span> <span class="n">TSPGrasp</span><span class="p">(</span><span class="n">my_tsp</span><span class="p">,</span> <span class="n">solution_factory</span><span class="o">=</span><span class="n">tsp_solution_factory</span><span class="p">,</span> <span class="n">alpha</span><span class="o">=</span><span class="mf">0.0</span><span class="p">)</span>
<span class="n">feasible</span><span class="p">,</span> <span class="n">solution</span> <span class="o">=</span> <span class="n">tsp_solver</span><span class="o">.</span><span class="n">solve</span><span class="p">()</span>
</pre></div>
</div>
<p>Basically we instantiate the instance, the solution, the solver and then we call <code class="docutils literal notranslate"><span class="pre">solve</span></code> method, that triggers the solver and returns
the solution found. In fact, a tuple is returned, first element (<code class="docutils literal notranslate"><span class="pre">feasible</span></code>) is a boolean that tells if the solution found is feasible or not,
second element is the solution itself.
Note that the solution is not instantiated directly, what we do is to create a factory around it, but its the same syntax.
What this means is that solvers usually need to be able to create new solutions, so we want to give them a way to do so, thats what
<code class="docutils literal notranslate"><span class="pre">make_factory_from</span></code> does. The function signature is:</p>
<dl class="function">
<dt id="or_testbed.solvers.factory.make_factory_from">
<code class="sig-prename descclassname">or_testbed.solvers.factory.</code><code class="sig-name descname">make_factory_from</code><span class="sig-paren">(</span><em class="sig-param">cls</em>, <em class="sig-param">**kwargs</em><span class="sig-paren">)</span><a class="headerlink" href="#or_testbed.solvers.factory.make_factory_from" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>
<p>So, basically it expects a class reference (<code class="docutils literal notranslate"><span class="pre">cls</span></code>) and the arguments to instantiate that class, in the same way as a normal instantiation.</p>
</div>
</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 class="current">
<li class="toctree-l1"><a class="reference internal" href="install.html">Installation Guide</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Examples</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#traveling-salesman-problem-tsp">Traveling Salesman Problem (TSP)</a></li>
</ul>
</li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="entities.html">Entities</a></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>
<li class="toctree-l1"><a class="reference internal" href="factories.html">Factories</a></li>
</ul>
<div class="relations">
<h3>Related Topics</h3>
<ul>
<li><a href="index.html">Documentation overview</a><ul>
<li>Previous: <a href="install.html" title="previous chapter">Installation Guide</a></li>
<li>Next: <a href="entities.html" title="next chapter">Entities</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/examples.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>