lemon/lp_soplex.cc
author kpeter
Mon, 01 Jun 2009 15:35:27 +0000
changeset 2635 23570e368afa
parent 2553 bfced05fa852
permissions -rw-r--r--
XTI data structure for NS - backport hg commit [8c3112a66878]
deba@2313
     1
/* -*- C++ -*-
deba@2313
     2
 *
deba@2313
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@2313
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
deba@2313
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2313
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2313
     8
 *
deba@2313
     9
 * Permission to use, modify and distribute this software is granted
deba@2313
    10
 * provided that this copyright notice appears in all copies. For
deba@2313
    11
 * precise terms see the accompanying LICENSE file.
deba@2313
    12
 *
deba@2313
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@2313
    14
 * express or implied, and with no claim as to its suitability for any
deba@2313
    15
 * purpose.
deba@2313
    16
 *
deba@2313
    17
 */
deba@2313
    18
deba@2313
    19
#include<iostream>
deba@2313
    20
#include<lemon/lp_soplex.h>
deba@2313
    21
deba@2313
    22
#include <soplex/soplex.h>
deba@2313
    23
deba@2313
    24
deba@2313
    25
///\file
deba@2313
    26
///\brief Implementation of the LEMON-SOPLEX lp solver interface.
deba@2313
    27
namespace lemon {
deba@2313
    28
  
deba@2313
    29
  LpSoplex::LpSoplex() : LpSolverBase() {
deba@2363
    30
    rows.setIdHandler(relocateIdHandler);
deba@2363
    31
    cols.setIdHandler(relocateIdHandler);
deba@2313
    32
    soplex = new soplex::SoPlex;
deba@2363
    33
    solved = false;
deba@2313
    34
  }
deba@2313
    35
  
deba@2313
    36
  LpSoplex::~LpSoplex() {
deba@2313
    37
    delete soplex;
deba@2313
    38
  }
deba@2605
    39
deba@2605
    40
  LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
deba@2605
    41
    rows = lp.rows;
deba@2605
    42
    rows.setIdHandler(relocateIdHandler);
deba@2605
    43
deba@2605
    44
    cols = lp.cols;
deba@2605
    45
    cols.setIdHandler(relocateIdHandler);
deba@2605
    46
deba@2605
    47
    soplex = new soplex::SoPlex;
deba@2605
    48
    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
deba@2605
    49
deba@2605
    50
    colNames = lp.colNames;
deba@2605
    51
    invColNames = lp.invColNames;
deba@2605
    52
deba@2605
    53
    primal_value = lp.primal_value;
deba@2605
    54
    dual_value = lp.dual_value;
deba@2605
    55
deba@2605
    56
  }
deba@2313
    57
  
deba@2605
    58
  LpSolverBase* LpSoplex::_newLp() {
deba@2313
    59
    LpSoplex* newlp = new LpSoplex();
deba@2605
    60
    return newlp;
deba@2313
    61
  }
deba@2313
    62
deba@2605
    63
  LpSolverBase* LpSoplex::_copyLp() {
deba@2605
    64
    LpSoplex* newlp = new LpSoplex(*this);
deba@2605
    65
    return newlp;
deba@2313
    66
  }
deba@2313
    67
deba@2313
    68
  int LpSoplex::_addCol() {
deba@2386
    69
    soplex::LPCol c;
deba@2386
    70
    c.setLower(-soplex::infinity);
deba@2386
    71
    c.setUpper(soplex::infinity);
deba@2386
    72
    soplex->addCol(c);
deba@2313
    73
deba@2313
    74
    colNames.push_back(std::string());
deba@2363
    75
    primal_value.push_back(0.0);
deba@2363
    76
    solved = false;
deba@2313
    77
deba@2313
    78
    return soplex->nCols() - 1;
deba@2313
    79
  }
deba@2313
    80
deba@2313
    81
  int LpSoplex::_addRow() {
deba@2386
    82
    soplex::LPRow r;
deba@2386
    83
    r.setLhs(-soplex::infinity);
deba@2386
    84
    r.setRhs(soplex::infinity);
deba@2386
    85
    soplex->addRow(r);
deba@2313
    86
deba@2363
    87
    dual_value.push_back(0.0);
deba@2363
    88
    solved = false;
deba@2313
    89
deba@2313
    90
    return soplex->nRows() - 1;
deba@2313
    91
  }
deba@2313
    92
deba@2313
    93
deba@2313
    94
  void LpSoplex::_eraseCol(int i) {
deba@2313
    95
    soplex->removeCol(i);
deba@2368
    96
    invColNames.erase(colNames[i]);
deba@2363
    97
    colNames[i] = colNames.back();
deba@2368
    98
    invColNames[colNames.back()] = i;
deba@2363
    99
    colNames.pop_back();
deba@2363
   100
    primal_value[i] = primal_value.back();
deba@2363
   101
    primal_value.pop_back();
deba@2363
   102
    solved = false;
deba@2313
   103
  }
deba@2313
   104
  
deba@2313
   105
  void LpSoplex::_eraseRow(int i) {
deba@2313
   106
    soplex->removeRow(i);
deba@2363
   107
    dual_value[i] = dual_value.back();
deba@2363
   108
    dual_value.pop_back();
deba@2363
   109
    solved = false;
deba@2313
   110
  }
deba@2313
   111
  
deba@2386
   112
  void LpSoplex::_getColName(int c, std::string &name) const {
deba@2386
   113
    name = colNames[c]; 
deba@2313
   114
  }
deba@2313
   115
  
deba@2386
   116
  void LpSoplex::_setColName(int c, const std::string &name) {
deba@2386
   117
    invColNames.erase(colNames[c]);
deba@2386
   118
    colNames[c] = name; 
deba@2366
   119
    if (!name.empty()) {
deba@2386
   120
      invColNames.insert(std::make_pair(name, c));
deba@2366
   121
    }
deba@2366
   122
  }
deba@2366
   123
deba@2366
   124
  int LpSoplex::_colByName(const std::string& name) const {
deba@2366
   125
    std::map<std::string, int>::const_iterator it =
deba@2366
   126
      invColNames.find(name);
deba@2366
   127
    if (it != invColNames.end()) {
deba@2366
   128
      return it->second;
deba@2366
   129
    } else {
deba@2366
   130
      return -1;
deba@2366
   131
    }
deba@2313
   132
  }
deba@2313
   133
  
deba@2313
   134
deba@2364
   135
  void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
deba@2313
   136
    for (int j = 0; j < soplex->nCols(); ++j) {
deba@2313
   137
      soplex->changeElement(i, j, 0.0);
deba@2313
   138
    }
deba@2364
   139
    for(ConstRowIterator it = b; it != e; ++it) {
deba@2313
   140
      soplex->changeElement(i, it->first, it->second);
deba@2313
   141
    }
deba@2363
   142
    solved = false;
deba@2313
   143
  }
deba@2364
   144
deba@2366
   145
  void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
deba@2364
   146
    const soplex::SVector& vec = soplex->rowVector(i);
deba@2364
   147
    for (int k = 0; k < vec.size(); ++k) {
deba@2364
   148
      *b = std::make_pair(vec.index(k), vec.value(k));
deba@2364
   149
      ++b;
deba@2364
   150
    }
deba@2364
   151
  }
deba@2313
   152
  
deba@2364
   153
  void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
deba@2313
   154
    for (int i = 0; i < soplex->nRows(); ++i) {
deba@2313
   155
      soplex->changeElement(i, j, 0.0);
deba@2313
   156
    }
deba@2364
   157
    for(ConstColIterator it = b; it != e; ++it) {
deba@2313
   158
      soplex->changeElement(it->first, j, it->second);
deba@2313
   159
    }
deba@2363
   160
    solved = false;
deba@2313
   161
  }
deba@2364
   162
deba@2366
   163
  void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
deba@2364
   164
    const soplex::SVector& vec = soplex->colVector(i);
deba@2364
   165
    for (int k = 0; k < vec.size(); ++k) {
deba@2364
   166
      *b = std::make_pair(vec.index(k), vec.value(k));
deba@2364
   167
      ++b;
deba@2364
   168
    }
deba@2364
   169
  }
deba@2313
   170
  
deba@2363
   171
  void LpSoplex::_setCoeff(int i, int j, Value value) {
deba@2363
   172
    soplex->changeElement(i, j, value);
deba@2363
   173
    solved = false;
deba@2363
   174
  }
deba@2363
   175
deba@2366
   176
  LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
deba@2363
   177
    return soplex->rowVector(i)[j];
deba@2313
   178
  }
deba@2313
   179
deba@2313
   180
  void LpSoplex::_setColLowerBound(int i, Value value) {
deba@2363
   181
    soplex->changeLower(i, value != -INF ? value : -soplex::infinity); 
deba@2363
   182
    solved = false;
deba@2313
   183
  }
deba@2313
   184
  
deba@2366
   185
  LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
deba@2363
   186
    double value = soplex->lower(i);
deba@2363
   187
    return value != -soplex::infinity ? value : -INF;
deba@2363
   188
  }
deba@2363
   189
deba@2313
   190
  void LpSoplex::_setColUpperBound(int i, Value value) {
deba@2363
   191
    soplex->changeUpper(i, value != INF ? value : soplex::infinity); 
deba@2363
   192
    solved = false;
deba@2363
   193
  }
deba@2363
   194
deba@2366
   195
  LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
deba@2363
   196
    double value = soplex->upper(i);
deba@2363
   197
    return value != soplex::infinity ? value : INF;
deba@2313
   198
  }
deba@2313
   199
deba@2313
   200
  void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
deba@2363
   201
    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
deba@2363
   202
                        ub != INF ? ub : soplex::infinity);
deba@2363
   203
    solved = false;
deba@2363
   204
  }
deba@2366
   205
  void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
deba@2363
   206
    lower = soplex->lhs(i);
deba@2363
   207
    if (lower == -soplex::infinity) lower = -INF;
deba@2363
   208
    upper = soplex->rhs(i);
deba@2363
   209
    if (upper == -soplex::infinity) upper = INF;
deba@2313
   210
  }
deba@2313
   211
deba@2313
   212
  void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
deba@2313
   213
    soplex->changeObj(i, obj_coef);
deba@2363
   214
    solved = false;
deba@2363
   215
  }
deba@2363
   216
deba@2366
   217
  LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
deba@2363
   218
    return soplex->obj(i);
deba@2313
   219
  }
deba@2313
   220
deba@2313
   221
  void LpSoplex::_clearObj() {
deba@2313
   222
    for (int i = 0; i < soplex->nCols(); ++i) {
deba@2313
   223
      soplex->changeObj(i, 0.0);
deba@2313
   224
    }
deba@2363
   225
    solved = false;
deba@2313
   226
  }
deba@2313
   227
deba@2313
   228
  LpSoplex::SolveExitStatus LpSoplex::_solve() {
deba@2313
   229
    soplex::SPxSolver::Status status = soplex->solve();
deba@2313
   230
deba@2363
   231
    soplex::Vector pv(primal_value.size(), &primal_value[0]);
deba@2313
   232
    soplex->getPrimal(pv);
deba@2313
   233
deba@2363
   234
    soplex::Vector dv(dual_value.size(), &dual_value[0]);
deba@2313
   235
    soplex->getDual(dv);
deba@2313
   236
deba@2313
   237
    switch (status) {
deba@2313
   238
    case soplex::SPxSolver::OPTIMAL:
deba@2313
   239
    case soplex::SPxSolver::INFEASIBLE:
deba@2313
   240
    case soplex::SPxSolver::UNBOUNDED:
deba@2363
   241
      solved = true;
deba@2313
   242
      return SOLVED;
deba@2313
   243
    default:
deba@2313
   244
      return UNSOLVED;
deba@2313
   245
    }
deba@2313
   246
  }
deba@2313
   247
deba@2366
   248
  LpSoplex::Value LpSoplex::_getPrimal(int i) const {
deba@2363
   249
    return primal_value[i];
deba@2313
   250
  }
deba@2313
   251
deba@2366
   252
  LpSoplex::Value LpSoplex::_getDual(int i) const {
deba@2363
   253
    return dual_value[i];
deba@2313
   254
  }
deba@2313
   255
  
deba@2366
   256
  LpSoplex::Value LpSoplex::_getPrimalValue() const {
deba@2313
   257
    return soplex->objValue();
deba@2313
   258
  }
deba@2313
   259
deba@2366
   260
  bool LpSoplex::_isBasicCol(int i) const {
deba@2313
   261
    return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
deba@2313
   262
  }  
deba@2313
   263
deba@2366
   264
  LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
deba@2363
   265
    if (!solved) return UNDEFINED;
deba@2313
   266
    switch (soplex->status()) {
deba@2313
   267
    case soplex::SPxSolver::OPTIMAL:
deba@2313
   268
      return OPTIMAL;
deba@2313
   269
    case soplex::SPxSolver::UNBOUNDED:
deba@2313
   270
      return INFINITE;
deba@2313
   271
    case soplex::SPxSolver::INFEASIBLE:
deba@2313
   272
      return INFEASIBLE;
deba@2313
   273
    default:
deba@2313
   274
      return UNDEFINED;
deba@2313
   275
    }
deba@2313
   276
  }
deba@2313
   277
deba@2366
   278
  LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
deba@2363
   279
    if (!solved) return UNDEFINED;
deba@2363
   280
    switch (soplex->status()) {
deba@2363
   281
    case soplex::SPxSolver::OPTIMAL:
deba@2313
   282
      return OPTIMAL;
deba@2363
   283
    case soplex::SPxSolver::UNBOUNDED:
deba@2313
   284
      return INFEASIBLE;
deba@2363
   285
    default:
deba@2313
   286
      return UNDEFINED;
deba@2313
   287
    }
deba@2313
   288
  }
deba@2313
   289
deba@2366
   290
  LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
deba@2363
   291
    if (!solved) return UNKNOWN;
deba@2363
   292
    switch (soplex->status()) {
deba@2363
   293
    case soplex::SPxSolver::OPTIMAL:
deba@2313
   294
      return PRIMAL_DUAL_FEASIBLE;
deba@2363
   295
    case soplex::SPxSolver::UNBOUNDED:
deba@2313
   296
      return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
deba@2363
   297
    default:
deba@2313
   298
      return UNKNOWN;
deba@2313
   299
    }
deba@2313
   300
  }
deba@2313
   301
deba@2313
   302
  void LpSoplex::_setMax() {
deba@2313
   303
    soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
deba@2363
   304
    solved = false;
deba@2313
   305
  }
deba@2313
   306
  void LpSoplex::_setMin() {
deba@2313
   307
    soplex->changeSense(soplex::SPxSolver::MINIMIZE);
deba@2363
   308
    solved = false;
deba@2313
   309
  }
deba@2366
   310
  bool LpSoplex::_isMax() const {
deba@2363
   311
    return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;
deba@2363
   312
  }
deba@2363
   313
deba@2313
   314
  
deba@2313
   315
} //namespace lemon
deba@2313
   316