lemon/lp_clp.cc
changeset 459 ed54c0d13df0
equal deleted inserted replaced
-1:000000000000 0:538ddd7d76b1
       
     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 <lemon/lp_clp.h>
       
    20 #include <coin/ClpSimplex.hpp>
       
    21 
       
    22 namespace lemon {
       
    23 
       
    24   LpClp::LpClp() {
       
    25     _prob = new ClpSimplex();
       
    26     _init_temporals();
       
    27     messageLevel(MESSAGE_NO_OUTPUT);
       
    28   }
       
    29 
       
    30   LpClp::LpClp(const LpClp& other) {
       
    31     _prob = new ClpSimplex(*other._prob);
       
    32     rows = other.rows;
       
    33     cols = other.cols;
       
    34     _init_temporals();
       
    35     messageLevel(MESSAGE_NO_OUTPUT);
       
    36   }
       
    37 
       
    38   LpClp::~LpClp() {
       
    39     delete _prob;
       
    40     _clear_temporals();
       
    41   }
       
    42 
       
    43   void LpClp::_init_temporals() {
       
    44     _primal_ray = 0;
       
    45     _dual_ray = 0;
       
    46   }
       
    47 
       
    48   void LpClp::_clear_temporals() {
       
    49     if (_primal_ray) {
       
    50       delete[] _primal_ray;
       
    51       _primal_ray = 0;
       
    52     }
       
    53     if (_dual_ray) {
       
    54       delete[] _dual_ray;
       
    55       _dual_ray = 0;
       
    56     }
       
    57   }
       
    58 
       
    59   LpClp* LpClp::_newSolver() const {
       
    60     LpClp* newlp = new LpClp;
       
    61     return newlp;
       
    62   }
       
    63 
       
    64   LpClp* LpClp::_cloneSolver() const {
       
    65     LpClp* copylp = new LpClp(*this);
       
    66     return copylp;
       
    67   }
       
    68 
       
    69   const char* LpClp::_solverName() const { return "LpClp"; }
       
    70 
       
    71   int LpClp::_addCol() {
       
    72     _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
       
    73     return _prob->numberColumns() - 1;
       
    74   }
       
    75 
       
    76   int LpClp::_addRow() {
       
    77     _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
       
    78     return _prob->numberRows() - 1;
       
    79   }
       
    80 
       
    81 
       
    82   void LpClp::_eraseCol(int c) {
       
    83     _col_names_ref.erase(_prob->getColumnName(c));
       
    84     _prob->deleteColumns(1, &c);
       
    85   }
       
    86 
       
    87   void LpClp::_eraseRow(int r) {
       
    88     _row_names_ref.erase(_prob->getRowName(r));
       
    89     _prob->deleteRows(1, &r);
       
    90   }
       
    91 
       
    92   void LpClp::_eraseColId(int i) {
       
    93     cols.eraseIndex(i);
       
    94     cols.shiftIndices(i);
       
    95   }
       
    96 
       
    97   void LpClp::_eraseRowId(int i) {
       
    98     rows.eraseIndex(i);
       
    99     rows.shiftIndices(i);
       
   100   }
       
   101 
       
   102   void LpClp::_getColName(int c, std::string& name) const {
       
   103     name = _prob->getColumnName(c);
       
   104   }
       
   105 
       
   106   void LpClp::_setColName(int c, const std::string& name) {
       
   107     _prob->setColumnName(c, const_cast<std::string&>(name));
       
   108     _col_names_ref[name] = c;
       
   109   }
       
   110 
       
   111   int LpClp::_colByName(const std::string& name) const {
       
   112     std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
       
   113     return it != _col_names_ref.end() ? it->second : -1;
       
   114   }
       
   115 
       
   116   void LpClp::_getRowName(int r, std::string& name) const {
       
   117     name = _prob->getRowName(r);
       
   118   }
       
   119 
       
   120   void LpClp::_setRowName(int r, const std::string& name) {
       
   121     _prob->setRowName(r, const_cast<std::string&>(name));
       
   122     _row_names_ref[name] = r;
       
   123   }
       
   124 
       
   125   int LpClp::_rowByName(const std::string& name) const {
       
   126     std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
       
   127     return it != _row_names_ref.end() ? it->second : -1;
       
   128   }
       
   129 
       
   130 
       
   131   void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
       
   132     std::map<int, Value> coeffs;
       
   133 
       
   134     int n = _prob->clpMatrix()->getNumCols();
       
   135 
       
   136     const int* indices = _prob->clpMatrix()->getIndices();
       
   137     const double* elements = _prob->clpMatrix()->getElements();
       
   138 
       
   139     for (int i = 0; i < n; ++i) {
       
   140       CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
       
   141       CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
       
   142 
       
   143       const int* it = std::lower_bound(indices + begin, indices + end, ix);
       
   144       if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
       
   145         coeffs[i] = 0.0;
       
   146       }
       
   147     }
       
   148 
       
   149     for (ExprIterator it = b; it != e; ++it) {
       
   150       coeffs[it->first] = it->second;
       
   151     }
       
   152 
       
   153     for (std::map<int, Value>::iterator it = coeffs.begin();
       
   154          it != coeffs.end(); ++it) {
       
   155       _prob->modifyCoefficient(ix, it->first, it->second);
       
   156     }
       
   157   }
       
   158 
       
   159   void LpClp::_getRowCoeffs(int ix, InsertIterator b) const {
       
   160     int n = _prob->clpMatrix()->getNumCols();
       
   161 
       
   162     const int* indices = _prob->clpMatrix()->getIndices();
       
   163     const double* elements = _prob->clpMatrix()->getElements();
       
   164 
       
   165     for (int i = 0; i < n; ++i) {
       
   166       CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
       
   167       CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
       
   168 
       
   169       const int* it = std::lower_bound(indices + begin, indices + end, ix);
       
   170       if (it != indices + end && *it == ix) {
       
   171         *b = std::make_pair(i, elements[it - indices]);
       
   172       }
       
   173     }
       
   174   }
       
   175 
       
   176   void LpClp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
       
   177     std::map<int, Value> coeffs;
       
   178 
       
   179     CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
       
   180     CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
       
   181 
       
   182     const int* indices = _prob->clpMatrix()->getIndices();
       
   183     const double* elements = _prob->clpMatrix()->getElements();
       
   184 
       
   185     for (CoinBigIndex i = begin; i != end; ++i) {
       
   186       if (elements[i] != 0.0) {
       
   187         coeffs[indices[i]] = 0.0;
       
   188       }
       
   189     }
       
   190     for (ExprIterator it = b; it != e; ++it) {
       
   191       coeffs[it->first] = it->second;
       
   192     }
       
   193     for (std::map<int, Value>::iterator it = coeffs.begin();
       
   194          it != coeffs.end(); ++it) {
       
   195       _prob->modifyCoefficient(it->first, ix, it->second);
       
   196     }
       
   197   }
       
   198 
       
   199   void LpClp::_getColCoeffs(int ix, InsertIterator b) const {
       
   200     CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
       
   201     CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
       
   202 
       
   203     const int* indices = _prob->clpMatrix()->getIndices();
       
   204     const double* elements = _prob->clpMatrix()->getElements();
       
   205 
       
   206     for (CoinBigIndex i = begin; i != end; ++i) {
       
   207       *b = std::make_pair(indices[i], elements[i]);
       
   208       ++b;
       
   209     }
       
   210   }
       
   211 
       
   212   void LpClp::_setCoeff(int ix, int jx, Value value) {
       
   213     _prob->modifyCoefficient(ix, jx, value);
       
   214   }
       
   215 
       
   216   LpClp::Value LpClp::_getCoeff(int ix, int jx) const {
       
   217     CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
       
   218     CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
       
   219 
       
   220     const int* indices = _prob->clpMatrix()->getIndices();
       
   221     const double* elements = _prob->clpMatrix()->getElements();
       
   222 
       
   223     const int* it = std::lower_bound(indices + begin, indices + end, jx);
       
   224     if (it != indices + end && *it == jx) {
       
   225       return elements[it - indices];
       
   226     } else {
       
   227       return 0.0;
       
   228     }
       
   229   }
       
   230 
       
   231   void LpClp::_setColLowerBound(int i, Value lo) {
       
   232     _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
       
   233   }
       
   234 
       
   235   LpClp::Value LpClp::_getColLowerBound(int i) const {
       
   236     double val = _prob->getColLower()[i];
       
   237     return val == - COIN_DBL_MAX ? - INF : val;
       
   238   }
       
   239 
       
   240   void LpClp::_setColUpperBound(int i, Value up) {
       
   241     _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
       
   242   }
       
   243 
       
   244   LpClp::Value LpClp::_getColUpperBound(int i) const {
       
   245     double val = _prob->getColUpper()[i];
       
   246     return val == COIN_DBL_MAX ? INF : val;
       
   247   }
       
   248 
       
   249   void LpClp::_setRowLowerBound(int i, Value lo) {
       
   250     _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
       
   251   }
       
   252 
       
   253   LpClp::Value LpClp::_getRowLowerBound(int i) const {
       
   254     double val = _prob->getRowLower()[i];
       
   255     return val == - COIN_DBL_MAX ? - INF : val;
       
   256   }
       
   257 
       
   258   void LpClp::_setRowUpperBound(int i, Value up) {
       
   259     _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
       
   260   }
       
   261 
       
   262   LpClp::Value LpClp::_getRowUpperBound(int i) const {
       
   263     double val = _prob->getRowUpper()[i];
       
   264     return val == COIN_DBL_MAX ? INF : val;
       
   265   }
       
   266 
       
   267   void LpClp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
       
   268     int num = _prob->clpMatrix()->getNumCols();
       
   269     for (int i = 0; i < num; ++i) {
       
   270       _prob->setObjectiveCoefficient(i, 0.0);
       
   271     }
       
   272     for (ExprIterator it = b; it != e; ++it) {
       
   273       _prob->setObjectiveCoefficient(it->first, it->second);
       
   274     }
       
   275   }
       
   276 
       
   277   void LpClp::_getObjCoeffs(InsertIterator b) const {
       
   278     int num = _prob->clpMatrix()->getNumCols();
       
   279     for (int i = 0; i < num; ++i) {
       
   280       Value coef = _prob->getObjCoefficients()[i];
       
   281       if (coef != 0.0) {
       
   282         *b = std::make_pair(i, coef);
       
   283         ++b;
       
   284       }
       
   285     }
       
   286   }
       
   287 
       
   288   void LpClp::_setObjCoeff(int i, Value obj_coef) {
       
   289     _prob->setObjectiveCoefficient(i, obj_coef);
       
   290   }
       
   291 
       
   292   LpClp::Value LpClp::_getObjCoeff(int i) const {
       
   293     return _prob->getObjCoefficients()[i];
       
   294   }
       
   295 
       
   296   LpClp::SolveExitStatus LpClp::_solve() {
       
   297     return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
       
   298   }
       
   299 
       
   300   LpClp::SolveExitStatus LpClp::solvePrimal() {
       
   301     return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
       
   302   }
       
   303 
       
   304   LpClp::SolveExitStatus LpClp::solveDual() {
       
   305     return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
       
   306   }
       
   307 
       
   308   LpClp::SolveExitStatus LpClp::solveBarrier() {
       
   309     return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
       
   310   }
       
   311 
       
   312   LpClp::Value LpClp::_getPrimal(int i) const {
       
   313     return _prob->primalColumnSolution()[i];
       
   314   }
       
   315   LpClp::Value LpClp::_getPrimalValue() const {
       
   316     return _prob->objectiveValue();
       
   317   }
       
   318 
       
   319   LpClp::Value LpClp::_getDual(int i) const {
       
   320     return _prob->dualRowSolution()[i];
       
   321   }
       
   322 
       
   323   LpClp::Value LpClp::_getPrimalRay(int i) const {
       
   324     if (!_primal_ray) {
       
   325       _primal_ray = _prob->unboundedRay();
       
   326       LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
       
   327     }
       
   328     return _primal_ray[i];
       
   329   }
       
   330 
       
   331   LpClp::Value LpClp::_getDualRay(int i) const {
       
   332     if (!_dual_ray) {
       
   333       _dual_ray = _prob->infeasibilityRay();
       
   334       LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
       
   335     }
       
   336     return _dual_ray[i];
       
   337   }
       
   338 
       
   339   LpClp::VarStatus LpClp::_getColStatus(int i) const {
       
   340     switch (_prob->getColumnStatus(i)) {
       
   341     case ClpSimplex::basic:
       
   342       return BASIC;
       
   343     case ClpSimplex::isFree:
       
   344       return FREE;
       
   345     case ClpSimplex::atUpperBound:
       
   346       return UPPER;
       
   347     case ClpSimplex::atLowerBound:
       
   348       return LOWER;
       
   349     case ClpSimplex::isFixed:
       
   350       return FIXED;
       
   351     case ClpSimplex::superBasic:
       
   352       return FREE;
       
   353     default:
       
   354       LEMON_ASSERT(false, "Wrong column status");
       
   355       return VarStatus();
       
   356     }
       
   357   }
       
   358 
       
   359   LpClp::VarStatus LpClp::_getRowStatus(int i) const {
       
   360     switch (_prob->getColumnStatus(i)) {
       
   361     case ClpSimplex::basic:
       
   362       return BASIC;
       
   363     case ClpSimplex::isFree:
       
   364       return FREE;
       
   365     case ClpSimplex::atUpperBound:
       
   366       return UPPER;
       
   367     case ClpSimplex::atLowerBound:
       
   368       return LOWER;
       
   369     case ClpSimplex::isFixed:
       
   370       return FIXED;
       
   371     case ClpSimplex::superBasic:
       
   372       return FREE;
       
   373     default:
       
   374       LEMON_ASSERT(false, "Wrong row status");
       
   375       return VarStatus();
       
   376     }
       
   377   }
       
   378 
       
   379 
       
   380   LpClp::ProblemType LpClp::_getPrimalType() const {
       
   381     if (_prob->isProvenOptimal()) {
       
   382       return OPTIMAL;
       
   383     } else if (_prob->isProvenPrimalInfeasible()) {
       
   384       return INFEASIBLE;
       
   385     } else if (_prob->isProvenDualInfeasible()) {
       
   386       return UNBOUNDED;
       
   387     } else {
       
   388       return UNDEFINED;
       
   389     }
       
   390   }
       
   391 
       
   392   LpClp::ProblemType LpClp::_getDualType() const {
       
   393     if (_prob->isProvenOptimal()) {
       
   394       return OPTIMAL;
       
   395     } else if (_prob->isProvenDualInfeasible()) {
       
   396       return INFEASIBLE;
       
   397     } else if (_prob->isProvenPrimalInfeasible()) {
       
   398       return INFEASIBLE;
       
   399     } else {
       
   400       return UNDEFINED;
       
   401     }
       
   402   }
       
   403 
       
   404   void LpClp::_setSense(LpClp::Sense sense) {
       
   405     switch (sense) {
       
   406     case MIN:
       
   407       _prob->setOptimizationDirection(1);
       
   408       break;
       
   409     case MAX:
       
   410       _prob->setOptimizationDirection(-1);
       
   411       break;
       
   412     }
       
   413   }
       
   414 
       
   415   LpClp::Sense LpClp::_getSense() const {
       
   416     double dir = _prob->optimizationDirection();
       
   417     if (dir > 0.0) {
       
   418       return MIN;
       
   419     } else {
       
   420       return MAX;
       
   421     }
       
   422   }
       
   423 
       
   424   void LpClp::_clear() {
       
   425     delete _prob;
       
   426     _prob = new ClpSimplex();
       
   427     rows.clear();
       
   428     cols.clear();
       
   429     _col_names_ref.clear();
       
   430     _clear_temporals();
       
   431   }
       
   432 
       
   433   void LpClp::messageLevel(MessageLevel m) {
       
   434     _prob->setLogLevel(static_cast<int>(m));
       
   435   }
       
   436 
       
   437 } //END OF NAMESPACE LEMON