COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/clp.cc

Last change on this file was 1130:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 6 years ago

STL style iterators (#325)

For

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