lemon/soplex.cc
changeset 802 994c7df296c9
parent 540 9db62975c32b
child 746 e4554cd6b2bf
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/soplex.cc	Thu Dec 10 17:05:35 2009 +0100
     1.3 @@ -0,0 +1,452 @@
     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 <iostream>
    1.23 +#include <lemon/soplex.h>
    1.24 +
    1.25 +#include <soplex.h>
    1.26 +#include <spxout.h>
    1.27 +
    1.28 +
    1.29 +///\file
    1.30 +///\brief Implementation of the LEMON-SOPLEX lp solver interface.
    1.31 +namespace lemon {
    1.32 +
    1.33 +  SoplexLp::SoplexLp() {
    1.34 +    soplex = new soplex::SoPlex;
    1.35 +    messageLevel(MESSAGE_NOTHING);
    1.36 +  }
    1.37 +
    1.38 +  SoplexLp::~SoplexLp() {
    1.39 +    delete soplex;
    1.40 +  }
    1.41 +
    1.42 +  SoplexLp::SoplexLp(const SoplexLp& lp) {
    1.43 +    rows = lp.rows;
    1.44 +    cols = lp.cols;
    1.45 +
    1.46 +    soplex = new soplex::SoPlex;
    1.47 +    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
    1.48 +
    1.49 +    _col_names = lp._col_names;
    1.50 +    _col_names_ref = lp._col_names_ref;
    1.51 +
    1.52 +    _row_names = lp._row_names;
    1.53 +    _row_names_ref = lp._row_names_ref;
    1.54 +
    1.55 +    messageLevel(MESSAGE_NOTHING);
    1.56 +  }
    1.57 +
    1.58 +  void SoplexLp::_clear_temporals() {
    1.59 +    _primal_values.clear();
    1.60 +    _dual_values.clear();
    1.61 +  }
    1.62 +
    1.63 +  SoplexLp* SoplexLp::newSolver() const {
    1.64 +    SoplexLp* newlp = new SoplexLp();
    1.65 +    return newlp;
    1.66 +  }
    1.67 +
    1.68 +  SoplexLp* SoplexLp::cloneSolver() const {
    1.69 +    SoplexLp* newlp = new SoplexLp(*this);
    1.70 +    return newlp;
    1.71 +  }
    1.72 +
    1.73 +  const char* SoplexLp::_solverName() const { return "SoplexLp"; }
    1.74 +
    1.75 +  int SoplexLp::_addCol() {
    1.76 +    soplex::LPCol c;
    1.77 +    c.setLower(-soplex::infinity);
    1.78 +    c.setUpper(soplex::infinity);
    1.79 +    soplex->addCol(c);
    1.80 +
    1.81 +    _col_names.push_back(std::string());
    1.82 +
    1.83 +    return soplex->nCols() - 1;
    1.84 +  }
    1.85 +
    1.86 +  int SoplexLp::_addRow() {
    1.87 +    soplex::LPRow r;
    1.88 +    r.setLhs(-soplex::infinity);
    1.89 +    r.setRhs(soplex::infinity);
    1.90 +    soplex->addRow(r);
    1.91 +
    1.92 +    _row_names.push_back(std::string());
    1.93 +
    1.94 +    return soplex->nRows() - 1;
    1.95 +  }
    1.96 +
    1.97 +
    1.98 +  void SoplexLp::_eraseCol(int i) {
    1.99 +    soplex->removeCol(i);
   1.100 +    _col_names_ref.erase(_col_names[i]);
   1.101 +    _col_names[i] = _col_names.back();
   1.102 +    _col_names_ref[_col_names.back()] = i;
   1.103 +    _col_names.pop_back();
   1.104 +  }
   1.105 +
   1.106 +  void SoplexLp::_eraseRow(int i) {
   1.107 +    soplex->removeRow(i);
   1.108 +    _row_names_ref.erase(_row_names[i]);
   1.109 +    _row_names[i] = _row_names.back();
   1.110 +    _row_names_ref[_row_names.back()] = i;
   1.111 +    _row_names.pop_back();
   1.112 +  }
   1.113 +
   1.114 +  void SoplexLp::_eraseColId(int i) {
   1.115 +    cols.eraseIndex(i);
   1.116 +    cols.relocateIndex(i, cols.maxIndex());
   1.117 +  }
   1.118 +  void SoplexLp::_eraseRowId(int i) {
   1.119 +    rows.eraseIndex(i);
   1.120 +    rows.relocateIndex(i, rows.maxIndex());
   1.121 +  }
   1.122 +
   1.123 +  void SoplexLp::_getColName(int c, std::string &name) const {
   1.124 +    name = _col_names[c];
   1.125 +  }
   1.126 +
   1.127 +  void SoplexLp::_setColName(int c, const std::string &name) {
   1.128 +    _col_names_ref.erase(_col_names[c]);
   1.129 +    _col_names[c] = name;
   1.130 +    if (!name.empty()) {
   1.131 +      _col_names_ref.insert(std::make_pair(name, c));
   1.132 +    }
   1.133 +  }
   1.134 +
   1.135 +  int SoplexLp::_colByName(const std::string& name) const {
   1.136 +    std::map<std::string, int>::const_iterator it =
   1.137 +      _col_names_ref.find(name);
   1.138 +    if (it != _col_names_ref.end()) {
   1.139 +      return it->second;
   1.140 +    } else {
   1.141 +      return -1;
   1.142 +    }
   1.143 +  }
   1.144 +
   1.145 +  void SoplexLp::_getRowName(int r, std::string &name) const {
   1.146 +    name = _row_names[r];
   1.147 +  }
   1.148 +
   1.149 +  void SoplexLp::_setRowName(int r, const std::string &name) {
   1.150 +    _row_names_ref.erase(_row_names[r]);
   1.151 +    _row_names[r] = name;
   1.152 +    if (!name.empty()) {
   1.153 +      _row_names_ref.insert(std::make_pair(name, r));
   1.154 +    }
   1.155 +  }
   1.156 +
   1.157 +  int SoplexLp::_rowByName(const std::string& name) const {
   1.158 +    std::map<std::string, int>::const_iterator it =
   1.159 +      _row_names_ref.find(name);
   1.160 +    if (it != _row_names_ref.end()) {
   1.161 +      return it->second;
   1.162 +    } else {
   1.163 +      return -1;
   1.164 +    }
   1.165 +  }
   1.166 +
   1.167 +
   1.168 +  void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
   1.169 +    for (int j = 0; j < soplex->nCols(); ++j) {
   1.170 +      soplex->changeElement(i, j, 0.0);
   1.171 +    }
   1.172 +    for(ExprIterator it = b; it != e; ++it) {
   1.173 +      soplex->changeElement(i, it->first, it->second);
   1.174 +    }
   1.175 +  }
   1.176 +
   1.177 +  void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
   1.178 +    const soplex::SVector& vec = soplex->rowVector(i);
   1.179 +    for (int k = 0; k < vec.size(); ++k) {
   1.180 +      *b = std::make_pair(vec.index(k), vec.value(k));
   1.181 +      ++b;
   1.182 +    }
   1.183 +  }
   1.184 +
   1.185 +  void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
   1.186 +    for (int i = 0; i < soplex->nRows(); ++i) {
   1.187 +      soplex->changeElement(i, j, 0.0);
   1.188 +    }
   1.189 +    for(ExprIterator it = b; it != e; ++it) {
   1.190 +      soplex->changeElement(it->first, j, it->second);
   1.191 +    }
   1.192 +  }
   1.193 +
   1.194 +  void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
   1.195 +    const soplex::SVector& vec = soplex->colVector(i);
   1.196 +    for (int k = 0; k < vec.size(); ++k) {
   1.197 +      *b = std::make_pair(vec.index(k), vec.value(k));
   1.198 +      ++b;
   1.199 +    }
   1.200 +  }
   1.201 +
   1.202 +  void SoplexLp::_setCoeff(int i, int j, Value value) {
   1.203 +    soplex->changeElement(i, j, value);
   1.204 +  }
   1.205 +
   1.206 +  SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
   1.207 +    return soplex->rowVector(i)[j];
   1.208 +  }
   1.209 +
   1.210 +  void SoplexLp::_setColLowerBound(int i, Value value) {
   1.211 +    LEMON_ASSERT(value != INF, "Invalid bound");
   1.212 +    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
   1.213 +  }
   1.214 +
   1.215 +  SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
   1.216 +    double value = soplex->lower(i);
   1.217 +    return value != -soplex::infinity ? value : -INF;
   1.218 +  }
   1.219 +
   1.220 +  void SoplexLp::_setColUpperBound(int i, Value value) {
   1.221 +    LEMON_ASSERT(value != -INF, "Invalid bound");
   1.222 +    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
   1.223 +  }
   1.224 +
   1.225 +  SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
   1.226 +    double value = soplex->upper(i);
   1.227 +    return value != soplex::infinity ? value : INF;
   1.228 +  }
   1.229 +
   1.230 +  void SoplexLp::_setRowLowerBound(int i, Value lb) {
   1.231 +    LEMON_ASSERT(lb != INF, "Invalid bound");
   1.232 +    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
   1.233 +  }
   1.234 +
   1.235 +  SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
   1.236 +    double res = soplex->lhs(i);
   1.237 +    return res == -soplex::infinity ? -INF : res;
   1.238 +  }
   1.239 +
   1.240 +  void SoplexLp::_setRowUpperBound(int i, Value ub) {
   1.241 +    LEMON_ASSERT(ub != -INF, "Invalid bound");
   1.242 +    soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
   1.243 +  }
   1.244 +
   1.245 +  SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
   1.246 +    double res = soplex->rhs(i);
   1.247 +    return res == soplex::infinity ? INF : res;
   1.248 +  }
   1.249 +
   1.250 +  void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
   1.251 +    for (int j = 0; j < soplex->nCols(); ++j) {
   1.252 +      soplex->changeObj(j, 0.0);
   1.253 +    }
   1.254 +    for (ExprIterator it = b; it != e; ++it) {
   1.255 +      soplex->changeObj(it->first, it->second);
   1.256 +    }
   1.257 +  }
   1.258 +
   1.259 +  void SoplexLp::_getObjCoeffs(InsertIterator b) const {
   1.260 +    for (int j = 0; j < soplex->nCols(); ++j) {
   1.261 +      Value coef = soplex->obj(j);
   1.262 +      if (coef != 0.0) {
   1.263 +        *b = std::make_pair(j, coef);
   1.264 +        ++b;
   1.265 +      }
   1.266 +    }
   1.267 +  }
   1.268 +
   1.269 +  void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
   1.270 +    soplex->changeObj(i, obj_coef);
   1.271 +  }
   1.272 +
   1.273 +  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
   1.274 +    return soplex->obj(i);
   1.275 +  }
   1.276 +
   1.277 +  SoplexLp::SolveExitStatus SoplexLp::_solve() {
   1.278 +
   1.279 +    _clear_temporals();
   1.280 +    
   1.281 +    _applyMessageLevel();
   1.282 +
   1.283 +    soplex::SPxSolver::Status status = soplex->solve();
   1.284 +
   1.285 +    switch (status) {
   1.286 +    case soplex::SPxSolver::OPTIMAL:
   1.287 +    case soplex::SPxSolver::INFEASIBLE:
   1.288 +    case soplex::SPxSolver::UNBOUNDED:
   1.289 +      return SOLVED;
   1.290 +    default:
   1.291 +      return UNSOLVED;
   1.292 +    }
   1.293 +  }
   1.294 +
   1.295 +  SoplexLp::Value SoplexLp::_getPrimal(int i) const {
   1.296 +    if (_primal_values.empty()) {
   1.297 +      _primal_values.resize(soplex->nCols());
   1.298 +      soplex::Vector pv(_primal_values.size(), &_primal_values.front());
   1.299 +      soplex->getPrimal(pv);
   1.300 +    }
   1.301 +    return _primal_values[i];
   1.302 +  }
   1.303 +
   1.304 +  SoplexLp::Value SoplexLp::_getDual(int i) const {
   1.305 +    if (_dual_values.empty()) {
   1.306 +      _dual_values.resize(soplex->nRows());
   1.307 +      soplex::Vector dv(_dual_values.size(), &_dual_values.front());
   1.308 +      soplex->getDual(dv);
   1.309 +    }
   1.310 +    return _dual_values[i];
   1.311 +  }
   1.312 +
   1.313 +  SoplexLp::Value SoplexLp::_getPrimalValue() const {
   1.314 +    return soplex->objValue();
   1.315 +  }
   1.316 +
   1.317 +  SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
   1.318 +    switch (soplex->getBasisColStatus(i)) {
   1.319 +    case soplex::SPxSolver::BASIC:
   1.320 +      return BASIC;
   1.321 +    case soplex::SPxSolver::ON_UPPER:
   1.322 +      return UPPER;
   1.323 +    case soplex::SPxSolver::ON_LOWER:
   1.324 +      return LOWER;
   1.325 +    case soplex::SPxSolver::FIXED:
   1.326 +      return FIXED;
   1.327 +    case soplex::SPxSolver::ZERO:
   1.328 +      return FREE;
   1.329 +    default:
   1.330 +      LEMON_ASSERT(false, "Wrong column status");
   1.331 +      return VarStatus();
   1.332 +    }
   1.333 +  }
   1.334 +
   1.335 +  SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
   1.336 +    switch (soplex->getBasisRowStatus(i)) {
   1.337 +    case soplex::SPxSolver::BASIC:
   1.338 +      return BASIC;
   1.339 +    case soplex::SPxSolver::ON_UPPER:
   1.340 +      return UPPER;
   1.341 +    case soplex::SPxSolver::ON_LOWER:
   1.342 +      return LOWER;
   1.343 +    case soplex::SPxSolver::FIXED:
   1.344 +      return FIXED;
   1.345 +    case soplex::SPxSolver::ZERO:
   1.346 +      return FREE;
   1.347 +    default:
   1.348 +      LEMON_ASSERT(false, "Wrong row status");
   1.349 +      return VarStatus();
   1.350 +    }
   1.351 +  }
   1.352 +
   1.353 +  SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
   1.354 +    if (_primal_ray.empty()) {
   1.355 +      _primal_ray.resize(soplex->nCols());
   1.356 +      soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
   1.357 +      soplex->getDualfarkas(pv);
   1.358 +    }
   1.359 +    return _primal_ray[i];
   1.360 +  }
   1.361 +
   1.362 +  SoplexLp::Value SoplexLp::_getDualRay(int i) const {
   1.363 +    if (_dual_ray.empty()) {
   1.364 +      _dual_ray.resize(soplex->nRows());
   1.365 +      soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
   1.366 +      soplex->getDualfarkas(dv);
   1.367 +    }
   1.368 +    return _dual_ray[i];
   1.369 +  }
   1.370 +
   1.371 +  SoplexLp::ProblemType SoplexLp::_getPrimalType() const {
   1.372 +    switch (soplex->status()) {
   1.373 +    case soplex::SPxSolver::OPTIMAL:
   1.374 +      return OPTIMAL;
   1.375 +    case soplex::SPxSolver::UNBOUNDED:
   1.376 +      return UNBOUNDED;
   1.377 +    case soplex::SPxSolver::INFEASIBLE:
   1.378 +      return INFEASIBLE;
   1.379 +    default:
   1.380 +      return UNDEFINED;
   1.381 +    }
   1.382 +  }
   1.383 +
   1.384 +  SoplexLp::ProblemType SoplexLp::_getDualType() const {
   1.385 +    switch (soplex->status()) {
   1.386 +    case soplex::SPxSolver::OPTIMAL:
   1.387 +      return OPTIMAL;
   1.388 +    case soplex::SPxSolver::UNBOUNDED:
   1.389 +      return UNBOUNDED;
   1.390 +    case soplex::SPxSolver::INFEASIBLE:
   1.391 +      return INFEASIBLE;
   1.392 +    default:
   1.393 +      return UNDEFINED;
   1.394 +    }
   1.395 +  }
   1.396 +
   1.397 +  void SoplexLp::_setSense(Sense sense) {
   1.398 +    switch (sense) {
   1.399 +    case MIN:
   1.400 +      soplex->changeSense(soplex::SPxSolver::MINIMIZE);
   1.401 +      break;
   1.402 +    case MAX:
   1.403 +      soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
   1.404 +    }
   1.405 +  }
   1.406 +
   1.407 +  SoplexLp::Sense SoplexLp::_getSense() const {
   1.408 +    switch (soplex->spxSense()) {
   1.409 +    case soplex::SPxSolver::MAXIMIZE:
   1.410 +      return MAX;
   1.411 +    case soplex::SPxSolver::MINIMIZE:
   1.412 +      return MIN;
   1.413 +    default:
   1.414 +      LEMON_ASSERT(false, "Wrong sense.");
   1.415 +      return SoplexLp::Sense();
   1.416 +    }
   1.417 +  }
   1.418 +
   1.419 +  void SoplexLp::_clear() {
   1.420 +    soplex->clear();
   1.421 +    _col_names.clear();
   1.422 +    _col_names_ref.clear();
   1.423 +    _row_names.clear();
   1.424 +    _row_names_ref.clear();
   1.425 +    cols.clear();
   1.426 +    rows.clear();
   1.427 +    _clear_temporals();
   1.428 +  }
   1.429 +
   1.430 +  void SoplexLp::_messageLevel(MessageLevel level) {
   1.431 +    switch (level) {
   1.432 +    case MESSAGE_NOTHING:
   1.433 +      _message_level = -1;
   1.434 +      break;
   1.435 +    case MESSAGE_ERROR:
   1.436 +      _message_level = soplex::SPxOut::ERROR;
   1.437 +      break;
   1.438 +    case MESSAGE_WARNING:
   1.439 +      _message_level = soplex::SPxOut::WARNING;
   1.440 +      break;
   1.441 +    case MESSAGE_NORMAL:
   1.442 +      _message_level = soplex::SPxOut::INFO2;
   1.443 +      break;
   1.444 +    case MESSAGE_VERBOSE:
   1.445 +      _message_level = soplex::SPxOut::DEBUG;
   1.446 +      break;
   1.447 +    }
   1.448 +  }
   1.449 +
   1.450 +  void SoplexLp::_applyMessageLevel() {
   1.451 +    soplex::Param::setVerbose(_message_level);
   1.452 +  }
   1.453 +
   1.454 +} //namespace lemon
   1.455 +