lemon/lp_clp.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 12 Jan 2009 12:25:55 +0000
changeset 460 76ec7bd57026
permissions -rw-r--r--
Bypass warnings with gcc 4.3
deba@459
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@459
     2
 *
deba@459
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@459
     4
 *
deba@459
     5
 * Copyright (C) 2003-2008
deba@459
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@459
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@459
     8
 *
deba@459
     9
 * Permission to use, modify and distribute this software is granted
deba@459
    10
 * provided that this copyright notice appears in all copies. For
deba@459
    11
 * precise terms see the accompanying LICENSE file.
deba@459
    12
 *
deba@459
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@459
    14
 * express or implied, and with no claim as to its suitability for any
deba@459
    15
 * purpose.
deba@459
    16
 *
deba@459
    17
 */
deba@459
    18
deba@459
    19
#include <lemon/lp_clp.h>
deba@459
    20
#include <coin/ClpSimplex.hpp>
deba@459
    21
deba@459
    22
namespace lemon {
deba@459
    23
deba@459
    24
  LpClp::LpClp() {
deba@459
    25
    _prob = new ClpSimplex();
deba@459
    26
    _init_temporals();
deba@459
    27
    messageLevel(MESSAGE_NO_OUTPUT);
deba@459
    28
  }
deba@459
    29
deba@459
    30
  LpClp::LpClp(const LpClp& other) {
deba@459
    31
    _prob = new ClpSimplex(*other._prob);
deba@459
    32
    rows = other.rows;
deba@459
    33
    cols = other.cols;
deba@459
    34
    _init_temporals();
deba@459
    35
    messageLevel(MESSAGE_NO_OUTPUT);
deba@459
    36
  }
deba@459
    37
deba@459
    38
  LpClp::~LpClp() {
deba@459
    39
    delete _prob;
deba@459
    40
    _clear_temporals();
deba@459
    41
  }
deba@459
    42
deba@459
    43
  void LpClp::_init_temporals() {
deba@459
    44
    _primal_ray = 0;
deba@459
    45
    _dual_ray = 0;
deba@459
    46
  }
deba@459
    47
deba@459
    48
  void LpClp::_clear_temporals() {
deba@459
    49
    if (_primal_ray) {
deba@459
    50
      delete[] _primal_ray;
deba@459
    51
      _primal_ray = 0;
deba@459
    52
    }
deba@459
    53
    if (_dual_ray) {
deba@459
    54
      delete[] _dual_ray;
deba@459
    55
      _dual_ray = 0;
deba@459
    56
    }
deba@459
    57
  }
deba@459
    58
deba@459
    59
  LpClp* LpClp::_newSolver() const {
deba@459
    60
    LpClp* newlp = new LpClp;
deba@459
    61
    return newlp;
deba@459
    62
  }
deba@459
    63
deba@459
    64
  LpClp* LpClp::_cloneSolver() const {
deba@459
    65
    LpClp* copylp = new LpClp(*this);
deba@459
    66
    return copylp;
deba@459
    67
  }
deba@459
    68
deba@459
    69
  const char* LpClp::_solverName() const { return "LpClp"; }
deba@459
    70
deba@459
    71
  int LpClp::_addCol() {
deba@459
    72
    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
deba@459
    73
    return _prob->numberColumns() - 1;
deba@459
    74
  }
deba@459
    75
deba@459
    76
  int LpClp::_addRow() {
deba@459
    77
    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
deba@459
    78
    return _prob->numberRows() - 1;
deba@459
    79
  }
deba@459
    80
deba@459
    81
deba@459
    82
  void LpClp::_eraseCol(int c) {
deba@459
    83
    _col_names_ref.erase(_prob->getColumnName(c));
deba@459
    84
    _prob->deleteColumns(1, &c);
deba@459
    85
  }
deba@459
    86
deba@459
    87
  void LpClp::_eraseRow(int r) {
deba@459
    88
    _row_names_ref.erase(_prob->getRowName(r));
deba@459
    89
    _prob->deleteRows(1, &r);
deba@459
    90
  }
deba@459
    91
deba@459
    92
  void LpClp::_eraseColId(int i) {
deba@459
    93
    cols.eraseIndex(i);
deba@459
    94
    cols.shiftIndices(i);
deba@459
    95
  }
deba@459
    96
deba@459
    97
  void LpClp::_eraseRowId(int i) {
deba@459
    98
    rows.eraseIndex(i);
deba@459
    99
    rows.shiftIndices(i);
deba@459
   100
  }
deba@459
   101
deba@459
   102
  void LpClp::_getColName(int c, std::string& name) const {
deba@459
   103
    name = _prob->getColumnName(c);
deba@459
   104
  }
deba@459
   105
deba@459
   106
  void LpClp::_setColName(int c, const std::string& name) {
deba@459
   107
    _prob->setColumnName(c, const_cast<std::string&>(name));
deba@459
   108
    _col_names_ref[name] = c;
deba@459
   109
  }
deba@459
   110
deba@459
   111
  int LpClp::_colByName(const std::string& name) const {
deba@459
   112
    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
deba@459
   113
    return it != _col_names_ref.end() ? it->second : -1;
deba@459
   114
  }
deba@459
   115
deba@459
   116
  void LpClp::_getRowName(int r, std::string& name) const {
deba@459
   117
    name = _prob->getRowName(r);
deba@459
   118
  }
deba@459
   119
deba@459
   120
  void LpClp::_setRowName(int r, const std::string& name) {
deba@459
   121
    _prob->setRowName(r, const_cast<std::string&>(name));
deba@459
   122
    _row_names_ref[name] = r;
deba@459
   123
  }
deba@459
   124
deba@459
   125
  int LpClp::_rowByName(const std::string& name) const {
deba@459
   126
    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
deba@459
   127
    return it != _row_names_ref.end() ? it->second : -1;
deba@459
   128
  }
deba@459
   129
deba@459
   130
deba@459
   131
  void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
deba@459
   132
    std::map<int, Value> coeffs;
deba@459
   133
deba@459
   134
    int n = _prob->clpMatrix()->getNumCols();
deba@459
   135
deba@459
   136
    const int* indices = _prob->clpMatrix()->getIndices();
deba@459
   137
    const double* elements = _prob->clpMatrix()->getElements();
deba@459
   138
deba@459
   139
    for (int i = 0; i < n; ++i) {
deba@459
   140
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
deba@459
   141
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
deba@459
   142
deba@459
   143
      const int* it = std::lower_bound(indices + begin, indices + end, ix);
deba@459
   144
      if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
deba@459
   145
        coeffs[i] = 0.0;
deba@459
   146
      }
deba@459
   147
    }
deba@459
   148
deba@459
   149
    for (ExprIterator it = b; it != e; ++it) {
deba@459
   150
      coeffs[it->first] = it->second;
deba@459
   151
    }
deba@459
   152
deba@459
   153
    for (std::map<int, Value>::iterator it = coeffs.begin();
deba@459
   154
         it != coeffs.end(); ++it) {
deba@459
   155
      _prob->modifyCoefficient(ix, it->first, it->second);
deba@459
   156
    }
deba@459
   157
  }
deba@459
   158
deba@459
   159
  void LpClp::_getRowCoeffs(int ix, InsertIterator b) const {
deba@459
   160
    int n = _prob->clpMatrix()->getNumCols();
deba@459
   161
deba@459
   162
    const int* indices = _prob->clpMatrix()->getIndices();
deba@459
   163
    const double* elements = _prob->clpMatrix()->getElements();
deba@459
   164
deba@459
   165
    for (int i = 0; i < n; ++i) {
deba@459
   166
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
deba@459
   167
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
deba@459
   168
deba@459
   169
      const int* it = std::lower_bound(indices + begin, indices + end, ix);
deba@459
   170
      if (it != indices + end && *it == ix) {
deba@459
   171
        *b = std::make_pair(i, elements[it - indices]);
deba@459
   172
      }
deba@459
   173
    }
deba@459
   174
  }
deba@459
   175
deba@459
   176
  void LpClp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
deba@459
   177
    std::map<int, Value> coeffs;
deba@459
   178
deba@459
   179
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
deba@459
   180
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
deba@459
   181
deba@459
   182
    const int* indices = _prob->clpMatrix()->getIndices();
deba@459
   183
    const double* elements = _prob->clpMatrix()->getElements();
deba@459
   184
deba@459
   185
    for (CoinBigIndex i = begin; i != end; ++i) {
deba@459
   186
      if (elements[i] != 0.0) {
deba@459
   187
        coeffs[indices[i]] = 0.0;
deba@459
   188
      }
deba@459
   189
    }
deba@459
   190
    for (ExprIterator it = b; it != e; ++it) {
deba@459
   191
      coeffs[it->first] = it->second;
deba@459
   192
    }
deba@459
   193
    for (std::map<int, Value>::iterator it = coeffs.begin();
deba@459
   194
         it != coeffs.end(); ++it) {
deba@459
   195
      _prob->modifyCoefficient(it->first, ix, it->second);
deba@459
   196
    }
deba@459
   197
  }
deba@459
   198
deba@459
   199
  void LpClp::_getColCoeffs(int ix, InsertIterator b) const {
deba@459
   200
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
deba@459
   201
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
deba@459
   202
deba@459
   203
    const int* indices = _prob->clpMatrix()->getIndices();
deba@459
   204
    const double* elements = _prob->clpMatrix()->getElements();
deba@459
   205
deba@459
   206
    for (CoinBigIndex i = begin; i != end; ++i) {
deba@459
   207
      *b = std::make_pair(indices[i], elements[i]);
deba@459
   208
      ++b;
deba@459
   209
    }
deba@459
   210
  }
deba@459
   211
deba@459
   212
  void LpClp::_setCoeff(int ix, int jx, Value value) {
deba@459
   213
    _prob->modifyCoefficient(ix, jx, value);
deba@459
   214
  }
deba@459
   215
deba@459
   216
  LpClp::Value LpClp::_getCoeff(int ix, int jx) const {
deba@459
   217
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
deba@459
   218
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
deba@459
   219
deba@459
   220
    const int* indices = _prob->clpMatrix()->getIndices();
deba@459
   221
    const double* elements = _prob->clpMatrix()->getElements();
deba@459
   222
deba@459
   223
    const int* it = std::lower_bound(indices + begin, indices + end, jx);
deba@459
   224
    if (it != indices + end && *it == jx) {
deba@459
   225
      return elements[it - indices];
deba@459
   226
    } else {
deba@459
   227
      return 0.0;
deba@459
   228
    }
deba@459
   229
  }
deba@459
   230
deba@459
   231
  void LpClp::_setColLowerBound(int i, Value lo) {
deba@459
   232
    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
deba@459
   233
  }
deba@459
   234
deba@459
   235
  LpClp::Value LpClp::_getColLowerBound(int i) const {
deba@459
   236
    double val = _prob->getColLower()[i];
deba@459
   237
    return val == - COIN_DBL_MAX ? - INF : val;
deba@459
   238
  }
deba@459
   239
deba@459
   240
  void LpClp::_setColUpperBound(int i, Value up) {
deba@459
   241
    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
deba@459
   242
  }
deba@459
   243
deba@459
   244
  LpClp::Value LpClp::_getColUpperBound(int i) const {
deba@459
   245
    double val = _prob->getColUpper()[i];
deba@459
   246
    return val == COIN_DBL_MAX ? INF : val;
deba@459
   247
  }
deba@459
   248
deba@459
   249
  void LpClp::_setRowLowerBound(int i, Value lo) {
deba@459
   250
    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
deba@459
   251
  }
deba@459
   252
deba@459
   253
  LpClp::Value LpClp::_getRowLowerBound(int i) const {
deba@459
   254
    double val = _prob->getRowLower()[i];
deba@459
   255
    return val == - COIN_DBL_MAX ? - INF : val;
deba@459
   256
  }
deba@459
   257
deba@459
   258
  void LpClp::_setRowUpperBound(int i, Value up) {
deba@459
   259
    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
deba@459
   260
  }
deba@459
   261
deba@459
   262
  LpClp::Value LpClp::_getRowUpperBound(int i) const {
deba@459
   263
    double val = _prob->getRowUpper()[i];
deba@459
   264
    return val == COIN_DBL_MAX ? INF : val;
deba@459
   265
  }
deba@459
   266
deba@459
   267
  void LpClp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
deba@459
   268
    int num = _prob->clpMatrix()->getNumCols();
deba@459
   269
    for (int i = 0; i < num; ++i) {
deba@459
   270
      _prob->setObjectiveCoefficient(i, 0.0);
deba@459
   271
    }
deba@459
   272
    for (ExprIterator it = b; it != e; ++it) {
deba@459
   273
      _prob->setObjectiveCoefficient(it->first, it->second);
deba@459
   274
    }
deba@459
   275
  }
deba@459
   276
deba@459
   277
  void LpClp::_getObjCoeffs(InsertIterator b) const {
deba@459
   278
    int num = _prob->clpMatrix()->getNumCols();
deba@459
   279
    for (int i = 0; i < num; ++i) {
deba@459
   280
      Value coef = _prob->getObjCoefficients()[i];
deba@459
   281
      if (coef != 0.0) {
deba@459
   282
        *b = std::make_pair(i, coef);
deba@459
   283
        ++b;
deba@459
   284
      }
deba@459
   285
    }
deba@459
   286
  }
deba@459
   287
deba@459
   288
  void LpClp::_setObjCoeff(int i, Value obj_coef) {
deba@459
   289
    _prob->setObjectiveCoefficient(i, obj_coef);
deba@459
   290
  }
deba@459
   291
deba@459
   292
  LpClp::Value LpClp::_getObjCoeff(int i) const {
deba@459
   293
    return _prob->getObjCoefficients()[i];
deba@459
   294
  }
deba@459
   295
deba@459
   296
  LpClp::SolveExitStatus LpClp::_solve() {
deba@459
   297
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
deba@459
   298
  }
deba@459
   299
deba@459
   300
  LpClp::SolveExitStatus LpClp::solvePrimal() {
deba@459
   301
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
deba@459
   302
  }
deba@459
   303
deba@459
   304
  LpClp::SolveExitStatus LpClp::solveDual() {
deba@459
   305
    return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
deba@459
   306
  }
deba@459
   307
deba@459
   308
  LpClp::SolveExitStatus LpClp::solveBarrier() {
deba@459
   309
    return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
deba@459
   310
  }
deba@459
   311
deba@459
   312
  LpClp::Value LpClp::_getPrimal(int i) const {
deba@459
   313
    return _prob->primalColumnSolution()[i];
deba@459
   314
  }
deba@459
   315
  LpClp::Value LpClp::_getPrimalValue() const {
deba@459
   316
    return _prob->objectiveValue();
deba@459
   317
  }
deba@459
   318
deba@459
   319
  LpClp::Value LpClp::_getDual(int i) const {
deba@459
   320
    return _prob->dualRowSolution()[i];
deba@459
   321
  }
deba@459
   322
deba@459
   323
  LpClp::Value LpClp::_getPrimalRay(int i) const {
deba@459
   324
    if (!_primal_ray) {
deba@459
   325
      _primal_ray = _prob->unboundedRay();
deba@459
   326
      LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
deba@459
   327
    }
deba@459
   328
    return _primal_ray[i];
deba@459
   329
  }
deba@459
   330
deba@459
   331
  LpClp::Value LpClp::_getDualRay(int i) const {
deba@459
   332
    if (!_dual_ray) {
deba@459
   333
      _dual_ray = _prob->infeasibilityRay();
deba@459
   334
      LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
deba@459
   335
    }
deba@459
   336
    return _dual_ray[i];
deba@459
   337
  }
deba@459
   338
deba@459
   339
  LpClp::VarStatus LpClp::_getColStatus(int i) const {
deba@459
   340
    switch (_prob->getColumnStatus(i)) {
deba@459
   341
    case ClpSimplex::basic:
deba@459
   342
      return BASIC;
deba@459
   343
    case ClpSimplex::isFree:
deba@459
   344
      return FREE;
deba@459
   345
    case ClpSimplex::atUpperBound:
deba@459
   346
      return UPPER;
deba@459
   347
    case ClpSimplex::atLowerBound:
deba@459
   348
      return LOWER;
deba@459
   349
    case ClpSimplex::isFixed:
deba@459
   350
      return FIXED;
deba@459
   351
    case ClpSimplex::superBasic:
deba@459
   352
      return FREE;
deba@459
   353
    default:
deba@459
   354
      LEMON_ASSERT(false, "Wrong column status");
deba@459
   355
      return VarStatus();
deba@459
   356
    }
deba@459
   357
  }
deba@459
   358
deba@459
   359
  LpClp::VarStatus LpClp::_getRowStatus(int i) const {
deba@459
   360
    switch (_prob->getColumnStatus(i)) {
deba@459
   361
    case ClpSimplex::basic:
deba@459
   362
      return BASIC;
deba@459
   363
    case ClpSimplex::isFree:
deba@459
   364
      return FREE;
deba@459
   365
    case ClpSimplex::atUpperBound:
deba@459
   366
      return UPPER;
deba@459
   367
    case ClpSimplex::atLowerBound:
deba@459
   368
      return LOWER;
deba@459
   369
    case ClpSimplex::isFixed:
deba@459
   370
      return FIXED;
deba@459
   371
    case ClpSimplex::superBasic:
deba@459
   372
      return FREE;
deba@459
   373
    default:
deba@459
   374
      LEMON_ASSERT(false, "Wrong row status");
deba@459
   375
      return VarStatus();
deba@459
   376
    }
deba@459
   377
  }
deba@459
   378
deba@459
   379
deba@459
   380
  LpClp::ProblemType LpClp::_getPrimalType() const {
deba@459
   381
    if (_prob->isProvenOptimal()) {
deba@459
   382
      return OPTIMAL;
deba@459
   383
    } else if (_prob->isProvenPrimalInfeasible()) {
deba@459
   384
      return INFEASIBLE;
deba@459
   385
    } else if (_prob->isProvenDualInfeasible()) {
deba@459
   386
      return UNBOUNDED;
deba@459
   387
    } else {
deba@459
   388
      return UNDEFINED;
deba@459
   389
    }
deba@459
   390
  }
deba@459
   391
deba@459
   392
  LpClp::ProblemType LpClp::_getDualType() const {
deba@459
   393
    if (_prob->isProvenOptimal()) {
deba@459
   394
      return OPTIMAL;
deba@459
   395
    } else if (_prob->isProvenDualInfeasible()) {
deba@459
   396
      return INFEASIBLE;
deba@459
   397
    } else if (_prob->isProvenPrimalInfeasible()) {
deba@459
   398
      return INFEASIBLE;
deba@459
   399
    } else {
deba@459
   400
      return UNDEFINED;
deba@459
   401
    }
deba@459
   402
  }
deba@459
   403
deba@459
   404
  void LpClp::_setSense(LpClp::Sense sense) {
deba@459
   405
    switch (sense) {
deba@459
   406
    case MIN:
deba@459
   407
      _prob->setOptimizationDirection(1);
deba@459
   408
      break;
deba@459
   409
    case MAX:
deba@459
   410
      _prob->setOptimizationDirection(-1);
deba@459
   411
      break;
deba@459
   412
    }
deba@459
   413
  }
deba@459
   414
deba@459
   415
  LpClp::Sense LpClp::_getSense() const {
deba@459
   416
    double dir = _prob->optimizationDirection();
deba@459
   417
    if (dir > 0.0) {
deba@459
   418
      return MIN;
deba@459
   419
    } else {
deba@459
   420
      return MAX;
deba@459
   421
    }
deba@459
   422
  }
deba@459
   423
deba@459
   424
  void LpClp::_clear() {
deba@459
   425
    delete _prob;
deba@459
   426
    _prob = new ClpSimplex();
deba@459
   427
    rows.clear();
deba@459
   428
    cols.clear();
deba@459
   429
    _col_names_ref.clear();
deba@459
   430
    _clear_temporals();
deba@459
   431
  }
deba@459
   432
deba@459
   433
  void LpClp::messageLevel(MessageLevel m) {
deba@459
   434
    _prob->setLogLevel(static_cast<int>(m));
deba@459
   435
  }
deba@459
   436
deba@459
   437
} //END OF NAMESPACE LEMON