lemon/soplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 27 Mar 2009 18:49:25 +0100
changeset 558 f53d641aa967
parent 539 547e966b3b29
child 576 745e182d0139
permissions -rw-r--r--
Improve timer and counter tests (#253)

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