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