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