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 <lemon/lp_clp.h> |
|
20 #include <coin/ClpSimplex.hpp> |
|
21 |
|
22 namespace lemon { |
|
23 |
|
24 LpClp::LpClp() { |
|
25 _prob = new ClpSimplex(); |
|
26 _init_temporals(); |
|
27 messageLevel(MESSAGE_NO_OUTPUT); |
|
28 } |
|
29 |
|
30 LpClp::LpClp(const LpClp& other) { |
|
31 _prob = new ClpSimplex(*other._prob); |
|
32 rows = other.rows; |
|
33 cols = other.cols; |
|
34 _init_temporals(); |
|
35 messageLevel(MESSAGE_NO_OUTPUT); |
|
36 } |
|
37 |
|
38 LpClp::~LpClp() { |
|
39 delete _prob; |
|
40 _clear_temporals(); |
|
41 } |
|
42 |
|
43 void LpClp::_init_temporals() { |
|
44 _primal_ray = 0; |
|
45 _dual_ray = 0; |
|
46 } |
|
47 |
|
48 void LpClp::_clear_temporals() { |
|
49 if (_primal_ray) { |
|
50 delete[] _primal_ray; |
|
51 _primal_ray = 0; |
|
52 } |
|
53 if (_dual_ray) { |
|
54 delete[] _dual_ray; |
|
55 _dual_ray = 0; |
|
56 } |
|
57 } |
|
58 |
|
59 LpClp* LpClp::_newSolver() const { |
|
60 LpClp* newlp = new LpClp; |
|
61 return newlp; |
|
62 } |
|
63 |
|
64 LpClp* LpClp::_cloneSolver() const { |
|
65 LpClp* copylp = new LpClp(*this); |
|
66 return copylp; |
|
67 } |
|
68 |
|
69 const char* LpClp::_solverName() const { return "LpClp"; } |
|
70 |
|
71 int LpClp::_addCol() { |
|
72 _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0); |
|
73 return _prob->numberColumns() - 1; |
|
74 } |
|
75 |
|
76 int LpClp::_addRow() { |
|
77 _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); |
|
78 return _prob->numberRows() - 1; |
|
79 } |
|
80 |
|
81 |
|
82 void LpClp::_eraseCol(int c) { |
|
83 _col_names_ref.erase(_prob->getColumnName(c)); |
|
84 _prob->deleteColumns(1, &c); |
|
85 } |
|
86 |
|
87 void LpClp::_eraseRow(int r) { |
|
88 _row_names_ref.erase(_prob->getRowName(r)); |
|
89 _prob->deleteRows(1, &r); |
|
90 } |
|
91 |
|
92 void LpClp::_eraseColId(int i) { |
|
93 cols.eraseIndex(i); |
|
94 cols.shiftIndices(i); |
|
95 } |
|
96 |
|
97 void LpClp::_eraseRowId(int i) { |
|
98 rows.eraseIndex(i); |
|
99 rows.shiftIndices(i); |
|
100 } |
|
101 |
|
102 void LpClp::_getColName(int c, std::string& name) const { |
|
103 name = _prob->getColumnName(c); |
|
104 } |
|
105 |
|
106 void LpClp::_setColName(int c, const std::string& name) { |
|
107 _prob->setColumnName(c, const_cast<std::string&>(name)); |
|
108 _col_names_ref[name] = c; |
|
109 } |
|
110 |
|
111 int LpClp::_colByName(const std::string& name) const { |
|
112 std::map<std::string, int>::const_iterator it = _col_names_ref.find(name); |
|
113 return it != _col_names_ref.end() ? it->second : -1; |
|
114 } |
|
115 |
|
116 void LpClp::_getRowName(int r, std::string& name) const { |
|
117 name = _prob->getRowName(r); |
|
118 } |
|
119 |
|
120 void LpClp::_setRowName(int r, const std::string& name) { |
|
121 _prob->setRowName(r, const_cast<std::string&>(name)); |
|
122 _row_names_ref[name] = r; |
|
123 } |
|
124 |
|
125 int LpClp::_rowByName(const std::string& name) const { |
|
126 std::map<std::string, int>::const_iterator it = _row_names_ref.find(name); |
|
127 return it != _row_names_ref.end() ? it->second : -1; |
|
128 } |
|
129 |
|
130 |
|
131 void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) { |
|
132 std::map<int, Value> coeffs; |
|
133 |
|
134 int n = _prob->clpMatrix()->getNumCols(); |
|
135 |
|
136 const int* indices = _prob->clpMatrix()->getIndices(); |
|
137 const double* elements = _prob->clpMatrix()->getElements(); |
|
138 |
|
139 for (int i = 0; i < n; ++i) { |
|
140 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i]; |
|
141 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i]; |
|
142 |
|
143 const int* it = std::lower_bound(indices + begin, indices + end, ix); |
|
144 if (it != indices + end && *it == ix && elements[it - indices] != 0.0) { |
|
145 coeffs[i] = 0.0; |
|
146 } |
|
147 } |
|
148 |
|
149 for (ExprIterator it = b; it != e; ++it) { |
|
150 coeffs[it->first] = it->second; |
|
151 } |
|
152 |
|
153 for (std::map<int, Value>::iterator it = coeffs.begin(); |
|
154 it != coeffs.end(); ++it) { |
|
155 _prob->modifyCoefficient(ix, it->first, it->second); |
|
156 } |
|
157 } |
|
158 |
|
159 void LpClp::_getRowCoeffs(int ix, InsertIterator b) const { |
|
160 int n = _prob->clpMatrix()->getNumCols(); |
|
161 |
|
162 const int* indices = _prob->clpMatrix()->getIndices(); |
|
163 const double* elements = _prob->clpMatrix()->getElements(); |
|
164 |
|
165 for (int i = 0; i < n; ++i) { |
|
166 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i]; |
|
167 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i]; |
|
168 |
|
169 const int* it = std::lower_bound(indices + begin, indices + end, ix); |
|
170 if (it != indices + end && *it == ix) { |
|
171 *b = std::make_pair(i, elements[it - indices]); |
|
172 } |
|
173 } |
|
174 } |
|
175 |
|
176 void LpClp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) { |
|
177 std::map<int, Value> coeffs; |
|
178 |
|
179 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; |
|
180 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; |
|
181 |
|
182 const int* indices = _prob->clpMatrix()->getIndices(); |
|
183 const double* elements = _prob->clpMatrix()->getElements(); |
|
184 |
|
185 for (CoinBigIndex i = begin; i != end; ++i) { |
|
186 if (elements[i] != 0.0) { |
|
187 coeffs[indices[i]] = 0.0; |
|
188 } |
|
189 } |
|
190 for (ExprIterator it = b; it != e; ++it) { |
|
191 coeffs[it->first] = it->second; |
|
192 } |
|
193 for (std::map<int, Value>::iterator it = coeffs.begin(); |
|
194 it != coeffs.end(); ++it) { |
|
195 _prob->modifyCoefficient(it->first, ix, it->second); |
|
196 } |
|
197 } |
|
198 |
|
199 void LpClp::_getColCoeffs(int ix, InsertIterator b) const { |
|
200 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; |
|
201 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; |
|
202 |
|
203 const int* indices = _prob->clpMatrix()->getIndices(); |
|
204 const double* elements = _prob->clpMatrix()->getElements(); |
|
205 |
|
206 for (CoinBigIndex i = begin; i != end; ++i) { |
|
207 *b = std::make_pair(indices[i], elements[i]); |
|
208 ++b; |
|
209 } |
|
210 } |
|
211 |
|
212 void LpClp::_setCoeff(int ix, int jx, Value value) { |
|
213 _prob->modifyCoefficient(ix, jx, value); |
|
214 } |
|
215 |
|
216 LpClp::Value LpClp::_getCoeff(int ix, int jx) const { |
|
217 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; |
|
218 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; |
|
219 |
|
220 const int* indices = _prob->clpMatrix()->getIndices(); |
|
221 const double* elements = _prob->clpMatrix()->getElements(); |
|
222 |
|
223 const int* it = std::lower_bound(indices + begin, indices + end, jx); |
|
224 if (it != indices + end && *it == jx) { |
|
225 return elements[it - indices]; |
|
226 } else { |
|
227 return 0.0; |
|
228 } |
|
229 } |
|
230 |
|
231 void LpClp::_setColLowerBound(int i, Value lo) { |
|
232 _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo); |
|
233 } |
|
234 |
|
235 LpClp::Value LpClp::_getColLowerBound(int i) const { |
|
236 double val = _prob->getColLower()[i]; |
|
237 return val == - COIN_DBL_MAX ? - INF : val; |
|
238 } |
|
239 |
|
240 void LpClp::_setColUpperBound(int i, Value up) { |
|
241 _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up); |
|
242 } |
|
243 |
|
244 LpClp::Value LpClp::_getColUpperBound(int i) const { |
|
245 double val = _prob->getColUpper()[i]; |
|
246 return val == COIN_DBL_MAX ? INF : val; |
|
247 } |
|
248 |
|
249 void LpClp::_setRowLowerBound(int i, Value lo) { |
|
250 _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo); |
|
251 } |
|
252 |
|
253 LpClp::Value LpClp::_getRowLowerBound(int i) const { |
|
254 double val = _prob->getRowLower()[i]; |
|
255 return val == - COIN_DBL_MAX ? - INF : val; |
|
256 } |
|
257 |
|
258 void LpClp::_setRowUpperBound(int i, Value up) { |
|
259 _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up); |
|
260 } |
|
261 |
|
262 LpClp::Value LpClp::_getRowUpperBound(int i) const { |
|
263 double val = _prob->getRowUpper()[i]; |
|
264 return val == COIN_DBL_MAX ? INF : val; |
|
265 } |
|
266 |
|
267 void LpClp::_setObjCoeffs(ExprIterator b, ExprIterator e) { |
|
268 int num = _prob->clpMatrix()->getNumCols(); |
|
269 for (int i = 0; i < num; ++i) { |
|
270 _prob->setObjectiveCoefficient(i, 0.0); |
|
271 } |
|
272 for (ExprIterator it = b; it != e; ++it) { |
|
273 _prob->setObjectiveCoefficient(it->first, it->second); |
|
274 } |
|
275 } |
|
276 |
|
277 void LpClp::_getObjCoeffs(InsertIterator b) const { |
|
278 int num = _prob->clpMatrix()->getNumCols(); |
|
279 for (int i = 0; i < num; ++i) { |
|
280 Value coef = _prob->getObjCoefficients()[i]; |
|
281 if (coef != 0.0) { |
|
282 *b = std::make_pair(i, coef); |
|
283 ++b; |
|
284 } |
|
285 } |
|
286 } |
|
287 |
|
288 void LpClp::_setObjCoeff(int i, Value obj_coef) { |
|
289 _prob->setObjectiveCoefficient(i, obj_coef); |
|
290 } |
|
291 |
|
292 LpClp::Value LpClp::_getObjCoeff(int i) const { |
|
293 return _prob->getObjCoefficients()[i]; |
|
294 } |
|
295 |
|
296 LpClp::SolveExitStatus LpClp::_solve() { |
|
297 return _prob->primal() >= 0 ? SOLVED : UNSOLVED; |
|
298 } |
|
299 |
|
300 LpClp::SolveExitStatus LpClp::solvePrimal() { |
|
301 return _prob->primal() >= 0 ? SOLVED : UNSOLVED; |
|
302 } |
|
303 |
|
304 LpClp::SolveExitStatus LpClp::solveDual() { |
|
305 return _prob->dual() >= 0 ? SOLVED : UNSOLVED; |
|
306 } |
|
307 |
|
308 LpClp::SolveExitStatus LpClp::solveBarrier() { |
|
309 return _prob->barrier() >= 0 ? SOLVED : UNSOLVED; |
|
310 } |
|
311 |
|
312 LpClp::Value LpClp::_getPrimal(int i) const { |
|
313 return _prob->primalColumnSolution()[i]; |
|
314 } |
|
315 LpClp::Value LpClp::_getPrimalValue() const { |
|
316 return _prob->objectiveValue(); |
|
317 } |
|
318 |
|
319 LpClp::Value LpClp::_getDual(int i) const { |
|
320 return _prob->dualRowSolution()[i]; |
|
321 } |
|
322 |
|
323 LpClp::Value LpClp::_getPrimalRay(int i) const { |
|
324 if (!_primal_ray) { |
|
325 _primal_ray = _prob->unboundedRay(); |
|
326 LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided"); |
|
327 } |
|
328 return _primal_ray[i]; |
|
329 } |
|
330 |
|
331 LpClp::Value LpClp::_getDualRay(int i) const { |
|
332 if (!_dual_ray) { |
|
333 _dual_ray = _prob->infeasibilityRay(); |
|
334 LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided"); |
|
335 } |
|
336 return _dual_ray[i]; |
|
337 } |
|
338 |
|
339 LpClp::VarStatus LpClp::_getColStatus(int i) const { |
|
340 switch (_prob->getColumnStatus(i)) { |
|
341 case ClpSimplex::basic: |
|
342 return BASIC; |
|
343 case ClpSimplex::isFree: |
|
344 return FREE; |
|
345 case ClpSimplex::atUpperBound: |
|
346 return UPPER; |
|
347 case ClpSimplex::atLowerBound: |
|
348 return LOWER; |
|
349 case ClpSimplex::isFixed: |
|
350 return FIXED; |
|
351 case ClpSimplex::superBasic: |
|
352 return FREE; |
|
353 default: |
|
354 LEMON_ASSERT(false, "Wrong column status"); |
|
355 return VarStatus(); |
|
356 } |
|
357 } |
|
358 |
|
359 LpClp::VarStatus LpClp::_getRowStatus(int i) const { |
|
360 switch (_prob->getColumnStatus(i)) { |
|
361 case ClpSimplex::basic: |
|
362 return BASIC; |
|
363 case ClpSimplex::isFree: |
|
364 return FREE; |
|
365 case ClpSimplex::atUpperBound: |
|
366 return UPPER; |
|
367 case ClpSimplex::atLowerBound: |
|
368 return LOWER; |
|
369 case ClpSimplex::isFixed: |
|
370 return FIXED; |
|
371 case ClpSimplex::superBasic: |
|
372 return FREE; |
|
373 default: |
|
374 LEMON_ASSERT(false, "Wrong row status"); |
|
375 return VarStatus(); |
|
376 } |
|
377 } |
|
378 |
|
379 |
|
380 LpClp::ProblemType LpClp::_getPrimalType() const { |
|
381 if (_prob->isProvenOptimal()) { |
|
382 return OPTIMAL; |
|
383 } else if (_prob->isProvenPrimalInfeasible()) { |
|
384 return INFEASIBLE; |
|
385 } else if (_prob->isProvenDualInfeasible()) { |
|
386 return UNBOUNDED; |
|
387 } else { |
|
388 return UNDEFINED; |
|
389 } |
|
390 } |
|
391 |
|
392 LpClp::ProblemType LpClp::_getDualType() const { |
|
393 if (_prob->isProvenOptimal()) { |
|
394 return OPTIMAL; |
|
395 } else if (_prob->isProvenDualInfeasible()) { |
|
396 return INFEASIBLE; |
|
397 } else if (_prob->isProvenPrimalInfeasible()) { |
|
398 return INFEASIBLE; |
|
399 } else { |
|
400 return UNDEFINED; |
|
401 } |
|
402 } |
|
403 |
|
404 void LpClp::_setSense(LpClp::Sense sense) { |
|
405 switch (sense) { |
|
406 case MIN: |
|
407 _prob->setOptimizationDirection(1); |
|
408 break; |
|
409 case MAX: |
|
410 _prob->setOptimizationDirection(-1); |
|
411 break; |
|
412 } |
|
413 } |
|
414 |
|
415 LpClp::Sense LpClp::_getSense() const { |
|
416 double dir = _prob->optimizationDirection(); |
|
417 if (dir > 0.0) { |
|
418 return MIN; |
|
419 } else { |
|
420 return MAX; |
|
421 } |
|
422 } |
|
423 |
|
424 void LpClp::_clear() { |
|
425 delete _prob; |
|
426 _prob = new ClpSimplex(); |
|
427 rows.clear(); |
|
428 cols.clear(); |
|
429 _col_names_ref.clear(); |
|
430 _clear_temporals(); |
|
431 } |
|
432 |
|
433 void LpClp::messageLevel(MessageLevel m) { |
|
434 _prob->setLogLevel(static_cast<int>(m)); |
|
435 } |
|
436 |
|
437 } //END OF NAMESPACE LEMON |
|