lemon/soplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 600 6ac5d9ae1d3d
parent 461 08d495d48089
child 527 547e966b3b29
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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/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