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