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