lemon/soplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 23 Aug 2009 11:13:21 +0200
changeset 738 456fa5bc3256
parent 540 9db62975c32b
child 746 e4554cd6b2bf
permissions -rw-r--r--
Much better implementation for node splitting (#311)
in ListDigraph. This solution is the same as the one that
is used in SmartDigraph. It is much faster and does not
invalidate any iterator like the former implementation.
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>
deba@576
    23
#include <spxout.h>
alpar@461
    24
alpar@461
    25
alpar@461
    26
///\file
alpar@461
    27
///\brief Implementation of the LEMON-SOPLEX lp solver interface.
alpar@461
    28
namespace lemon {
alpar@461
    29
alpar@462
    30
  SoplexLp::SoplexLp() {
alpar@461
    31
    soplex = new soplex::SoPlex;
deba@576
    32
    messageLevel(MESSAGE_NOTHING);
alpar@461
    33
  }
alpar@461
    34
alpar@462
    35
  SoplexLp::~SoplexLp() {
alpar@461
    36
    delete soplex;
alpar@461
    37
  }
alpar@461
    38
alpar@462
    39
  SoplexLp::SoplexLp(const SoplexLp& lp) {
alpar@461
    40
    rows = lp.rows;
alpar@461
    41
    cols = lp.cols;
alpar@461
    42
alpar@461
    43
    soplex = new soplex::SoPlex;
alpar@461
    44
    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
alpar@461
    45
alpar@461
    46
    _col_names = lp._col_names;
alpar@461
    47
    _col_names_ref = lp._col_names_ref;
alpar@461
    48
alpar@461
    49
    _row_names = lp._row_names;
alpar@461
    50
    _row_names_ref = lp._row_names_ref;
alpar@461
    51
deba@576
    52
    messageLevel(MESSAGE_NOTHING);
alpar@461
    53
  }
alpar@461
    54
alpar@462
    55
  void SoplexLp::_clear_temporals() {
alpar@461
    56
    _primal_values.clear();
alpar@461
    57
    _dual_values.clear();
alpar@461
    58
  }
alpar@461
    59
alpar@540
    60
  SoplexLp* SoplexLp::newSolver() const {
alpar@462
    61
    SoplexLp* newlp = new SoplexLp();
alpar@461
    62
    return newlp;
alpar@461
    63
  }
alpar@461
    64
alpar@540
    65
  SoplexLp* SoplexLp::cloneSolver() const {
alpar@462
    66
    SoplexLp* newlp = new SoplexLp(*this);
alpar@461
    67
    return newlp;
alpar@461
    68
  }
alpar@461
    69
alpar@462
    70
  const char* SoplexLp::_solverName() const { return "SoplexLp"; }
alpar@461
    71
alpar@462
    72
  int SoplexLp::_addCol() {
alpar@461
    73
    soplex::LPCol c;
alpar@461
    74
    c.setLower(-soplex::infinity);
alpar@461
    75
    c.setUpper(soplex::infinity);
alpar@461
    76
    soplex->addCol(c);
alpar@461
    77
alpar@461
    78
    _col_names.push_back(std::string());
alpar@461
    79
alpar@461
    80
    return soplex->nCols() - 1;
alpar@461
    81
  }
alpar@461
    82
alpar@462
    83
  int SoplexLp::_addRow() {
alpar@461
    84
    soplex::LPRow r;
alpar@461
    85
    r.setLhs(-soplex::infinity);
alpar@461
    86
    r.setRhs(soplex::infinity);
alpar@461
    87
    soplex->addRow(r);
alpar@461
    88
alpar@461
    89
    _row_names.push_back(std::string());
alpar@461
    90
alpar@461
    91
    return soplex->nRows() - 1;
alpar@461
    92
  }
alpar@461
    93
alpar@461
    94
alpar@462
    95
  void SoplexLp::_eraseCol(int i) {
alpar@461
    96
    soplex->removeCol(i);
alpar@461
    97
    _col_names_ref.erase(_col_names[i]);
alpar@461
    98
    _col_names[i] = _col_names.back();
alpar@461
    99
    _col_names_ref[_col_names.back()] = i;
alpar@461
   100
    _col_names.pop_back();
alpar@461
   101
  }
alpar@461
   102
alpar@462
   103
  void SoplexLp::_eraseRow(int i) {
alpar@461
   104
    soplex->removeRow(i);
alpar@461
   105
    _row_names_ref.erase(_row_names[i]);
alpar@461
   106
    _row_names[i] = _row_names.back();
alpar@461
   107
    _row_names_ref[_row_names.back()] = i;
alpar@461
   108
    _row_names.pop_back();
alpar@461
   109
  }
alpar@461
   110
alpar@462
   111
  void SoplexLp::_eraseColId(int i) {
alpar@461
   112
    cols.eraseIndex(i);
alpar@461
   113
    cols.relocateIndex(i, cols.maxIndex());
alpar@461
   114
  }
alpar@462
   115
  void SoplexLp::_eraseRowId(int i) {
alpar@461
   116
    rows.eraseIndex(i);
alpar@461
   117
    rows.relocateIndex(i, rows.maxIndex());
alpar@461
   118
  }
alpar@461
   119
alpar@462
   120
  void SoplexLp::_getColName(int c, std::string &name) const {
alpar@461
   121
    name = _col_names[c];
alpar@461
   122
  }
alpar@461
   123
alpar@462
   124
  void SoplexLp::_setColName(int c, const std::string &name) {
alpar@461
   125
    _col_names_ref.erase(_col_names[c]);
alpar@461
   126
    _col_names[c] = name;
alpar@461
   127
    if (!name.empty()) {
alpar@461
   128
      _col_names_ref.insert(std::make_pair(name, c));
alpar@461
   129
    }
alpar@461
   130
  }
alpar@461
   131
alpar@462
   132
  int SoplexLp::_colByName(const std::string& name) const {
alpar@461
   133
    std::map<std::string, int>::const_iterator it =
alpar@461
   134
      _col_names_ref.find(name);
alpar@461
   135
    if (it != _col_names_ref.end()) {
alpar@461
   136
      return it->second;
alpar@461
   137
    } else {
alpar@461
   138
      return -1;
alpar@461
   139
    }
alpar@461
   140
  }
alpar@461
   141
alpar@462
   142
  void SoplexLp::_getRowName(int r, std::string &name) const {
alpar@461
   143
    name = _row_names[r];
alpar@461
   144
  }
alpar@461
   145
alpar@462
   146
  void SoplexLp::_setRowName(int r, const std::string &name) {
alpar@461
   147
    _row_names_ref.erase(_row_names[r]);
alpar@461
   148
    _row_names[r] = name;
alpar@461
   149
    if (!name.empty()) {
alpar@461
   150
      _row_names_ref.insert(std::make_pair(name, r));
alpar@461
   151
    }
alpar@461
   152
  }
alpar@461
   153
alpar@462
   154
  int SoplexLp::_rowByName(const std::string& name) const {
alpar@461
   155
    std::map<std::string, int>::const_iterator it =
alpar@461
   156
      _row_names_ref.find(name);
alpar@461
   157
    if (it != _row_names_ref.end()) {
alpar@461
   158
      return it->second;
alpar@461
   159
    } else {
alpar@461
   160
      return -1;
alpar@461
   161
    }
alpar@461
   162
  }
alpar@461
   163
alpar@461
   164
alpar@462
   165
  void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
alpar@461
   166
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   167
      soplex->changeElement(i, j, 0.0);
alpar@461
   168
    }
alpar@461
   169
    for(ExprIterator it = b; it != e; ++it) {
alpar@461
   170
      soplex->changeElement(i, it->first, it->second);
alpar@461
   171
    }
alpar@461
   172
  }
alpar@461
   173
alpar@462
   174
  void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
alpar@461
   175
    const soplex::SVector& vec = soplex->rowVector(i);
alpar@461
   176
    for (int k = 0; k < vec.size(); ++k) {
alpar@461
   177
      *b = std::make_pair(vec.index(k), vec.value(k));
alpar@461
   178
      ++b;
alpar@461
   179
    }
alpar@461
   180
  }
alpar@461
   181
alpar@462
   182
  void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
alpar@461
   183
    for (int i = 0; i < soplex->nRows(); ++i) {
alpar@461
   184
      soplex->changeElement(i, j, 0.0);
alpar@461
   185
    }
alpar@461
   186
    for(ExprIterator it = b; it != e; ++it) {
alpar@461
   187
      soplex->changeElement(it->first, j, it->second);
alpar@461
   188
    }
alpar@461
   189
  }
alpar@461
   190
alpar@462
   191
  void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
alpar@461
   192
    const soplex::SVector& vec = soplex->colVector(i);
alpar@461
   193
    for (int k = 0; k < vec.size(); ++k) {
alpar@461
   194
      *b = std::make_pair(vec.index(k), vec.value(k));
alpar@461
   195
      ++b;
alpar@461
   196
    }
alpar@461
   197
  }
alpar@461
   198
alpar@462
   199
  void SoplexLp::_setCoeff(int i, int j, Value value) {
alpar@461
   200
    soplex->changeElement(i, j, value);
alpar@461
   201
  }
alpar@461
   202
alpar@462
   203
  SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
alpar@461
   204
    return soplex->rowVector(i)[j];
alpar@461
   205
  }
alpar@461
   206
alpar@462
   207
  void SoplexLp::_setColLowerBound(int i, Value value) {
alpar@461
   208
    LEMON_ASSERT(value != INF, "Invalid bound");
alpar@461
   209
    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
alpar@461
   210
  }
alpar@461
   211
alpar@462
   212
  SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
alpar@461
   213
    double value = soplex->lower(i);
alpar@461
   214
    return value != -soplex::infinity ? value : -INF;
alpar@461
   215
  }
alpar@461
   216
alpar@462
   217
  void SoplexLp::_setColUpperBound(int i, Value value) {
alpar@461
   218
    LEMON_ASSERT(value != -INF, "Invalid bound");
alpar@461
   219
    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
alpar@461
   220
  }
alpar@461
   221
alpar@462
   222
  SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
alpar@461
   223
    double value = soplex->upper(i);
alpar@461
   224
    return value != soplex::infinity ? value : INF;
alpar@461
   225
  }
alpar@461
   226
alpar@462
   227
  void SoplexLp::_setRowLowerBound(int i, Value lb) {
alpar@461
   228
    LEMON_ASSERT(lb != INF, "Invalid bound");
alpar@461
   229
    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
alpar@461
   230
  }
alpar@461
   231
alpar@462
   232
  SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
alpar@461
   233
    double res = soplex->lhs(i);
alpar@461
   234
    return res == -soplex::infinity ? -INF : res;
alpar@461
   235
  }
alpar@461
   236
alpar@462
   237
  void SoplexLp::_setRowUpperBound(int i, Value ub) {
alpar@461
   238
    LEMON_ASSERT(ub != -INF, "Invalid bound");
alpar@461
   239
    soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
alpar@461
   240
  }
alpar@461
   241
alpar@462
   242
  SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
alpar@461
   243
    double res = soplex->rhs(i);
alpar@461
   244
    return res == soplex::infinity ? INF : res;
alpar@461
   245
  }
alpar@461
   246
alpar@462
   247
  void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
alpar@461
   248
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   249
      soplex->changeObj(j, 0.0);
alpar@461
   250
    }
alpar@461
   251
    for (ExprIterator it = b; it != e; ++it) {
alpar@461
   252
      soplex->changeObj(it->first, it->second);
alpar@461
   253
    }
alpar@461
   254
  }
alpar@461
   255
alpar@462
   256
  void SoplexLp::_getObjCoeffs(InsertIterator b) const {
alpar@461
   257
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   258
      Value coef = soplex->obj(j);
alpar@461
   259
      if (coef != 0.0) {
alpar@461
   260
        *b = std::make_pair(j, coef);
alpar@461
   261
        ++b;
alpar@461
   262
      }
alpar@461
   263
    }
alpar@461
   264
  }
alpar@461
   265
alpar@462
   266
  void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
alpar@461
   267
    soplex->changeObj(i, obj_coef);
alpar@461
   268
  }
alpar@461
   269
alpar@462
   270
  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
alpar@461
   271
    return soplex->obj(i);
alpar@461
   272
  }
alpar@461
   273
alpar@462
   274
  SoplexLp::SolveExitStatus SoplexLp::_solve() {
alpar@461
   275
alpar@461
   276
    _clear_temporals();
deba@576
   277
    
deba@576
   278
    _applyMessageLevel();
alpar@461
   279
alpar@461
   280
    soplex::SPxSolver::Status status = soplex->solve();
alpar@461
   281
alpar@461
   282
    switch (status) {
alpar@461
   283
    case soplex::SPxSolver::OPTIMAL:
alpar@461
   284
    case soplex::SPxSolver::INFEASIBLE:
alpar@461
   285
    case soplex::SPxSolver::UNBOUNDED:
alpar@461
   286
      return SOLVED;
alpar@461
   287
    default:
alpar@461
   288
      return UNSOLVED;
alpar@461
   289
    }
alpar@461
   290
  }
alpar@461
   291
alpar@462
   292
  SoplexLp::Value SoplexLp::_getPrimal(int i) const {
alpar@461
   293
    if (_primal_values.empty()) {
alpar@461
   294
      _primal_values.resize(soplex->nCols());
alpar@461
   295
      soplex::Vector pv(_primal_values.size(), &_primal_values.front());
alpar@461
   296
      soplex->getPrimal(pv);
alpar@461
   297
    }
alpar@461
   298
    return _primal_values[i];
alpar@461
   299
  }
alpar@461
   300
alpar@462
   301
  SoplexLp::Value SoplexLp::_getDual(int i) const {
alpar@461
   302
    if (_dual_values.empty()) {
alpar@461
   303
      _dual_values.resize(soplex->nRows());
alpar@461
   304
      soplex::Vector dv(_dual_values.size(), &_dual_values.front());
alpar@461
   305
      soplex->getDual(dv);
alpar@461
   306
    }
alpar@461
   307
    return _dual_values[i];
alpar@461
   308
  }
alpar@461
   309
alpar@462
   310
  SoplexLp::Value SoplexLp::_getPrimalValue() const {
alpar@461
   311
    return soplex->objValue();
alpar@461
   312
  }
alpar@461
   313
alpar@462
   314
  SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
alpar@461
   315
    switch (soplex->getBasisColStatus(i)) {
alpar@461
   316
    case soplex::SPxSolver::BASIC:
alpar@461
   317
      return BASIC;
alpar@461
   318
    case soplex::SPxSolver::ON_UPPER:
alpar@461
   319
      return UPPER;
alpar@461
   320
    case soplex::SPxSolver::ON_LOWER:
alpar@461
   321
      return LOWER;
alpar@461
   322
    case soplex::SPxSolver::FIXED:
alpar@461
   323
      return FIXED;
alpar@461
   324
    case soplex::SPxSolver::ZERO:
alpar@461
   325
      return FREE;
alpar@461
   326
    default:
alpar@461
   327
      LEMON_ASSERT(false, "Wrong column status");
alpar@461
   328
      return VarStatus();
alpar@461
   329
    }
alpar@461
   330
  }
alpar@461
   331
alpar@462
   332
  SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
alpar@461
   333
    switch (soplex->getBasisRowStatus(i)) {
alpar@461
   334
    case soplex::SPxSolver::BASIC:
alpar@461
   335
      return BASIC;
alpar@461
   336
    case soplex::SPxSolver::ON_UPPER:
alpar@461
   337
      return UPPER;
alpar@461
   338
    case soplex::SPxSolver::ON_LOWER:
alpar@461
   339
      return LOWER;
alpar@461
   340
    case soplex::SPxSolver::FIXED:
alpar@461
   341
      return FIXED;
alpar@461
   342
    case soplex::SPxSolver::ZERO:
alpar@461
   343
      return FREE;
alpar@461
   344
    default:
alpar@461
   345
      LEMON_ASSERT(false, "Wrong row status");
alpar@461
   346
      return VarStatus();
alpar@461
   347
    }
alpar@461
   348
  }
alpar@461
   349
alpar@462
   350
  SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
alpar@461
   351
    if (_primal_ray.empty()) {
alpar@461
   352
      _primal_ray.resize(soplex->nCols());
alpar@461
   353
      soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
alpar@461
   354
      soplex->getDualfarkas(pv);
alpar@461
   355
    }
alpar@461
   356
    return _primal_ray[i];
alpar@461
   357
  }
alpar@461
   358
alpar@462
   359
  SoplexLp::Value SoplexLp::_getDualRay(int i) const {
alpar@461
   360
    if (_dual_ray.empty()) {
alpar@461
   361
      _dual_ray.resize(soplex->nRows());
alpar@461
   362
      soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
alpar@461
   363
      soplex->getDualfarkas(dv);
alpar@461
   364
    }
alpar@461
   365
    return _dual_ray[i];
alpar@461
   366
  }
alpar@461
   367
alpar@462
   368
  SoplexLp::ProblemType SoplexLp::_getPrimalType() const {
alpar@461
   369
    switch (soplex->status()) {
alpar@461
   370
    case soplex::SPxSolver::OPTIMAL:
alpar@461
   371
      return OPTIMAL;
alpar@461
   372
    case soplex::SPxSolver::UNBOUNDED:
alpar@461
   373
      return UNBOUNDED;
alpar@461
   374
    case soplex::SPxSolver::INFEASIBLE:
alpar@461
   375
      return INFEASIBLE;
alpar@461
   376
    default:
alpar@461
   377
      return UNDEFINED;
alpar@461
   378
    }
alpar@461
   379
  }
alpar@461
   380
alpar@462
   381
  SoplexLp::ProblemType SoplexLp::_getDualType() const {
alpar@461
   382
    switch (soplex->status()) {
alpar@461
   383
    case soplex::SPxSolver::OPTIMAL:
alpar@461
   384
      return OPTIMAL;
alpar@461
   385
    case soplex::SPxSolver::UNBOUNDED:
alpar@461
   386
      return UNBOUNDED;
alpar@461
   387
    case soplex::SPxSolver::INFEASIBLE:
alpar@461
   388
      return INFEASIBLE;
alpar@461
   389
    default:
alpar@461
   390
      return UNDEFINED;
alpar@461
   391
    }
alpar@461
   392
  }
alpar@461
   393
alpar@462
   394
  void SoplexLp::_setSense(Sense sense) {
alpar@461
   395
    switch (sense) {
alpar@461
   396
    case MIN:
alpar@461
   397
      soplex->changeSense(soplex::SPxSolver::MINIMIZE);
alpar@461
   398
      break;
alpar@461
   399
    case MAX:
alpar@461
   400
      soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
alpar@461
   401
    }
alpar@461
   402
  }
alpar@461
   403
alpar@462
   404
  SoplexLp::Sense SoplexLp::_getSense() const {
alpar@461
   405
    switch (soplex->spxSense()) {
alpar@461
   406
    case soplex::SPxSolver::MAXIMIZE:
alpar@461
   407
      return MAX;
alpar@461
   408
    case soplex::SPxSolver::MINIMIZE:
alpar@461
   409
      return MIN;
alpar@461
   410
    default:
alpar@461
   411
      LEMON_ASSERT(false, "Wrong sense.");
alpar@462
   412
      return SoplexLp::Sense();
alpar@461
   413
    }
alpar@461
   414
  }
alpar@461
   415
alpar@462
   416
  void SoplexLp::_clear() {
alpar@461
   417
    soplex->clear();
alpar@461
   418
    _col_names.clear();
alpar@461
   419
    _col_names_ref.clear();
alpar@461
   420
    _row_names.clear();
alpar@461
   421
    _row_names_ref.clear();
alpar@461
   422
    cols.clear();
alpar@461
   423
    rows.clear();
alpar@461
   424
    _clear_temporals();
alpar@461
   425
  }
alpar@461
   426
deba@576
   427
  void SoplexLp::_messageLevel(MessageLevel level) {
deba@576
   428
    switch (level) {
deba@576
   429
    case MESSAGE_NOTHING:
deba@576
   430
      _message_level = -1;
deba@576
   431
      break;
deba@576
   432
    case MESSAGE_ERROR:
deba@576
   433
      _message_level = soplex::SPxOut::ERROR;
deba@576
   434
      break;
deba@576
   435
    case MESSAGE_WARNING:
deba@576
   436
      _message_level = soplex::SPxOut::WARNING;
deba@576
   437
      break;
deba@576
   438
    case MESSAGE_NORMAL:
deba@576
   439
      _message_level = soplex::SPxOut::INFO2;
deba@576
   440
      break;
deba@576
   441
    case MESSAGE_VERBOSE:
deba@576
   442
      _message_level = soplex::SPxOut::DEBUG;
deba@576
   443
      break;
deba@576
   444
    }
deba@576
   445
  }
deba@576
   446
deba@576
   447
  void SoplexLp::_applyMessageLevel() {
deba@576
   448
    soplex::Param::setVerbose(_message_level);
deba@576
   449
  }
deba@576
   450
alpar@461
   451
} //namespace lemon
alpar@461
   452