COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 482:ed54c0d13df0 in lemon for lemon/lp_soplex.cc


Ignore:
Timestamp:
12/02/08 22:48:28 (15 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
483:76ec7bd57026, 547:17cabb114d52
Phase:
public
Message:

Thorough redesign of the LP/MIP interface (#44)

  • Redesigned class structure
  • Redesigned iterators
  • Some functions in the basic interface redesigned
  • More complete setting functions
  • Ray retrieving functions
  • Lot of improvements
  • Cplex common env
  • CLP macro definition to config.h.in
  • Update lp.h to also use soplex and clp
  • Remove default_solver_name
  • New solverName() function in solvers
  • Handle exceptions for MipCplex? test
  • Rename tolerance parameter to epsilon
  • Rename MapIt? to CoeffIt?
  • Lot of documentation improvements
  • Various bugfixes
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/lp_soplex.cc

    r481 r482  
    1717 */
    1818
    19 #include<iostream>
    20 #include<lemon/lp_soplex.h>
     19#include <iostream>
     20#include <lemon/lp_soplex.h>
    2121
    2222#include <soplex/soplex.h>
    … …  
    2727namespace lemon {
    2828
    29   LpSoplex::LpSoplex() : LpSolverBase() {
    30     rows.setIdHandler(relocateIdHandler);
    31     cols.setIdHandler(relocateIdHandler);
     29  LpSoplex::LpSoplex() {
    3230    soplex = new soplex::SoPlex;
    33     solved = false;
    3431  }
    3532
    … …  
    3835  }
    3936
    40   LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
     37  LpSoplex::LpSoplex(const LpSoplex& lp) {
    4138    rows = lp.rows;
    42     rows.setIdHandler(relocateIdHandler);
    43 
    4439    cols = lp.cols;
    45     cols.setIdHandler(relocateIdHandler);
    4640
    4741    soplex = new soplex::SoPlex;
    4842    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
    4943
    50     colNames = lp.colNames;
    51     invColNames = lp.invColNames;
    52 
    53     primal_value = lp.primal_value;
    54     dual_value = lp.dual_value;
    55 
    56   }
    57 
    58   LpSolverBase* LpSoplex::_newLp() {
     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 {
    5958    LpSoplex* newlp = new LpSoplex();
    6059    return newlp;
    6160  }
    6261
    63   LpSolverBase* LpSoplex::_copyLp() {
     62  LpSoplex* LpSoplex::_cloneSolver() const {
    6463    LpSoplex* newlp = new LpSoplex(*this);
    6564    return newlp;
    6665  }
     66
     67  const char* LpSoplex::_solverName() const { return "LpSoplex"; }
    6768
    6869  int LpSoplex::_addCol() {
    … …  
    7273    soplex->addCol(c);
    7374
    74     colNames.push_back(std::string());
    75     primal_value.push_back(0.0);
    76     solved = false;
     75    _col_names.push_back(std::string());
    7776
    7877    return soplex->nCols() - 1;
    … …  
    8584    soplex->addRow(r);
    8685
    87     dual_value.push_back(0.0);
    88     solved = false;
     86    _row_names.push_back(std::string());
    8987
    9088    return soplex->nRows() - 1;
    … …  
    9492  void LpSoplex::_eraseCol(int i) {
    9593    soplex->removeCol(i);
    96     invColNames.erase(colNames[i]);
    97     colNames[i] = colNames.back();
    98     invColNames[colNames.back()] = i;
    99     colNames.pop_back();
    100     primal_value[i] = primal_value.back();
    101     primal_value.pop_back();
    102     solved = false;
     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();
    10398  }
    10499
    105100  void LpSoplex::_eraseRow(int i) {
    106101    soplex->removeRow(i);
    107     dual_value[i] = dual_value.back();
    108     dual_value.pop_back();
    109     solved = false;
     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());
    110115  }
    111116
    112117  void LpSoplex::_getColName(int c, std::string &name) const {
    113     name = colNames[c];
     118    name = _col_names[c];
    114119  }
    115120
    116121  void LpSoplex::_setColName(int c, const std::string &name) {
    117     invColNames.erase(colNames[c]);
    118     colNames[c] = name;
     122    _col_names_ref.erase(_col_names[c]);
     123    _col_names[c] = name;
    119124    if (!name.empty()) {
    120       invColNames.insert(std::make_pair(name, c));
     125      _col_names_ref.insert(std::make_pair(name, c));
    121126    }
    122127  }
    … …  
    124129  int LpSoplex::_colByName(const std::string& name) const {
    125130    std::map<std::string, int>::const_iterator it =
    126       invColNames.find(name);
    127     if (it != invColNames.end()) {
     131      _col_names_ref.find(name);
     132    if (it != _col_names_ref.end()) {
    128133      return it->second;
    129134    } else {
    … …  
    132137  }
    133138
    134 
    135   void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
     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) {
    136163    for (int j = 0; j < soplex->nCols(); ++j) {
    137164      soplex->changeElement(i, j, 0.0);
    138165    }
    139     for(ConstRowIterator it = b; it != e; ++it) {
     166    for(ExprIterator it = b; it != e; ++it) {
    140167      soplex->changeElement(i, it->first, it->second);
    141168    }
    142     solved = false;
    143   }
    144 
    145   void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
     169  }
     170
     171  void LpSoplex::_getRowCoeffs(int i, InsertIterator b) const {
    146172    const soplex::SVector& vec = soplex->rowVector(i);
    147173    for (int k = 0; k < vec.size(); ++k) {
    … …  
    151177  }
    152178
    153   void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
     179  void LpSoplex::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
    154180    for (int i = 0; i < soplex->nRows(); ++i) {
    155181      soplex->changeElement(i, j, 0.0);
    156182    }
    157     for(ConstColIterator it = b; it != e; ++it) {
     183    for(ExprIterator it = b; it != e; ++it) {
    158184      soplex->changeElement(it->first, j, it->second);
    159185    }
    160     solved = false;
    161   }
    162 
    163   void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
     186  }
     187
     188  void LpSoplex::_getColCoeffs(int i, InsertIterator b) const {
    164189    const soplex::SVector& vec = soplex->colVector(i);
    165190    for (int k = 0; k < vec.size(); ++k) {
    … …  
    171196  void LpSoplex::_setCoeff(int i, int j, Value value) {
    172197    soplex->changeElement(i, j, value);
    173     solved = false;
    174198  }
    175199
    … …  
    179203
    180204  void LpSoplex::_setColLowerBound(int i, Value value) {
     205    LEMON_ASSERT(value != INF, "Invalid bound");
    181206    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
    182     solved = false;
    183207  }
    184208
    … …  
    189213
    190214  void LpSoplex::_setColUpperBound(int i, Value value) {
     215    LEMON_ASSERT(value != -INF, "Invalid bound");
    191216    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
    192     solved = false;
    193217  }
    194218
    … …  
    198222  }
    199223
    200   void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
    201     soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
    202                         ub != INF ? ub : soplex::infinity);
    203     solved = false;
    204   }
    205   void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
    206     lower = soplex->lhs(i);
    207     if (lower == -soplex::infinity) lower = -INF;
    208     upper = soplex->rhs(i);
    209     if (upper == -soplex::infinity) upper = INF;
     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    }
    210261  }
    211262
    212263  void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
    213264    soplex->changeObj(i, obj_coef);
    214     solved = false;
    215265  }
    216266
    … …  
    219269  }
    220270
    221   void LpSoplex::_clearObj() {
    222     for (int i = 0; i < soplex->nCols(); ++i) {
    223       soplex->changeObj(i, 0.0);
    224     }
    225     solved = false;
    226   }
    227 
    228271  LpSoplex::SolveExitStatus LpSoplex::_solve() {
     272
     273    _clear_temporals();
     274
    229275    soplex::SPxSolver::Status status = soplex->solve();
    230 
    231     soplex::Vector pv(primal_value.size(), &primal_value[0]);
    232     soplex->getPrimal(pv);
    233 
    234     soplex::Vector dv(dual_value.size(), &dual_value[0]);
    235     soplex->getDual(dv);
    236276
    237277    switch (status) {
    … …  
    239279    case soplex::SPxSolver::INFEASIBLE:
    240280    case soplex::SPxSolver::UNBOUNDED:
    241       solved = true;
    242281      return SOLVED;
    243282    default:
    … …  
    247286
    248287  LpSoplex::Value LpSoplex::_getPrimal(int i) const {
    249     return primal_value[i];
     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];
    250294  }
    251295
    252296  LpSoplex::Value LpSoplex::_getDual(int i) const {
    253     return dual_value[i];
     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];
    254303  }
    255304
    … …  
    258307  }
    259308
    260   bool LpSoplex::_isBasicCol(int i) const {
    261     return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
    262   }
    263 
    264   LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
    265     if (!solved) return UNDEFINED;
     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 {
    266364    switch (soplex->status()) {
    267365    case soplex::SPxSolver::OPTIMAL:
    268366      return OPTIMAL;
    269367    case soplex::SPxSolver::UNBOUNDED:
    270       return INFINITE;
     368      return UNBOUNDED;
    271369    case soplex::SPxSolver::INFEASIBLE:
    272370      return INFEASIBLE;
    … …  
    276374  }
    277375
    278   LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
    279     if (!solved) return UNDEFINED;
     376  LpSoplex::ProblemType LpSoplex::_getDualType() const {
    280377    switch (soplex->status()) {
    281378    case soplex::SPxSolver::OPTIMAL:
    282379      return OPTIMAL;
    283380    case soplex::SPxSolver::UNBOUNDED:
     381      return UNBOUNDED;
     382    case soplex::SPxSolver::INFEASIBLE:
    284383      return INFEASIBLE;
    285384    default:
    … …  
    288387  }
    289388
    290   LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
    291     if (!solved) return UNKNOWN;
    292     switch (soplex->status()) {
    293     case soplex::SPxSolver::OPTIMAL:
    294       return PRIMAL_DUAL_FEASIBLE;
    295     case soplex::SPxSolver::UNBOUNDED:
    296       return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
    297     default:
    298       return UNKNOWN;
    299     }
    300   }
    301 
    302   void LpSoplex::_setMax() {
    303     soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
    304     solved = false;
    305   }
    306   void LpSoplex::_setMin() {
    307     soplex->changeSense(soplex::SPxSolver::MINIMIZE);
    308     solved = false;
    309   }
    310   bool LpSoplex::_isMax() const {
    311     return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;
    312   }
    313 
     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  }
    314421
    315422} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.