lemon/soplex.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 29 Sep 2009 09:25:00 +0200
changeset 732 1f8ad32f088b
parent 540 9db62975c32b
child 746 e4554cd6b2bf
permissions -rw-r--r--
Simple interactive bootstrap script
     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.h>
    23 #include <spxout.h>
    24 
    25 
    26 ///\file
    27 ///\brief Implementation of the LEMON-SOPLEX lp solver interface.
    28 namespace lemon {
    29 
    30   SoplexLp::SoplexLp() {
    31     soplex = new soplex::SoPlex;
    32     messageLevel(MESSAGE_NOTHING);
    33   }
    34 
    35   SoplexLp::~SoplexLp() {
    36     delete soplex;
    37   }
    38 
    39   SoplexLp::SoplexLp(const SoplexLp& lp) {
    40     rows = lp.rows;
    41     cols = lp.cols;
    42 
    43     soplex = new soplex::SoPlex;
    44     (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
    45 
    46     _col_names = lp._col_names;
    47     _col_names_ref = lp._col_names_ref;
    48 
    49     _row_names = lp._row_names;
    50     _row_names_ref = lp._row_names_ref;
    51 
    52     messageLevel(MESSAGE_NOTHING);
    53   }
    54 
    55   void SoplexLp::_clear_temporals() {
    56     _primal_values.clear();
    57     _dual_values.clear();
    58   }
    59 
    60   SoplexLp* SoplexLp::newSolver() const {
    61     SoplexLp* newlp = new SoplexLp();
    62     return newlp;
    63   }
    64 
    65   SoplexLp* SoplexLp::cloneSolver() const {
    66     SoplexLp* newlp = new SoplexLp(*this);
    67     return newlp;
    68   }
    69 
    70   const char* SoplexLp::_solverName() const { return "SoplexLp"; }
    71 
    72   int SoplexLp::_addCol() {
    73     soplex::LPCol c;
    74     c.setLower(-soplex::infinity);
    75     c.setUpper(soplex::infinity);
    76     soplex->addCol(c);
    77 
    78     _col_names.push_back(std::string());
    79 
    80     return soplex->nCols() - 1;
    81   }
    82 
    83   int SoplexLp::_addRow() {
    84     soplex::LPRow r;
    85     r.setLhs(-soplex::infinity);
    86     r.setRhs(soplex::infinity);
    87     soplex->addRow(r);
    88 
    89     _row_names.push_back(std::string());
    90 
    91     return soplex->nRows() - 1;
    92   }
    93 
    94 
    95   void SoplexLp::_eraseCol(int i) {
    96     soplex->removeCol(i);
    97     _col_names_ref.erase(_col_names[i]);
    98     _col_names[i] = _col_names.back();
    99     _col_names_ref[_col_names.back()] = i;
   100     _col_names.pop_back();
   101   }
   102 
   103   void SoplexLp::_eraseRow(int i) {
   104     soplex->removeRow(i);
   105     _row_names_ref.erase(_row_names[i]);
   106     _row_names[i] = _row_names.back();
   107     _row_names_ref[_row_names.back()] = i;
   108     _row_names.pop_back();
   109   }
   110 
   111   void SoplexLp::_eraseColId(int i) {
   112     cols.eraseIndex(i);
   113     cols.relocateIndex(i, cols.maxIndex());
   114   }
   115   void SoplexLp::_eraseRowId(int i) {
   116     rows.eraseIndex(i);
   117     rows.relocateIndex(i, rows.maxIndex());
   118   }
   119 
   120   void SoplexLp::_getColName(int c, std::string &name) const {
   121     name = _col_names[c];
   122   }
   123 
   124   void SoplexLp::_setColName(int c, const std::string &name) {
   125     _col_names_ref.erase(_col_names[c]);
   126     _col_names[c] = name;
   127     if (!name.empty()) {
   128       _col_names_ref.insert(std::make_pair(name, c));
   129     }
   130   }
   131 
   132   int SoplexLp::_colByName(const std::string& name) const {
   133     std::map<std::string, int>::const_iterator it =
   134       _col_names_ref.find(name);
   135     if (it != _col_names_ref.end()) {
   136       return it->second;
   137     } else {
   138       return -1;
   139     }
   140   }
   141 
   142   void SoplexLp::_getRowName(int r, std::string &name) const {
   143     name = _row_names[r];
   144   }
   145 
   146   void SoplexLp::_setRowName(int r, const std::string &name) {
   147     _row_names_ref.erase(_row_names[r]);
   148     _row_names[r] = name;
   149     if (!name.empty()) {
   150       _row_names_ref.insert(std::make_pair(name, r));
   151     }
   152   }
   153 
   154   int SoplexLp::_rowByName(const std::string& name) const {
   155     std::map<std::string, int>::const_iterator it =
   156       _row_names_ref.find(name);
   157     if (it != _row_names_ref.end()) {
   158       return it->second;
   159     } else {
   160       return -1;
   161     }
   162   }
   163 
   164 
   165   void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
   166     for (int j = 0; j < soplex->nCols(); ++j) {
   167       soplex->changeElement(i, j, 0.0);
   168     }
   169     for(ExprIterator it = b; it != e; ++it) {
   170       soplex->changeElement(i, it->first, it->second);
   171     }
   172   }
   173 
   174   void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
   175     const soplex::SVector& vec = soplex->rowVector(i);
   176     for (int k = 0; k < vec.size(); ++k) {
   177       *b = std::make_pair(vec.index(k), vec.value(k));
   178       ++b;
   179     }
   180   }
   181 
   182   void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
   183     for (int i = 0; i < soplex->nRows(); ++i) {
   184       soplex->changeElement(i, j, 0.0);
   185     }
   186     for(ExprIterator it = b; it != e; ++it) {
   187       soplex->changeElement(it->first, j, it->second);
   188     }
   189   }
   190 
   191   void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
   192     const soplex::SVector& vec = soplex->colVector(i);
   193     for (int k = 0; k < vec.size(); ++k) {
   194       *b = std::make_pair(vec.index(k), vec.value(k));
   195       ++b;
   196     }
   197   }
   198 
   199   void SoplexLp::_setCoeff(int i, int j, Value value) {
   200     soplex->changeElement(i, j, value);
   201   }
   202 
   203   SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
   204     return soplex->rowVector(i)[j];
   205   }
   206 
   207   void SoplexLp::_setColLowerBound(int i, Value value) {
   208     LEMON_ASSERT(value != INF, "Invalid bound");
   209     soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
   210   }
   211 
   212   SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
   213     double value = soplex->lower(i);
   214     return value != -soplex::infinity ? value : -INF;
   215   }
   216 
   217   void SoplexLp::_setColUpperBound(int i, Value value) {
   218     LEMON_ASSERT(value != -INF, "Invalid bound");
   219     soplex->changeUpper(i, value != INF ? value : soplex::infinity);
   220   }
   221 
   222   SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
   223     double value = soplex->upper(i);
   224     return value != soplex::infinity ? value : INF;
   225   }
   226 
   227   void SoplexLp::_setRowLowerBound(int i, Value lb) {
   228     LEMON_ASSERT(lb != INF, "Invalid bound");
   229     soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
   230   }
   231 
   232   SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
   233     double res = soplex->lhs(i);
   234     return res == -soplex::infinity ? -INF : res;
   235   }
   236 
   237   void SoplexLp::_setRowUpperBound(int i, Value ub) {
   238     LEMON_ASSERT(ub != -INF, "Invalid bound");
   239     soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
   240   }
   241 
   242   SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
   243     double res = soplex->rhs(i);
   244     return res == soplex::infinity ? INF : res;
   245   }
   246 
   247   void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
   248     for (int j = 0; j < soplex->nCols(); ++j) {
   249       soplex->changeObj(j, 0.0);
   250     }
   251     for (ExprIterator it = b; it != e; ++it) {
   252       soplex->changeObj(it->first, it->second);
   253     }
   254   }
   255 
   256   void SoplexLp::_getObjCoeffs(InsertIterator b) const {
   257     for (int j = 0; j < soplex->nCols(); ++j) {
   258       Value coef = soplex->obj(j);
   259       if (coef != 0.0) {
   260         *b = std::make_pair(j, coef);
   261         ++b;
   262       }
   263     }
   264   }
   265 
   266   void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
   267     soplex->changeObj(i, obj_coef);
   268   }
   269 
   270   SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
   271     return soplex->obj(i);
   272   }
   273 
   274   SoplexLp::SolveExitStatus SoplexLp::_solve() {
   275 
   276     _clear_temporals();
   277     
   278     _applyMessageLevel();
   279 
   280     soplex::SPxSolver::Status status = soplex->solve();
   281 
   282     switch (status) {
   283     case soplex::SPxSolver::OPTIMAL:
   284     case soplex::SPxSolver::INFEASIBLE:
   285     case soplex::SPxSolver::UNBOUNDED:
   286       return SOLVED;
   287     default:
   288       return UNSOLVED;
   289     }
   290   }
   291 
   292   SoplexLp::Value SoplexLp::_getPrimal(int i) const {
   293     if (_primal_values.empty()) {
   294       _primal_values.resize(soplex->nCols());
   295       soplex::Vector pv(_primal_values.size(), &_primal_values.front());
   296       soplex->getPrimal(pv);
   297     }
   298     return _primal_values[i];
   299   }
   300 
   301   SoplexLp::Value SoplexLp::_getDual(int i) const {
   302     if (_dual_values.empty()) {
   303       _dual_values.resize(soplex->nRows());
   304       soplex::Vector dv(_dual_values.size(), &_dual_values.front());
   305       soplex->getDual(dv);
   306     }
   307     return _dual_values[i];
   308   }
   309 
   310   SoplexLp::Value SoplexLp::_getPrimalValue() const {
   311     return soplex->objValue();
   312   }
   313 
   314   SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
   315     switch (soplex->getBasisColStatus(i)) {
   316     case soplex::SPxSolver::BASIC:
   317       return BASIC;
   318     case soplex::SPxSolver::ON_UPPER:
   319       return UPPER;
   320     case soplex::SPxSolver::ON_LOWER:
   321       return LOWER;
   322     case soplex::SPxSolver::FIXED:
   323       return FIXED;
   324     case soplex::SPxSolver::ZERO:
   325       return FREE;
   326     default:
   327       LEMON_ASSERT(false, "Wrong column status");
   328       return VarStatus();
   329     }
   330   }
   331 
   332   SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
   333     switch (soplex->getBasisRowStatus(i)) {
   334     case soplex::SPxSolver::BASIC:
   335       return BASIC;
   336     case soplex::SPxSolver::ON_UPPER:
   337       return UPPER;
   338     case soplex::SPxSolver::ON_LOWER:
   339       return LOWER;
   340     case soplex::SPxSolver::FIXED:
   341       return FIXED;
   342     case soplex::SPxSolver::ZERO:
   343       return FREE;
   344     default:
   345       LEMON_ASSERT(false, "Wrong row status");
   346       return VarStatus();
   347     }
   348   }
   349 
   350   SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
   351     if (_primal_ray.empty()) {
   352       _primal_ray.resize(soplex->nCols());
   353       soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
   354       soplex->getDualfarkas(pv);
   355     }
   356     return _primal_ray[i];
   357   }
   358 
   359   SoplexLp::Value SoplexLp::_getDualRay(int i) const {
   360     if (_dual_ray.empty()) {
   361       _dual_ray.resize(soplex->nRows());
   362       soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
   363       soplex->getDualfarkas(dv);
   364     }
   365     return _dual_ray[i];
   366   }
   367 
   368   SoplexLp::ProblemType SoplexLp::_getPrimalType() const {
   369     switch (soplex->status()) {
   370     case soplex::SPxSolver::OPTIMAL:
   371       return OPTIMAL;
   372     case soplex::SPxSolver::UNBOUNDED:
   373       return UNBOUNDED;
   374     case soplex::SPxSolver::INFEASIBLE:
   375       return INFEASIBLE;
   376     default:
   377       return UNDEFINED;
   378     }
   379   }
   380 
   381   SoplexLp::ProblemType SoplexLp::_getDualType() const {
   382     switch (soplex->status()) {
   383     case soplex::SPxSolver::OPTIMAL:
   384       return OPTIMAL;
   385     case soplex::SPxSolver::UNBOUNDED:
   386       return UNBOUNDED;
   387     case soplex::SPxSolver::INFEASIBLE:
   388       return INFEASIBLE;
   389     default:
   390       return UNDEFINED;
   391     }
   392   }
   393 
   394   void SoplexLp::_setSense(Sense sense) {
   395     switch (sense) {
   396     case MIN:
   397       soplex->changeSense(soplex::SPxSolver::MINIMIZE);
   398       break;
   399     case MAX:
   400       soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
   401     }
   402   }
   403 
   404   SoplexLp::Sense SoplexLp::_getSense() const {
   405     switch (soplex->spxSense()) {
   406     case soplex::SPxSolver::MAXIMIZE:
   407       return MAX;
   408     case soplex::SPxSolver::MINIMIZE:
   409       return MIN;
   410     default:
   411       LEMON_ASSERT(false, "Wrong sense.");
   412       return SoplexLp::Sense();
   413     }
   414   }
   415 
   416   void SoplexLp::_clear() {
   417     soplex->clear();
   418     _col_names.clear();
   419     _col_names_ref.clear();
   420     _row_names.clear();
   421     _row_names_ref.clear();
   422     cols.clear();
   423     rows.clear();
   424     _clear_temporals();
   425   }
   426 
   427   void SoplexLp::_messageLevel(MessageLevel level) {
   428     switch (level) {
   429     case MESSAGE_NOTHING:
   430       _message_level = -1;
   431       break;
   432     case MESSAGE_ERROR:
   433       _message_level = soplex::SPxOut::ERROR;
   434       break;
   435     case MESSAGE_WARNING:
   436       _message_level = soplex::SPxOut::WARNING;
   437       break;
   438     case MESSAGE_NORMAL:
   439       _message_level = soplex::SPxOut::INFO2;
   440       break;
   441     case MESSAGE_VERBOSE:
   442       _message_level = soplex::SPxOut::DEBUG;
   443       break;
   444     }
   445   }
   446 
   447   void SoplexLp::_applyMessageLevel() {
   448     soplex::Param::setVerbose(_message_level);
   449   }
   450 
   451 } //namespace lemon
   452