lemon/clp.cc
changeset 802 994c7df296c9
parent 540 9db62975c32b
child 746 e4554cd6b2bf
child 955 8d281761dea4
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/clp.cc	Thu Dec 10 17:05:35 2009 +0100
     1.3 @@ -0,0 +1,453 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <lemon/clp.h>
    1.23 +#include <coin/ClpSimplex.hpp>
    1.24 +
    1.25 +namespace lemon {
    1.26 +
    1.27 +  ClpLp::ClpLp() {
    1.28 +    _prob = new ClpSimplex();
    1.29 +    _init_temporals();
    1.30 +    messageLevel(MESSAGE_NOTHING);
    1.31 +  }
    1.32 +
    1.33 +  ClpLp::ClpLp(const ClpLp& other) {
    1.34 +    _prob = new ClpSimplex(*other._prob);
    1.35 +    rows = other.rows;
    1.36 +    cols = other.cols;
    1.37 +    _init_temporals();
    1.38 +    messageLevel(MESSAGE_NOTHING);
    1.39 +  }
    1.40 +
    1.41 +  ClpLp::~ClpLp() {
    1.42 +    delete _prob;
    1.43 +    _clear_temporals();
    1.44 +  }
    1.45 +
    1.46 +  void ClpLp::_init_temporals() {
    1.47 +    _primal_ray = 0;
    1.48 +    _dual_ray = 0;
    1.49 +  }
    1.50 +
    1.51 +  void ClpLp::_clear_temporals() {
    1.52 +    if (_primal_ray) {
    1.53 +      delete[] _primal_ray;
    1.54 +      _primal_ray = 0;
    1.55 +    }
    1.56 +    if (_dual_ray) {
    1.57 +      delete[] _dual_ray;
    1.58 +      _dual_ray = 0;
    1.59 +    }
    1.60 +  }
    1.61 +
    1.62 +  ClpLp* ClpLp::newSolver() const {
    1.63 +    ClpLp* newlp = new ClpLp;
    1.64 +    return newlp;
    1.65 +  }
    1.66 +
    1.67 +  ClpLp* ClpLp::cloneSolver() const {
    1.68 +    ClpLp* copylp = new ClpLp(*this);
    1.69 +    return copylp;
    1.70 +  }
    1.71 +
    1.72 +  const char* ClpLp::_solverName() const { return "ClpLp"; }
    1.73 +
    1.74 +  int ClpLp::_addCol() {
    1.75 +    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
    1.76 +    return _prob->numberColumns() - 1;
    1.77 +  }
    1.78 +
    1.79 +  int ClpLp::_addRow() {
    1.80 +    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    1.81 +    return _prob->numberRows() - 1;
    1.82 +  }
    1.83 +
    1.84 +
    1.85 +  void ClpLp::_eraseCol(int c) {
    1.86 +    _col_names_ref.erase(_prob->getColumnName(c));
    1.87 +    _prob->deleteColumns(1, &c);
    1.88 +  }
    1.89 +
    1.90 +  void ClpLp::_eraseRow(int r) {
    1.91 +    _row_names_ref.erase(_prob->getRowName(r));
    1.92 +    _prob->deleteRows(1, &r);
    1.93 +  }
    1.94 +
    1.95 +  void ClpLp::_eraseColId(int i) {
    1.96 +    cols.eraseIndex(i);
    1.97 +    cols.shiftIndices(i);
    1.98 +  }
    1.99 +
   1.100 +  void ClpLp::_eraseRowId(int i) {
   1.101 +    rows.eraseIndex(i);
   1.102 +    rows.shiftIndices(i);
   1.103 +  }
   1.104 +
   1.105 +  void ClpLp::_getColName(int c, std::string& name) const {
   1.106 +    name = _prob->getColumnName(c);
   1.107 +  }
   1.108 +
   1.109 +  void ClpLp::_setColName(int c, const std::string& name) {
   1.110 +    _prob->setColumnName(c, const_cast<std::string&>(name));
   1.111 +    _col_names_ref[name] = c;
   1.112 +  }
   1.113 +
   1.114 +  int ClpLp::_colByName(const std::string& name) const {
   1.115 +    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
   1.116 +    return it != _col_names_ref.end() ? it->second : -1;
   1.117 +  }
   1.118 +
   1.119 +  void ClpLp::_getRowName(int r, std::string& name) const {
   1.120 +    name = _prob->getRowName(r);
   1.121 +  }
   1.122 +
   1.123 +  void ClpLp::_setRowName(int r, const std::string& name) {
   1.124 +    _prob->setRowName(r, const_cast<std::string&>(name));
   1.125 +    _row_names_ref[name] = r;
   1.126 +  }
   1.127 +
   1.128 +  int ClpLp::_rowByName(const std::string& name) const {
   1.129 +    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
   1.130 +    return it != _row_names_ref.end() ? it->second : -1;
   1.131 +  }
   1.132 +
   1.133 +
   1.134 +  void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
   1.135 +    std::map<int, Value> coeffs;
   1.136 +
   1.137 +    int n = _prob->clpMatrix()->getNumCols();
   1.138 +
   1.139 +    const int* indices = _prob->clpMatrix()->getIndices();
   1.140 +    const double* elements = _prob->clpMatrix()->getElements();
   1.141 +
   1.142 +    for (int i = 0; i < n; ++i) {
   1.143 +      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
   1.144 +      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
   1.145 +
   1.146 +      const int* it = std::lower_bound(indices + begin, indices + end, ix);
   1.147 +      if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
   1.148 +        coeffs[i] = 0.0;
   1.149 +      }
   1.150 +    }
   1.151 +
   1.152 +    for (ExprIterator it = b; it != e; ++it) {
   1.153 +      coeffs[it->first] = it->second;
   1.154 +    }
   1.155 +
   1.156 +    for (std::map<int, Value>::iterator it = coeffs.begin();
   1.157 +         it != coeffs.end(); ++it) {
   1.158 +      _prob->modifyCoefficient(ix, it->first, it->second);
   1.159 +    }
   1.160 +  }
   1.161 +
   1.162 +  void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
   1.163 +    int n = _prob->clpMatrix()->getNumCols();
   1.164 +
   1.165 +    const int* indices = _prob->clpMatrix()->getIndices();
   1.166 +    const double* elements = _prob->clpMatrix()->getElements();
   1.167 +
   1.168 +    for (int i = 0; i < n; ++i) {
   1.169 +      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
   1.170 +      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
   1.171 +
   1.172 +      const int* it = std::lower_bound(indices + begin, indices + end, ix);
   1.173 +      if (it != indices + end && *it == ix) {
   1.174 +        *b = std::make_pair(i, elements[it - indices]);
   1.175 +      }
   1.176 +    }
   1.177 +  }
   1.178 +
   1.179 +  void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
   1.180 +    std::map<int, Value> coeffs;
   1.181 +
   1.182 +    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
   1.183 +    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
   1.184 +
   1.185 +    const int* indices = _prob->clpMatrix()->getIndices();
   1.186 +    const double* elements = _prob->clpMatrix()->getElements();
   1.187 +
   1.188 +    for (CoinBigIndex i = begin; i != end; ++i) {
   1.189 +      if (elements[i] != 0.0) {
   1.190 +        coeffs[indices[i]] = 0.0;
   1.191 +      }
   1.192 +    }
   1.193 +    for (ExprIterator it = b; it != e; ++it) {
   1.194 +      coeffs[it->first] = it->second;
   1.195 +    }
   1.196 +    for (std::map<int, Value>::iterator it = coeffs.begin();
   1.197 +         it != coeffs.end(); ++it) {
   1.198 +      _prob->modifyCoefficient(it->first, ix, it->second);
   1.199 +    }
   1.200 +  }
   1.201 +
   1.202 +  void ClpLp::_getColCoeffs(int ix, InsertIterator b) const {
   1.203 +    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
   1.204 +    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
   1.205 +
   1.206 +    const int* indices = _prob->clpMatrix()->getIndices();
   1.207 +    const double* elements = _prob->clpMatrix()->getElements();
   1.208 +
   1.209 +    for (CoinBigIndex i = begin; i != end; ++i) {
   1.210 +      *b = std::make_pair(indices[i], elements[i]);
   1.211 +      ++b;
   1.212 +    }
   1.213 +  }
   1.214 +
   1.215 +  void ClpLp::_setCoeff(int ix, int jx, Value value) {
   1.216 +    _prob->modifyCoefficient(ix, jx, value);
   1.217 +  }
   1.218 +
   1.219 +  ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const {
   1.220 +    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
   1.221 +    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
   1.222 +
   1.223 +    const int* indices = _prob->clpMatrix()->getIndices();
   1.224 +    const double* elements = _prob->clpMatrix()->getElements();
   1.225 +
   1.226 +    const int* it = std::lower_bound(indices + begin, indices + end, jx);
   1.227 +    if (it != indices + end && *it == jx) {
   1.228 +      return elements[it - indices];
   1.229 +    } else {
   1.230 +      return 0.0;
   1.231 +    }
   1.232 +  }
   1.233 +
   1.234 +  void ClpLp::_setColLowerBound(int i, Value lo) {
   1.235 +    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
   1.236 +  }
   1.237 +
   1.238 +  ClpLp::Value ClpLp::_getColLowerBound(int i) const {
   1.239 +    double val = _prob->getColLower()[i];
   1.240 +    return val == - COIN_DBL_MAX ? - INF : val;
   1.241 +  }
   1.242 +
   1.243 +  void ClpLp::_setColUpperBound(int i, Value up) {
   1.244 +    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
   1.245 +  }
   1.246 +
   1.247 +  ClpLp::Value ClpLp::_getColUpperBound(int i) const {
   1.248 +    double val = _prob->getColUpper()[i];
   1.249 +    return val == COIN_DBL_MAX ? INF : val;
   1.250 +  }
   1.251 +
   1.252 +  void ClpLp::_setRowLowerBound(int i, Value lo) {
   1.253 +    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
   1.254 +  }
   1.255 +
   1.256 +  ClpLp::Value ClpLp::_getRowLowerBound(int i) const {
   1.257 +    double val = _prob->getRowLower()[i];
   1.258 +    return val == - COIN_DBL_MAX ? - INF : val;
   1.259 +  }
   1.260 +
   1.261 +  void ClpLp::_setRowUpperBound(int i, Value up) {
   1.262 +    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
   1.263 +  }
   1.264 +
   1.265 +  ClpLp::Value ClpLp::_getRowUpperBound(int i) const {
   1.266 +    double val = _prob->getRowUpper()[i];
   1.267 +    return val == COIN_DBL_MAX ? INF : val;
   1.268 +  }
   1.269 +
   1.270 +  void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
   1.271 +    int num = _prob->clpMatrix()->getNumCols();
   1.272 +    for (int i = 0; i < num; ++i) {
   1.273 +      _prob->setObjectiveCoefficient(i, 0.0);
   1.274 +    }
   1.275 +    for (ExprIterator it = b; it != e; ++it) {
   1.276 +      _prob->setObjectiveCoefficient(it->first, it->second);
   1.277 +    }
   1.278 +  }
   1.279 +
   1.280 +  void ClpLp::_getObjCoeffs(InsertIterator b) const {
   1.281 +    int num = _prob->clpMatrix()->getNumCols();
   1.282 +    for (int i = 0; i < num; ++i) {
   1.283 +      Value coef = _prob->getObjCoefficients()[i];
   1.284 +      if (coef != 0.0) {
   1.285 +        *b = std::make_pair(i, coef);
   1.286 +        ++b;
   1.287 +      }
   1.288 +    }
   1.289 +  }
   1.290 +
   1.291 +  void ClpLp::_setObjCoeff(int i, Value obj_coef) {
   1.292 +    _prob->setObjectiveCoefficient(i, obj_coef);
   1.293 +  }
   1.294 +
   1.295 +  ClpLp::Value ClpLp::_getObjCoeff(int i) const {
   1.296 +    return _prob->getObjCoefficients()[i];
   1.297 +  }
   1.298 +
   1.299 +  ClpLp::SolveExitStatus ClpLp::_solve() {
   1.300 +    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
   1.301 +  }
   1.302 +
   1.303 +  ClpLp::SolveExitStatus ClpLp::solvePrimal() {
   1.304 +    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
   1.305 +  }
   1.306 +
   1.307 +  ClpLp::SolveExitStatus ClpLp::solveDual() {
   1.308 +    return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
   1.309 +  }
   1.310 +
   1.311 +  ClpLp::SolveExitStatus ClpLp::solveBarrier() {
   1.312 +    return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
   1.313 +  }
   1.314 +
   1.315 +  ClpLp::Value ClpLp::_getPrimal(int i) const {
   1.316 +    return _prob->primalColumnSolution()[i];
   1.317 +  }
   1.318 +  ClpLp::Value ClpLp::_getPrimalValue() const {
   1.319 +    return _prob->objectiveValue();
   1.320 +  }
   1.321 +
   1.322 +  ClpLp::Value ClpLp::_getDual(int i) const {
   1.323 +    return _prob->dualRowSolution()[i];
   1.324 +  }
   1.325 +
   1.326 +  ClpLp::Value ClpLp::_getPrimalRay(int i) const {
   1.327 +    if (!_primal_ray) {
   1.328 +      _primal_ray = _prob->unboundedRay();
   1.329 +      LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
   1.330 +    }
   1.331 +    return _primal_ray[i];
   1.332 +  }
   1.333 +
   1.334 +  ClpLp::Value ClpLp::_getDualRay(int i) const {
   1.335 +    if (!_dual_ray) {
   1.336 +      _dual_ray = _prob->infeasibilityRay();
   1.337 +      LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
   1.338 +    }
   1.339 +    return _dual_ray[i];
   1.340 +  }
   1.341 +
   1.342 +  ClpLp::VarStatus ClpLp::_getColStatus(int i) const {
   1.343 +    switch (_prob->getColumnStatus(i)) {
   1.344 +    case ClpSimplex::basic:
   1.345 +      return BASIC;
   1.346 +    case ClpSimplex::isFree:
   1.347 +      return FREE;
   1.348 +    case ClpSimplex::atUpperBound:
   1.349 +      return UPPER;
   1.350 +    case ClpSimplex::atLowerBound:
   1.351 +      return LOWER;
   1.352 +    case ClpSimplex::isFixed:
   1.353 +      return FIXED;
   1.354 +    case ClpSimplex::superBasic:
   1.355 +      return FREE;
   1.356 +    default:
   1.357 +      LEMON_ASSERT(false, "Wrong column status");
   1.358 +      return VarStatus();
   1.359 +    }
   1.360 +  }
   1.361 +
   1.362 +  ClpLp::VarStatus ClpLp::_getRowStatus(int i) const {
   1.363 +    switch (_prob->getColumnStatus(i)) {
   1.364 +    case ClpSimplex::basic:
   1.365 +      return BASIC;
   1.366 +    case ClpSimplex::isFree:
   1.367 +      return FREE;
   1.368 +    case ClpSimplex::atUpperBound:
   1.369 +      return UPPER;
   1.370 +    case ClpSimplex::atLowerBound:
   1.371 +      return LOWER;
   1.372 +    case ClpSimplex::isFixed:
   1.373 +      return FIXED;
   1.374 +    case ClpSimplex::superBasic:
   1.375 +      return FREE;
   1.376 +    default:
   1.377 +      LEMON_ASSERT(false, "Wrong row status");
   1.378 +      return VarStatus();
   1.379 +    }
   1.380 +  }
   1.381 +
   1.382 +
   1.383 +  ClpLp::ProblemType ClpLp::_getPrimalType() const {
   1.384 +    if (_prob->isProvenOptimal()) {
   1.385 +      return OPTIMAL;
   1.386 +    } else if (_prob->isProvenPrimalInfeasible()) {
   1.387 +      return INFEASIBLE;
   1.388 +    } else if (_prob->isProvenDualInfeasible()) {
   1.389 +      return UNBOUNDED;
   1.390 +    } else {
   1.391 +      return UNDEFINED;
   1.392 +    }
   1.393 +  }
   1.394 +
   1.395 +  ClpLp::ProblemType ClpLp::_getDualType() const {
   1.396 +    if (_prob->isProvenOptimal()) {
   1.397 +      return OPTIMAL;
   1.398 +    } else if (_prob->isProvenDualInfeasible()) {
   1.399 +      return INFEASIBLE;
   1.400 +    } else if (_prob->isProvenPrimalInfeasible()) {
   1.401 +      return INFEASIBLE;
   1.402 +    } else {
   1.403 +      return UNDEFINED;
   1.404 +    }
   1.405 +  }
   1.406 +
   1.407 +  void ClpLp::_setSense(ClpLp::Sense sense) {
   1.408 +    switch (sense) {
   1.409 +    case MIN:
   1.410 +      _prob->setOptimizationDirection(1);
   1.411 +      break;
   1.412 +    case MAX:
   1.413 +      _prob->setOptimizationDirection(-1);
   1.414 +      break;
   1.415 +    }
   1.416 +  }
   1.417 +
   1.418 +  ClpLp::Sense ClpLp::_getSense() const {
   1.419 +    double dir = _prob->optimizationDirection();
   1.420 +    if (dir > 0.0) {
   1.421 +      return MIN;
   1.422 +    } else {
   1.423 +      return MAX;
   1.424 +    }
   1.425 +  }
   1.426 +
   1.427 +  void ClpLp::_clear() {
   1.428 +    delete _prob;
   1.429 +    _prob = new ClpSimplex();
   1.430 +    rows.clear();
   1.431 +    cols.clear();
   1.432 +    _col_names_ref.clear();
   1.433 +    _clear_temporals();
   1.434 +  }
   1.435 +
   1.436 +  void ClpLp::_messageLevel(MessageLevel level) {
   1.437 +    switch (level) {
   1.438 +    case MESSAGE_NOTHING:
   1.439 +      _prob->setLogLevel(0);
   1.440 +      break;
   1.441 +    case MESSAGE_ERROR:
   1.442 +      _prob->setLogLevel(1);
   1.443 +      break;
   1.444 +    case MESSAGE_WARNING:
   1.445 +      _prob->setLogLevel(2);
   1.446 +      break;
   1.447 +    case MESSAGE_NORMAL:
   1.448 +      _prob->setLogLevel(3);
   1.449 +      break;
   1.450 +    case MESSAGE_VERBOSE:
   1.451 +      _prob->setLogLevel(4);
   1.452 +      break;
   1.453 +    }
   1.454 +  }
   1.455 +
   1.456 +} //END OF NAMESPACE LEMON