lemon/lp_soplex.cc
changeset 461 08d495d48089
parent 458 7afc121e0689
equal deleted inserted replaced
1:439db83f7af5 -1:000000000000
     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/lp_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   LpSoplex::LpSoplex() {
       
    30     soplex = new soplex::SoPlex;
       
    31   }
       
    32 
       
    33   LpSoplex::~LpSoplex() {
       
    34     delete soplex;
       
    35   }
       
    36 
       
    37   LpSoplex::LpSoplex(const LpSoplex& 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 LpSoplex::_clear_temporals() {
       
    53     _primal_values.clear();
       
    54     _dual_values.clear();
       
    55   }
       
    56 
       
    57   LpSoplex* LpSoplex::_newSolver() const {
       
    58     LpSoplex* newlp = new LpSoplex();
       
    59     return newlp;
       
    60   }
       
    61 
       
    62   LpSoplex* LpSoplex::_cloneSolver() const {
       
    63     LpSoplex* newlp = new LpSoplex(*this);
       
    64     return newlp;
       
    65   }
       
    66 
       
    67   const char* LpSoplex::_solverName() const { return "LpSoplex"; }
       
    68 
       
    69   int LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_eraseColId(int i) {
       
   109     cols.eraseIndex(i);
       
   110     cols.relocateIndex(i, cols.maxIndex());
       
   111   }
       
   112   void LpSoplex::_eraseRowId(int i) {
       
   113     rows.eraseIndex(i);
       
   114     rows.relocateIndex(i, rows.maxIndex());
       
   115   }
       
   116 
       
   117   void LpSoplex::_getColName(int c, std::string &name) const {
       
   118     name = _col_names[c];
       
   119   }
       
   120 
       
   121   void LpSoplex::_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 LpSoplex::_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 LpSoplex::_getRowName(int r, std::string &name) const {
       
   140     name = _row_names[r];
       
   141   }
       
   142 
       
   143   void LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_setCoeff(int i, int j, Value value) {
       
   197     soplex->changeElement(i, j, value);
       
   198   }
       
   199 
       
   200   LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
       
   201     return soplex->rowVector(i)[j];
       
   202   }
       
   203 
       
   204   void LpSoplex::_setColLowerBound(int i, Value value) {
       
   205     LEMON_ASSERT(value != INF, "Invalid bound");
       
   206     soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
       
   207   }
       
   208 
       
   209   LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
       
   210     double value = soplex->lower(i);
       
   211     return value != -soplex::infinity ? value : -INF;
       
   212   }
       
   213 
       
   214   void LpSoplex::_setColUpperBound(int i, Value value) {
       
   215     LEMON_ASSERT(value != -INF, "Invalid bound");
       
   216     soplex->changeUpper(i, value != INF ? value : soplex::infinity);
       
   217   }
       
   218 
       
   219   LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
       
   220     double value = soplex->upper(i);
       
   221     return value != soplex::infinity ? value : INF;
       
   222   }
       
   223 
       
   224   void LpSoplex::_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   LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const {
       
   230     double res = soplex->lhs(i);
       
   231     return res == -soplex::infinity ? -INF : res;
       
   232   }
       
   233 
       
   234   void LpSoplex::_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   LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const {
       
   240     double res = soplex->rhs(i);
       
   241     return res == soplex::infinity ? INF : res;
       
   242   }
       
   243 
       
   244   void LpSoplex::_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 LpSoplex::_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 LpSoplex::_setObjCoeff(int i, Value obj_coef) {
       
   264     soplex->changeObj(i, obj_coef);
       
   265   }
       
   266 
       
   267   LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
       
   268     return soplex->obj(i);
       
   269   }
       
   270 
       
   271   LpSoplex::SolveExitStatus LpSoplex::_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   LpSoplex::Value LpSoplex::_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   LpSoplex::Value LpSoplex::_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   LpSoplex::Value LpSoplex::_getPrimalValue() const {
       
   306     return soplex->objValue();
       
   307   }
       
   308 
       
   309   LpSoplex::VarStatus LpSoplex::_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   LpSoplex::VarStatus LpSoplex::_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   LpSoplex::Value LpSoplex::_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   LpSoplex::Value LpSoplex::_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   LpSoplex::ProblemType LpSoplex::_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   LpSoplex::ProblemType LpSoplex::_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 LpSoplex::_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   LpSoplex::Sense LpSoplex::_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 LpSoplex::Sense();
       
   408     }
       
   409   }
       
   410 
       
   411   void LpSoplex::_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