lemon/soplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 30 Jan 2012 19:29:03 +0100
changeset 985 eb12ad2789fc
parent 746 e4554cd6b2bf
child 1092 dceba191c00d
permissions -rw-r--r--
Fix the doc in CapacityScaling: cost can be real numbers (#261)
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@877
     5
 * Copyright (C) 2003-2010
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
deba@746
    94
  int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
deba@746
    95
    soplex::DSVector v;
deba@746
    96
    for (ExprIterator it = b; it != e; ++it) {
deba@746
    97
      v.add(it->first, it->second);
deba@746
    98
    }
deba@746
    99
    soplex::LPRow r(l, v, u);
deba@746
   100
    soplex->addRow(r);
deba@746
   101
deba@746
   102
    _row_names.push_back(std::string());
deba@746
   103
deba@746
   104
    return soplex->nRows() - 1;
deba@746
   105
  }
deba@746
   106
alpar@461
   107
alpar@462
   108
  void SoplexLp::_eraseCol(int i) {
alpar@461
   109
    soplex->removeCol(i);
alpar@461
   110
    _col_names_ref.erase(_col_names[i]);
alpar@461
   111
    _col_names[i] = _col_names.back();
alpar@461
   112
    _col_names_ref[_col_names.back()] = i;
alpar@461
   113
    _col_names.pop_back();
alpar@461
   114
  }
alpar@461
   115
alpar@462
   116
  void SoplexLp::_eraseRow(int i) {
alpar@461
   117
    soplex->removeRow(i);
alpar@461
   118
    _row_names_ref.erase(_row_names[i]);
alpar@461
   119
    _row_names[i] = _row_names.back();
alpar@461
   120
    _row_names_ref[_row_names.back()] = i;
alpar@461
   121
    _row_names.pop_back();
alpar@461
   122
  }
alpar@461
   123
alpar@462
   124
  void SoplexLp::_eraseColId(int i) {
alpar@461
   125
    cols.eraseIndex(i);
alpar@461
   126
    cols.relocateIndex(i, cols.maxIndex());
alpar@461
   127
  }
alpar@462
   128
  void SoplexLp::_eraseRowId(int i) {
alpar@461
   129
    rows.eraseIndex(i);
alpar@461
   130
    rows.relocateIndex(i, rows.maxIndex());
alpar@461
   131
  }
alpar@461
   132
alpar@462
   133
  void SoplexLp::_getColName(int c, std::string &name) const {
alpar@461
   134
    name = _col_names[c];
alpar@461
   135
  }
alpar@461
   136
alpar@462
   137
  void SoplexLp::_setColName(int c, const std::string &name) {
alpar@461
   138
    _col_names_ref.erase(_col_names[c]);
alpar@461
   139
    _col_names[c] = name;
alpar@461
   140
    if (!name.empty()) {
alpar@461
   141
      _col_names_ref.insert(std::make_pair(name, c));
alpar@461
   142
    }
alpar@461
   143
  }
alpar@461
   144
alpar@462
   145
  int SoplexLp::_colByName(const std::string& name) const {
alpar@461
   146
    std::map<std::string, int>::const_iterator it =
alpar@461
   147
      _col_names_ref.find(name);
alpar@461
   148
    if (it != _col_names_ref.end()) {
alpar@461
   149
      return it->second;
alpar@461
   150
    } else {
alpar@461
   151
      return -1;
alpar@461
   152
    }
alpar@461
   153
  }
alpar@461
   154
alpar@462
   155
  void SoplexLp::_getRowName(int r, std::string &name) const {
alpar@461
   156
    name = _row_names[r];
alpar@461
   157
  }
alpar@461
   158
alpar@462
   159
  void SoplexLp::_setRowName(int r, const std::string &name) {
alpar@461
   160
    _row_names_ref.erase(_row_names[r]);
alpar@461
   161
    _row_names[r] = name;
alpar@461
   162
    if (!name.empty()) {
alpar@461
   163
      _row_names_ref.insert(std::make_pair(name, r));
alpar@461
   164
    }
alpar@461
   165
  }
alpar@461
   166
alpar@462
   167
  int SoplexLp::_rowByName(const std::string& name) const {
alpar@461
   168
    std::map<std::string, int>::const_iterator it =
alpar@461
   169
      _row_names_ref.find(name);
alpar@461
   170
    if (it != _row_names_ref.end()) {
alpar@461
   171
      return it->second;
alpar@461
   172
    } else {
alpar@461
   173
      return -1;
alpar@461
   174
    }
alpar@461
   175
  }
alpar@461
   176
alpar@461
   177
alpar@462
   178
  void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
alpar@461
   179
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   180
      soplex->changeElement(i, j, 0.0);
alpar@461
   181
    }
alpar@461
   182
    for(ExprIterator it = b; it != e; ++it) {
alpar@461
   183
      soplex->changeElement(i, it->first, it->second);
alpar@461
   184
    }
alpar@461
   185
  }
alpar@461
   186
alpar@462
   187
  void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
alpar@461
   188
    const soplex::SVector& vec = soplex->rowVector(i);
alpar@461
   189
    for (int k = 0; k < vec.size(); ++k) {
alpar@461
   190
      *b = std::make_pair(vec.index(k), vec.value(k));
alpar@461
   191
      ++b;
alpar@461
   192
    }
alpar@461
   193
  }
alpar@461
   194
alpar@462
   195
  void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
alpar@461
   196
    for (int i = 0; i < soplex->nRows(); ++i) {
alpar@461
   197
      soplex->changeElement(i, j, 0.0);
alpar@461
   198
    }
alpar@461
   199
    for(ExprIterator it = b; it != e; ++it) {
alpar@461
   200
      soplex->changeElement(it->first, j, it->second);
alpar@461
   201
    }
alpar@461
   202
  }
alpar@461
   203
alpar@462
   204
  void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
alpar@461
   205
    const soplex::SVector& vec = soplex->colVector(i);
alpar@461
   206
    for (int k = 0; k < vec.size(); ++k) {
alpar@461
   207
      *b = std::make_pair(vec.index(k), vec.value(k));
alpar@461
   208
      ++b;
alpar@461
   209
    }
alpar@461
   210
  }
alpar@461
   211
alpar@462
   212
  void SoplexLp::_setCoeff(int i, int j, Value value) {
alpar@461
   213
    soplex->changeElement(i, j, value);
alpar@461
   214
  }
alpar@461
   215
alpar@462
   216
  SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
alpar@461
   217
    return soplex->rowVector(i)[j];
alpar@461
   218
  }
alpar@461
   219
alpar@462
   220
  void SoplexLp::_setColLowerBound(int i, Value value) {
alpar@461
   221
    LEMON_ASSERT(value != INF, "Invalid bound");
alpar@461
   222
    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
alpar@461
   223
  }
alpar@461
   224
alpar@462
   225
  SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
alpar@461
   226
    double value = soplex->lower(i);
alpar@461
   227
    return value != -soplex::infinity ? value : -INF;
alpar@461
   228
  }
alpar@461
   229
alpar@462
   230
  void SoplexLp::_setColUpperBound(int i, Value value) {
alpar@461
   231
    LEMON_ASSERT(value != -INF, "Invalid bound");
alpar@461
   232
    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
alpar@461
   233
  }
alpar@461
   234
alpar@462
   235
  SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
alpar@461
   236
    double value = soplex->upper(i);
alpar@461
   237
    return value != soplex::infinity ? value : INF;
alpar@461
   238
  }
alpar@461
   239
alpar@462
   240
  void SoplexLp::_setRowLowerBound(int i, Value lb) {
alpar@461
   241
    LEMON_ASSERT(lb != INF, "Invalid bound");
alpar@461
   242
    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
alpar@461
   243
  }
alpar@461
   244
alpar@462
   245
  SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
alpar@461
   246
    double res = soplex->lhs(i);
alpar@461
   247
    return res == -soplex::infinity ? -INF : res;
alpar@461
   248
  }
alpar@461
   249
alpar@462
   250
  void SoplexLp::_setRowUpperBound(int i, Value ub) {
alpar@461
   251
    LEMON_ASSERT(ub != -INF, "Invalid bound");
alpar@461
   252
    soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
alpar@461
   253
  }
alpar@461
   254
alpar@462
   255
  SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
alpar@461
   256
    double res = soplex->rhs(i);
alpar@461
   257
    return res == soplex::infinity ? INF : res;
alpar@461
   258
  }
alpar@461
   259
alpar@462
   260
  void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
alpar@461
   261
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   262
      soplex->changeObj(j, 0.0);
alpar@461
   263
    }
alpar@461
   264
    for (ExprIterator it = b; it != e; ++it) {
alpar@461
   265
      soplex->changeObj(it->first, it->second);
alpar@461
   266
    }
alpar@461
   267
  }
alpar@461
   268
alpar@462
   269
  void SoplexLp::_getObjCoeffs(InsertIterator b) const {
alpar@461
   270
    for (int j = 0; j < soplex->nCols(); ++j) {
alpar@461
   271
      Value coef = soplex->obj(j);
alpar@461
   272
      if (coef != 0.0) {
alpar@461
   273
        *b = std::make_pair(j, coef);
alpar@461
   274
        ++b;
alpar@461
   275
      }
alpar@461
   276
    }
alpar@461
   277
  }
alpar@461
   278
alpar@462
   279
  void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
alpar@461
   280
    soplex->changeObj(i, obj_coef);
alpar@461
   281
  }
alpar@461
   282
alpar@462
   283
  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
alpar@461
   284
    return soplex->obj(i);
alpar@461
   285
  }
alpar@461
   286
alpar@462
   287
  SoplexLp::SolveExitStatus SoplexLp::_solve() {
alpar@461
   288
alpar@461
   289
    _clear_temporals();
alpar@877
   290
deba@576
   291
    _applyMessageLevel();
alpar@461
   292
alpar@461
   293
    soplex::SPxSolver::Status status = soplex->solve();
alpar@461
   294
alpar@461
   295
    switch (status) {
alpar@461
   296
    case soplex::SPxSolver::OPTIMAL:
alpar@461
   297
    case soplex::SPxSolver::INFEASIBLE:
alpar@461
   298
    case soplex::SPxSolver::UNBOUNDED:
alpar@461
   299
      return SOLVED;
alpar@461
   300
    default:
alpar@461
   301
      return UNSOLVED;
alpar@461
   302
    }
alpar@461
   303
  }
alpar@461
   304
alpar@462
   305
  SoplexLp::Value SoplexLp::_getPrimal(int i) const {
alpar@461
   306
    if (_primal_values.empty()) {
alpar@461
   307
      _primal_values.resize(soplex->nCols());
alpar@461
   308
      soplex::Vector pv(_primal_values.size(), &_primal_values.front());
alpar@461
   309
      soplex->getPrimal(pv);
alpar@461
   310
    }
alpar@461
   311
    return _primal_values[i];
alpar@461
   312
  }
alpar@461
   313
alpar@462
   314
  SoplexLp::Value SoplexLp::_getDual(int i) const {
alpar@461
   315
    if (_dual_values.empty()) {
alpar@461
   316
      _dual_values.resize(soplex->nRows());
alpar@461
   317
      soplex::Vector dv(_dual_values.size(), &_dual_values.front());
alpar@461
   318
      soplex->getDual(dv);
alpar@461
   319
    }
alpar@461
   320
    return _dual_values[i];
alpar@461
   321
  }
alpar@461
   322
alpar@462
   323
  SoplexLp::Value SoplexLp::_getPrimalValue() const {
alpar@461
   324
    return soplex->objValue();
alpar@461
   325
  }
alpar@461
   326
alpar@462
   327
  SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
alpar@461
   328
    switch (soplex->getBasisColStatus(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 column status");
alpar@461
   341
      return VarStatus();
alpar@461
   342
    }
alpar@461
   343
  }
alpar@461
   344
alpar@462
   345
  SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
alpar@461
   346
    switch (soplex->getBasisRowStatus(i)) {
alpar@461
   347
    case soplex::SPxSolver::BASIC:
alpar@461
   348
      return BASIC;
alpar@461
   349
    case soplex::SPxSolver::ON_UPPER:
alpar@461
   350
      return UPPER;
alpar@461
   351
    case soplex::SPxSolver::ON_LOWER:
alpar@461
   352
      return LOWER;
alpar@461
   353
    case soplex::SPxSolver::FIXED:
alpar@461
   354
      return FIXED;
alpar@461
   355
    case soplex::SPxSolver::ZERO:
alpar@461
   356
      return FREE;
alpar@461
   357
    default:
alpar@461
   358
      LEMON_ASSERT(false, "Wrong row status");
alpar@461
   359
      return VarStatus();
alpar@461
   360
    }
alpar@461
   361
  }
alpar@461
   362
alpar@462
   363
  SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
alpar@461
   364
    if (_primal_ray.empty()) {
alpar@461
   365
      _primal_ray.resize(soplex->nCols());
alpar@461
   366
      soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
alpar@461
   367
      soplex->getDualfarkas(pv);
alpar@461
   368
    }
alpar@461
   369
    return _primal_ray[i];
alpar@461
   370
  }
alpar@461
   371
alpar@462
   372
  SoplexLp::Value SoplexLp::_getDualRay(int i) const {
alpar@461
   373
    if (_dual_ray.empty()) {
alpar@461
   374
      _dual_ray.resize(soplex->nRows());
alpar@461
   375
      soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
alpar@461
   376
      soplex->getDualfarkas(dv);
alpar@461
   377
    }
alpar@461
   378
    return _dual_ray[i];
alpar@461
   379
  }
alpar@461
   380
alpar@462
   381
  SoplexLp::ProblemType SoplexLp::_getPrimalType() 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
  SoplexLp::ProblemType SoplexLp::_getDualType() const {
alpar@461
   395
    switch (soplex->status()) {
alpar@461
   396
    case soplex::SPxSolver::OPTIMAL:
alpar@461
   397
      return OPTIMAL;
alpar@461
   398
    case soplex::SPxSolver::UNBOUNDED:
alpar@461
   399
      return UNBOUNDED;
alpar@461
   400
    case soplex::SPxSolver::INFEASIBLE:
alpar@461
   401
      return INFEASIBLE;
alpar@461
   402
    default:
alpar@461
   403
      return UNDEFINED;
alpar@461
   404
    }
alpar@461
   405
  }
alpar@461
   406
alpar@462
   407
  void SoplexLp::_setSense(Sense sense) {
alpar@461
   408
    switch (sense) {
alpar@461
   409
    case MIN:
alpar@461
   410
      soplex->changeSense(soplex::SPxSolver::MINIMIZE);
alpar@461
   411
      break;
alpar@461
   412
    case MAX:
alpar@461
   413
      soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
alpar@461
   414
    }
alpar@461
   415
  }
alpar@461
   416
alpar@462
   417
  SoplexLp::Sense SoplexLp::_getSense() const {
alpar@461
   418
    switch (soplex->spxSense()) {
alpar@461
   419
    case soplex::SPxSolver::MAXIMIZE:
alpar@461
   420
      return MAX;
alpar@461
   421
    case soplex::SPxSolver::MINIMIZE:
alpar@461
   422
      return MIN;
alpar@461
   423
    default:
alpar@461
   424
      LEMON_ASSERT(false, "Wrong sense.");
alpar@462
   425
      return SoplexLp::Sense();
alpar@461
   426
    }
alpar@461
   427
  }
alpar@461
   428
alpar@462
   429
  void SoplexLp::_clear() {
alpar@461
   430
    soplex->clear();
alpar@461
   431
    _col_names.clear();
alpar@461
   432
    _col_names_ref.clear();
alpar@461
   433
    _row_names.clear();
alpar@461
   434
    _row_names_ref.clear();
alpar@461
   435
    cols.clear();
alpar@461
   436
    rows.clear();
alpar@461
   437
    _clear_temporals();
alpar@461
   438
  }
alpar@461
   439
deba@576
   440
  void SoplexLp::_messageLevel(MessageLevel level) {
deba@576
   441
    switch (level) {
deba@576
   442
    case MESSAGE_NOTHING:
deba@576
   443
      _message_level = -1;
deba@576
   444
      break;
deba@576
   445
    case MESSAGE_ERROR:
deba@576
   446
      _message_level = soplex::SPxOut::ERROR;
deba@576
   447
      break;
deba@576
   448
    case MESSAGE_WARNING:
deba@576
   449
      _message_level = soplex::SPxOut::WARNING;
deba@576
   450
      break;
deba@576
   451
    case MESSAGE_NORMAL:
deba@576
   452
      _message_level = soplex::SPxOut::INFO2;
deba@576
   453
      break;
deba@576
   454
    case MESSAGE_VERBOSE:
deba@576
   455
      _message_level = soplex::SPxOut::DEBUG;
deba@576
   456
      break;
deba@576
   457
    }
deba@576
   458
  }
deba@576
   459
deba@576
   460
  void SoplexLp::_applyMessageLevel() {
deba@576
   461
    soplex::Param::setVerbose(_message_level);
deba@576
   462
  }
deba@576
   463
alpar@461
   464
} //namespace lemon
alpar@461
   465