|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <lemon/soplex.h> |
|
21 |
|
22 #include <soplex/soplex.h> |
|
23 |
|
24 |
|
25 ///\file |
|
26 ///\brief Implementation of the LEMON-SOPLEX lp solver interface. |
|
27 namespace lemon { |
|
28 |
|
29 LpSoplex::LpSoplex() { |
|
30 soplex = new soplex::SoPlex; |
|
31 } |
|
32 |
|
33 LpSoplex::~LpSoplex() { |
|
34 delete soplex; |
|
35 } |
|
36 |
|
37 LpSoplex::LpSoplex(const LpSoplex& lp) { |
|
38 rows = lp.rows; |
|
39 cols = lp.cols; |
|
40 |
|
41 soplex = new soplex::SoPlex; |
|
42 (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex); |
|
43 |
|
44 _col_names = lp._col_names; |
|
45 _col_names_ref = lp._col_names_ref; |
|
46 |
|
47 _row_names = lp._row_names; |
|
48 _row_names_ref = lp._row_names_ref; |
|
49 |
|
50 } |
|
51 |
|
52 void LpSoplex::_clear_temporals() { |
|
53 _primal_values.clear(); |
|
54 _dual_values.clear(); |
|
55 } |
|
56 |
|
57 LpSoplex* LpSoplex::_newSolver() const { |
|
58 LpSoplex* newlp = new LpSoplex(); |
|
59 return newlp; |
|
60 } |
|
61 |
|
62 LpSoplex* LpSoplex::_cloneSolver() const { |
|
63 LpSoplex* newlp = new LpSoplex(*this); |
|
64 return newlp; |
|
65 } |
|
66 |
|
67 const char* LpSoplex::_solverName() const { return "LpSoplex"; } |
|
68 |
|
69 int LpSoplex::_addCol() { |
|
70 soplex::LPCol c; |
|
71 c.setLower(-soplex::infinity); |
|
72 c.setUpper(soplex::infinity); |
|
73 soplex->addCol(c); |
|
74 |
|
75 _col_names.push_back(std::string()); |
|
76 |
|
77 return soplex->nCols() - 1; |
|
78 } |
|
79 |
|
80 int LpSoplex::_addRow() { |
|
81 soplex::LPRow r; |
|
82 r.setLhs(-soplex::infinity); |
|
83 r.setRhs(soplex::infinity); |
|
84 soplex->addRow(r); |
|
85 |
|
86 _row_names.push_back(std::string()); |
|
87 |
|
88 return soplex->nRows() - 1; |
|
89 } |
|
90 |
|
91 |
|
92 void LpSoplex::_eraseCol(int i) { |
|
93 soplex->removeCol(i); |
|
94 _col_names_ref.erase(_col_names[i]); |
|
95 _col_names[i] = _col_names.back(); |
|
96 _col_names_ref[_col_names.back()] = i; |
|
97 _col_names.pop_back(); |
|
98 } |
|
99 |
|
100 void LpSoplex::_eraseRow(int i) { |
|
101 soplex->removeRow(i); |
|
102 _row_names_ref.erase(_row_names[i]); |
|
103 _row_names[i] = _row_names.back(); |
|
104 _row_names_ref[_row_names.back()] = i; |
|
105 _row_names.pop_back(); |
|
106 } |
|
107 |
|
108 void LpSoplex::_eraseColId(int i) { |
|
109 cols.eraseIndex(i); |
|
110 cols.relocateIndex(i, cols.maxIndex()); |
|
111 } |
|
112 void LpSoplex::_eraseRowId(int i) { |
|
113 rows.eraseIndex(i); |
|
114 rows.relocateIndex(i, rows.maxIndex()); |
|
115 } |
|
116 |
|
117 void LpSoplex::_getColName(int c, std::string &name) const { |
|
118 name = _col_names[c]; |
|
119 } |
|
120 |
|
121 void LpSoplex::_setColName(int c, const std::string &name) { |
|
122 _col_names_ref.erase(_col_names[c]); |
|
123 _col_names[c] = name; |
|
124 if (!name.empty()) { |
|
125 _col_names_ref.insert(std::make_pair(name, c)); |
|
126 } |
|
127 } |
|
128 |
|
129 int LpSoplex::_colByName(const std::string& name) const { |
|
130 std::map<std::string, int>::const_iterator it = |
|
131 _col_names_ref.find(name); |
|
132 if (it != _col_names_ref.end()) { |
|
133 return it->second; |
|
134 } else { |
|
135 return -1; |
|
136 } |
|
137 } |
|
138 |
|
139 void LpSoplex::_getRowName(int r, std::string &name) const { |
|
140 name = _row_names[r]; |
|
141 } |
|
142 |
|
143 void LpSoplex::_setRowName(int r, const std::string &name) { |
|
144 _row_names_ref.erase(_row_names[r]); |
|
145 _row_names[r] = name; |
|
146 if (!name.empty()) { |
|
147 _row_names_ref.insert(std::make_pair(name, r)); |
|
148 } |
|
149 } |
|
150 |
|
151 int LpSoplex::_rowByName(const std::string& name) const { |
|
152 std::map<std::string, int>::const_iterator it = |
|
153 _row_names_ref.find(name); |
|
154 if (it != _row_names_ref.end()) { |
|
155 return it->second; |
|
156 } else { |
|
157 return -1; |
|
158 } |
|
159 } |
|
160 |
|
161 |
|
162 void LpSoplex::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) { |
|
163 for (int j = 0; j < soplex->nCols(); ++j) { |
|
164 soplex->changeElement(i, j, 0.0); |
|
165 } |
|
166 for(ExprIterator it = b; it != e; ++it) { |
|
167 soplex->changeElement(i, it->first, it->second); |
|
168 } |
|
169 } |
|
170 |
|
171 void LpSoplex::_getRowCoeffs(int i, InsertIterator b) const { |
|
172 const soplex::SVector& vec = soplex->rowVector(i); |
|
173 for (int k = 0; k < vec.size(); ++k) { |
|
174 *b = std::make_pair(vec.index(k), vec.value(k)); |
|
175 ++b; |
|
176 } |
|
177 } |
|
178 |
|
179 void LpSoplex::_setColCoeffs(int j, ExprIterator b, ExprIterator e) { |
|
180 for (int i = 0; i < soplex->nRows(); ++i) { |
|
181 soplex->changeElement(i, j, 0.0); |
|
182 } |
|
183 for(ExprIterator it = b; it != e; ++it) { |
|
184 soplex->changeElement(it->first, j, it->second); |
|
185 } |
|
186 } |
|
187 |
|
188 void LpSoplex::_getColCoeffs(int i, InsertIterator b) const { |
|
189 const soplex::SVector& vec = soplex->colVector(i); |
|
190 for (int k = 0; k < vec.size(); ++k) { |
|
191 *b = std::make_pair(vec.index(k), vec.value(k)); |
|
192 ++b; |
|
193 } |
|
194 } |
|
195 |
|
196 void LpSoplex::_setCoeff(int i, int j, Value value) { |
|
197 soplex->changeElement(i, j, value); |
|
198 } |
|
199 |
|
200 LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const { |
|
201 return soplex->rowVector(i)[j]; |
|
202 } |
|
203 |
|
204 void LpSoplex::_setColLowerBound(int i, Value value) { |
|
205 LEMON_ASSERT(value != INF, "Invalid bound"); |
|
206 soplex->changeLower(i, value != -INF ? value : -soplex::infinity); |
|
207 } |
|
208 |
|
209 LpSoplex::Value LpSoplex::_getColLowerBound(int i) const { |
|
210 double value = soplex->lower(i); |
|
211 return value != -soplex::infinity ? value : -INF; |
|
212 } |
|
213 |
|
214 void LpSoplex::_setColUpperBound(int i, Value value) { |
|
215 LEMON_ASSERT(value != -INF, "Invalid bound"); |
|
216 soplex->changeUpper(i, value != INF ? value : soplex::infinity); |
|
217 } |
|
218 |
|
219 LpSoplex::Value LpSoplex::_getColUpperBound(int i) const { |
|
220 double value = soplex->upper(i); |
|
221 return value != soplex::infinity ? value : INF; |
|
222 } |
|
223 |
|
224 void LpSoplex::_setRowLowerBound(int i, Value lb) { |
|
225 LEMON_ASSERT(lb != INF, "Invalid bound"); |
|
226 soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i)); |
|
227 } |
|
228 |
|
229 LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const { |
|
230 double res = soplex->lhs(i); |
|
231 return res == -soplex::infinity ? -INF : res; |
|
232 } |
|
233 |
|
234 void LpSoplex::_setRowUpperBound(int i, Value ub) { |
|
235 LEMON_ASSERT(ub != -INF, "Invalid bound"); |
|
236 soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity); |
|
237 } |
|
238 |
|
239 LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const { |
|
240 double res = soplex->rhs(i); |
|
241 return res == soplex::infinity ? INF : res; |
|
242 } |
|
243 |
|
244 void LpSoplex::_setObjCoeffs(ExprIterator b, ExprIterator e) { |
|
245 for (int j = 0; j < soplex->nCols(); ++j) { |
|
246 soplex->changeObj(j, 0.0); |
|
247 } |
|
248 for (ExprIterator it = b; it != e; ++it) { |
|
249 soplex->changeObj(it->first, it->second); |
|
250 } |
|
251 } |
|
252 |
|
253 void LpSoplex::_getObjCoeffs(InsertIterator b) const { |
|
254 for (int j = 0; j < soplex->nCols(); ++j) { |
|
255 Value coef = soplex->obj(j); |
|
256 if (coef != 0.0) { |
|
257 *b = std::make_pair(j, coef); |
|
258 ++b; |
|
259 } |
|
260 } |
|
261 } |
|
262 |
|
263 void LpSoplex::_setObjCoeff(int i, Value obj_coef) { |
|
264 soplex->changeObj(i, obj_coef); |
|
265 } |
|
266 |
|
267 LpSoplex::Value LpSoplex::_getObjCoeff(int i) const { |
|
268 return soplex->obj(i); |
|
269 } |
|
270 |
|
271 LpSoplex::SolveExitStatus LpSoplex::_solve() { |
|
272 |
|
273 _clear_temporals(); |
|
274 |
|
275 soplex::SPxSolver::Status status = soplex->solve(); |
|
276 |
|
277 switch (status) { |
|
278 case soplex::SPxSolver::OPTIMAL: |
|
279 case soplex::SPxSolver::INFEASIBLE: |
|
280 case soplex::SPxSolver::UNBOUNDED: |
|
281 return SOLVED; |
|
282 default: |
|
283 return UNSOLVED; |
|
284 } |
|
285 } |
|
286 |
|
287 LpSoplex::Value LpSoplex::_getPrimal(int i) const { |
|
288 if (_primal_values.empty()) { |
|
289 _primal_values.resize(soplex->nCols()); |
|
290 soplex::Vector pv(_primal_values.size(), &_primal_values.front()); |
|
291 soplex->getPrimal(pv); |
|
292 } |
|
293 return _primal_values[i]; |
|
294 } |
|
295 |
|
296 LpSoplex::Value LpSoplex::_getDual(int i) const { |
|
297 if (_dual_values.empty()) { |
|
298 _dual_values.resize(soplex->nRows()); |
|
299 soplex::Vector dv(_dual_values.size(), &_dual_values.front()); |
|
300 soplex->getDual(dv); |
|
301 } |
|
302 return _dual_values[i]; |
|
303 } |
|
304 |
|
305 LpSoplex::Value LpSoplex::_getPrimalValue() const { |
|
306 return soplex->objValue(); |
|
307 } |
|
308 |
|
309 LpSoplex::VarStatus LpSoplex::_getColStatus(int i) const { |
|
310 switch (soplex->getBasisColStatus(i)) { |
|
311 case soplex::SPxSolver::BASIC: |
|
312 return BASIC; |
|
313 case soplex::SPxSolver::ON_UPPER: |
|
314 return UPPER; |
|
315 case soplex::SPxSolver::ON_LOWER: |
|
316 return LOWER; |
|
317 case soplex::SPxSolver::FIXED: |
|
318 return FIXED; |
|
319 case soplex::SPxSolver::ZERO: |
|
320 return FREE; |
|
321 default: |
|
322 LEMON_ASSERT(false, "Wrong column status"); |
|
323 return VarStatus(); |
|
324 } |
|
325 } |
|
326 |
|
327 LpSoplex::VarStatus LpSoplex::_getRowStatus(int i) const { |
|
328 switch (soplex->getBasisRowStatus(i)) { |
|
329 case soplex::SPxSolver::BASIC: |
|
330 return BASIC; |
|
331 case soplex::SPxSolver::ON_UPPER: |
|
332 return UPPER; |
|
333 case soplex::SPxSolver::ON_LOWER: |
|
334 return LOWER; |
|
335 case soplex::SPxSolver::FIXED: |
|
336 return FIXED; |
|
337 case soplex::SPxSolver::ZERO: |
|
338 return FREE; |
|
339 default: |
|
340 LEMON_ASSERT(false, "Wrong row status"); |
|
341 return VarStatus(); |
|
342 } |
|
343 } |
|
344 |
|
345 LpSoplex::Value LpSoplex::_getPrimalRay(int i) const { |
|
346 if (_primal_ray.empty()) { |
|
347 _primal_ray.resize(soplex->nCols()); |
|
348 soplex::Vector pv(_primal_ray.size(), &_primal_ray.front()); |
|
349 soplex->getDualfarkas(pv); |
|
350 } |
|
351 return _primal_ray[i]; |
|
352 } |
|
353 |
|
354 LpSoplex::Value LpSoplex::_getDualRay(int i) const { |
|
355 if (_dual_ray.empty()) { |
|
356 _dual_ray.resize(soplex->nRows()); |
|
357 soplex::Vector dv(_dual_ray.size(), &_dual_ray.front()); |
|
358 soplex->getDualfarkas(dv); |
|
359 } |
|
360 return _dual_ray[i]; |
|
361 } |
|
362 |
|
363 LpSoplex::ProblemType LpSoplex::_getPrimalType() const { |
|
364 switch (soplex->status()) { |
|
365 case soplex::SPxSolver::OPTIMAL: |
|
366 return OPTIMAL; |
|
367 case soplex::SPxSolver::UNBOUNDED: |
|
368 return UNBOUNDED; |
|
369 case soplex::SPxSolver::INFEASIBLE: |
|
370 return INFEASIBLE; |
|
371 default: |
|
372 return UNDEFINED; |
|
373 } |
|
374 } |
|
375 |
|
376 LpSoplex::ProblemType LpSoplex::_getDualType() const { |
|
377 switch (soplex->status()) { |
|
378 case soplex::SPxSolver::OPTIMAL: |
|
379 return OPTIMAL; |
|
380 case soplex::SPxSolver::UNBOUNDED: |
|
381 return UNBOUNDED; |
|
382 case soplex::SPxSolver::INFEASIBLE: |
|
383 return INFEASIBLE; |
|
384 default: |
|
385 return UNDEFINED; |
|
386 } |
|
387 } |
|
388 |
|
389 void LpSoplex::_setSense(Sense sense) { |
|
390 switch (sense) { |
|
391 case MIN: |
|
392 soplex->changeSense(soplex::SPxSolver::MINIMIZE); |
|
393 break; |
|
394 case MAX: |
|
395 soplex->changeSense(soplex::SPxSolver::MAXIMIZE); |
|
396 } |
|
397 } |
|
398 |
|
399 LpSoplex::Sense LpSoplex::_getSense() const { |
|
400 switch (soplex->spxSense()) { |
|
401 case soplex::SPxSolver::MAXIMIZE: |
|
402 return MAX; |
|
403 case soplex::SPxSolver::MINIMIZE: |
|
404 return MIN; |
|
405 default: |
|
406 LEMON_ASSERT(false, "Wrong sense."); |
|
407 return LpSoplex::Sense(); |
|
408 } |
|
409 } |
|
410 |
|
411 void LpSoplex::_clear() { |
|
412 soplex->clear(); |
|
413 _col_names.clear(); |
|
414 _col_names_ref.clear(); |
|
415 _row_names.clear(); |
|
416 _row_names_ref.clear(); |
|
417 cols.clear(); |
|
418 rows.clear(); |
|
419 _clear_temporals(); |
|
420 } |
|
421 |
|
422 } //namespace lemon |
|
423 |