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-2013 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 ClpLp()24 ClpLp::ClpLp() { 25 _prob = new ClpSimplex(); 26 _init_temporals(); 27 messageLevel(MESSAGE_NOTHING); 28 } 29 ClpLp(const ClpLp & other)30 ClpLp::ClpLp(const ClpLp& other) { 31 _prob = new ClpSimplex(*other._prob); 32 rows = other.rows; 33 cols = other.cols; 34 _init_temporals(); 35 messageLevel(MESSAGE_NOTHING); 36 } 37 ~ClpLp()38 ClpLp::~ClpLp() { 39 delete _prob; 40 _clear_temporals(); 41 } 42 _init_temporals()43 void ClpLp::_init_temporals() { 44 _primal_ray = 0; 45 _dual_ray = 0; 46 } 47 _clear_temporals()48 void ClpLp::_clear_temporals() { 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 newSolver() const59 ClpLp* ClpLp::newSolver() const { 60 ClpLp* newlp = new ClpLp; 61 return newlp; 62 } 63 cloneSolver() const64 ClpLp* ClpLp::cloneSolver() const { 65 ClpLp* copylp = new ClpLp(*this); 66 return copylp; 67 } 68 _solverName() const69 const char* ClpLp::_solverName() const { return "ClpLp"; } 70 _addCol()71 int ClpLp::_addCol() { 72 _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0); 73 return _prob->numberColumns() - 1; 74 } 75 _addRow()76 int ClpLp::_addRow() { 77 _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); 78 return _prob->numberRows() - 1; 79 } 80 _addRow(Value l,ExprIterator b,ExprIterator e,Value u)81 int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { 82 std::vector<int> indexes; 83 std::vector<Value> values; 84 85 for(ExprIterator it = b; it != e; ++it) { 86 indexes.push_back(it->first); 87 values.push_back(it->second); 88 } 89 90 _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); 91 return _prob->numberRows() - 1; 92 } 93 94 _eraseCol(int c)95 void ClpLp::_eraseCol(int c) { 96 _col_names_ref.erase(_prob->getColumnName(c)); 97 _prob->deleteColumns(1, &c); 98 } 99 _eraseRow(int r)100 void ClpLp::_eraseRow(int r) { 101 _row_names_ref.erase(_prob->getRowName(r)); 102 _prob->deleteRows(1, &r); 103 } 104 _eraseColId(int i)105 void ClpLp::_eraseColId(int i) { 106 cols.eraseIndex(i); 107 cols.shiftIndices(i); 108 } 109 _eraseRowId(int i)110 void ClpLp::_eraseRowId(int i) { 111 rows.eraseIndex(i); 112 rows.shiftIndices(i); 113 } 114 _getColName(int c,std::string & name) const115 void ClpLp::_getColName(int c, std::string& name) const { 116 name = _prob->getColumnName(c); 117 } 118 _setColName(int c,const std::string & name)119 void ClpLp::_setColName(int c, const std::string& name) { 120 _prob->setColumnName(c, const_cast<std::string&>(name)); 121 _col_names_ref[name] = c; 122 } 123 _colByName(const std::string & name) const124 int ClpLp::_colByName(const std::string& name) const { 125 std::map<std::string, int>::const_iterator it = _col_names_ref.find(name); 126 return it != _col_names_ref.end() ? it->second : -1; 127 } 128 _getRowName(int r,std::string & name) const129 void ClpLp::_getRowName(int r, std::string& name) const { 130 name = _prob->getRowName(r); 131 } 132 _setRowName(int r,const std::string & name)133 void ClpLp::_setRowName(int r, const std::string& name) { 134 _prob->setRowName(r, const_cast<std::string&>(name)); 135 _row_names_ref[name] = r; 136 } 137 _rowByName(const std::string & name) const138 int ClpLp::_rowByName(const std::string& name) const { 139 std::map<std::string, int>::const_iterator it = _row_names_ref.find(name); 140 return it != _row_names_ref.end() ? it->second : -1; 141 } 142 143 _setRowCoeffs(int ix,ExprIterator b,ExprIterator e)144 void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) { 145 std::map<int, Value> coeffs; 146 147 int n = _prob->clpMatrix()->getNumCols(); 148 149 const int* indices = _prob->clpMatrix()->getIndices(); 150 const double* elements = _prob->clpMatrix()->getElements(); 151 152 for (int i = 0; i < n; ++i) { 153 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i]; 154 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i]; 155 156 const int* it = std::lower_bound(indices + begin, indices + end, ix); 157 if (it != indices + end && *it == ix && elements[it - indices] != 0.0) { 158 coeffs[i] = 0.0; 159 } 160 } 161 162 for (ExprIterator it = b; it != e; ++it) { 163 coeffs[it->first] = it->second; 164 } 165 166 for (std::map<int, Value>::iterator it = coeffs.begin(); 167 it != coeffs.end(); ++it) { 168 _prob->modifyCoefficient(ix, it->first, it->second); 169 } 170 } 171 _getRowCoeffs(int ix,InsertIterator b) const172 void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const { 173 int n = _prob->clpMatrix()->getNumCols(); 174 175 const int* indices = _prob->clpMatrix()->getIndices(); 176 const double* elements = _prob->clpMatrix()->getElements(); 177 178 for (int i = 0; i < n; ++i) { 179 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i]; 180 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i]; 181 182 const int* it = std::lower_bound(indices + begin, indices + end, ix); 183 if (it != indices + end && *it == ix) { 184 *b = std::make_pair(i, elements[it - indices]); 185 } 186 } 187 } 188 _setColCoeffs(int ix,ExprIterator b,ExprIterator e)189 void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) { 190 std::map<int, Value> coeffs; 191 192 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; 193 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; 194 195 const int* indices = _prob->clpMatrix()->getIndices(); 196 const double* elements = _prob->clpMatrix()->getElements(); 197 198 for (CoinBigIndex i = begin; i != end; ++i) { 199 if (elements[i] != 0.0) { 200 coeffs[indices[i]] = 0.0; 201 } 202 } 203 for (ExprIterator it = b; it != e; ++it) { 204 coeffs[it->first] = it->second; 205 } 206 for (std::map<int, Value>::iterator it = coeffs.begin(); 207 it != coeffs.end(); ++it) { 208 _prob->modifyCoefficient(it->first, ix, it->second); 209 } 210 } 211 _getColCoeffs(int ix,InsertIterator b) const212 void ClpLp::_getColCoeffs(int ix, InsertIterator b) const { 213 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; 214 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; 215 216 const int* indices = _prob->clpMatrix()->getIndices(); 217 const double* elements = _prob->clpMatrix()->getElements(); 218 219 for (CoinBigIndex i = begin; i != end; ++i) { 220 *b = std::make_pair(indices[i], elements[i]); 221 ++b; 222 } 223 } 224 _setCoeff(int ix,int jx,Value value)225 void ClpLp::_setCoeff(int ix, int jx, Value value) { 226 _prob->modifyCoefficient(ix, jx, value); 227 } 228 _getCoeff(int ix,int jx) const229 ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const { 230 CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix]; 231 CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix]; 232 233 const int* indices = _prob->clpMatrix()->getIndices(); 234 const double* elements = _prob->clpMatrix()->getElements(); 235 236 const int* it = std::lower_bound(indices + begin, indices + end, jx); 237 if (it != indices + end && *it == jx) { 238 return elements[it - indices]; 239 } else { 240 return 0.0; 241 } 242 } 243 _setColLowerBound(int i,Value lo)244 void ClpLp::_setColLowerBound(int i, Value lo) { 245 _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo); 246 } 247 _getColLowerBound(int i) const248 ClpLp::Value ClpLp::_getColLowerBound(int i) const { 249 double val = _prob->getColLower()[i]; 250 return val == - COIN_DBL_MAX ? - INF : val; 251 } 252 _setColUpperBound(int i,Value up)253 void ClpLp::_setColUpperBound(int i, Value up) { 254 _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up); 255 } 256 _getColUpperBound(int i) const257 ClpLp::Value ClpLp::_getColUpperBound(int i) const { 258 double val = _prob->getColUpper()[i]; 259 return val == COIN_DBL_MAX ? INF : val; 260 } 261 _setRowLowerBound(int i,Value lo)262 void ClpLp::_setRowLowerBound(int i, Value lo) { 263 _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo); 264 } 265 _getRowLowerBound(int i) const266 ClpLp::Value ClpLp::_getRowLowerBound(int i) const { 267 double val = _prob->getRowLower()[i]; 268 return val == - COIN_DBL_MAX ? - INF : val; 269 } 270 _setRowUpperBound(int i,Value up)271 void ClpLp::_setRowUpperBound(int i, Value up) { 272 _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up); 273 } 274 _getRowUpperBound(int i) const275 ClpLp::Value ClpLp::_getRowUpperBound(int i) const { 276 double val = _prob->getRowUpper()[i]; 277 return val == COIN_DBL_MAX ? INF : val; 278 } 279 _setObjCoeffs(ExprIterator b,ExprIterator e)280 void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) { 281 int num = _prob->clpMatrix()->getNumCols(); 282 for (int i = 0; i < num; ++i) { 283 _prob->setObjectiveCoefficient(i, 0.0); 284 } 285 for (ExprIterator it = b; it != e; ++it) { 286 _prob->setObjectiveCoefficient(it->first, it->second); 287 } 288 } 289 _getObjCoeffs(InsertIterator b) const290 void ClpLp::_getObjCoeffs(InsertIterator b) const { 291 int num = _prob->clpMatrix()->getNumCols(); 292 for (int i = 0; i < num; ++i) { 293 Value coef = _prob->getObjCoefficients()[i]; 294 if (coef != 0.0) { 295 *b = std::make_pair(i, coef); 296 ++b; 297 } 298 } 299 } 300 _setObjCoeff(int i,Value obj_coef)301 void ClpLp::_setObjCoeff(int i, Value obj_coef) { 302 _prob->setObjectiveCoefficient(i, obj_coef); 303 } 304 _getObjCoeff(int i) const305 ClpLp::Value ClpLp::_getObjCoeff(int i) const { 306 return _prob->getObjCoefficients()[i]; 307 } 308 _solve()309 ClpLp::SolveExitStatus ClpLp::_solve() { 310 return _prob->primal() >= 0 ? SOLVED : UNSOLVED; 311 } 312 solvePrimal()313 ClpLp::SolveExitStatus ClpLp::solvePrimal() { 314 return _prob->primal() >= 0 ? SOLVED : UNSOLVED; 315 } 316 solveDual()317 ClpLp::SolveExitStatus ClpLp::solveDual() { 318 return _prob->dual() >= 0 ? SOLVED : UNSOLVED; 319 } 320 solveBarrier()321 ClpLp::SolveExitStatus ClpLp::solveBarrier() { 322 return _prob->barrier() >= 0 ? SOLVED : UNSOLVED; 323 } 324 _getPrimal(int i) const325 ClpLp::Value ClpLp::_getPrimal(int i) const { 326 return _prob->primalColumnSolution()[i]; 327 } _getPrimalValue() const328 ClpLp::Value ClpLp::_getPrimalValue() const { 329 return _prob->objectiveValue(); 330 } 331 _getDual(int i) const332 ClpLp::Value ClpLp::_getDual(int i) const { 333 return _prob->dualRowSolution()[i]; 334 } 335 _getPrimalRay(int i) const336 ClpLp::Value ClpLp::_getPrimalRay(int i) const { 337 if (!_primal_ray) { 338 _primal_ray = _prob->unboundedRay(); 339 LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided"); 340 } 341 return _primal_ray[i]; 342 } 343 _getDualRay(int i) const344 ClpLp::Value ClpLp::_getDualRay(int i) const { 345 if (!_dual_ray) { 346 _dual_ray = _prob->infeasibilityRay(); 347 LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided"); 348 } 349 return _dual_ray[i]; 350 } 351 _getColStatus(int i) const352 ClpLp::VarStatus ClpLp::_getColStatus(int i) const { 353 switch (_prob->getColumnStatus(i)) { 354 case ClpSimplex::basic: 355 return BASIC; 356 case ClpSimplex::isFree: 357 return FREE; 358 case ClpSimplex::atUpperBound: 359 return UPPER; 360 case ClpSimplex::atLowerBound: 361 return LOWER; 362 case ClpSimplex::isFixed: 363 return FIXED; 364 case ClpSimplex::superBasic: 365 return FREE; 366 default: 367 LEMON_ASSERT(false, "Wrong column status"); 368 return VarStatus(); 369 } 370 } 371 _getRowStatus(int i) const372 ClpLp::VarStatus ClpLp::_getRowStatus(int i) const { 373 switch (_prob->getColumnStatus(i)) { 374 case ClpSimplex::basic: 375 return BASIC; 376 case ClpSimplex::isFree: 377 return FREE; 378 case ClpSimplex::atUpperBound: 379 return UPPER; 380 case ClpSimplex::atLowerBound: 381 return LOWER; 382 case ClpSimplex::isFixed: 383 return FIXED; 384 case ClpSimplex::superBasic: 385 return FREE; 386 default: 387 LEMON_ASSERT(false, "Wrong row status"); 388 return VarStatus(); 389 } 390 } 391 392 _getPrimalType() const393 ClpLp::ProblemType ClpLp::_getPrimalType() const { 394 if (_prob->isProvenOptimal()) { 395 return OPTIMAL; 396 } else if (_prob->isProvenPrimalInfeasible()) { 397 return INFEASIBLE; 398 } else if (_prob->isProvenDualInfeasible()) { 399 return UNBOUNDED; 400 } else { 401 return UNDEFINED; 402 } 403 } 404 _getDualType() const405 ClpLp::ProblemType ClpLp::_getDualType() const { 406 if (_prob->isProvenOptimal()) { 407 return OPTIMAL; 408 } else if (_prob->isProvenDualInfeasible()) { 409 return INFEASIBLE; 410 } else if (_prob->isProvenPrimalInfeasible()) { 411 return INFEASIBLE; 412 } else { 413 return UNDEFINED; 414 } 415 } 416 _setSense(ClpLp::Sense sense)417 void ClpLp::_setSense(ClpLp::Sense sense) { 418 switch (sense) { 419 case MIN: 420 _prob->setOptimizationDirection(1); 421 break; 422 case MAX: 423 _prob->setOptimizationDirection(-1); 424 break; 425 } 426 } 427 _getSense() const428 ClpLp::Sense ClpLp::_getSense() const { 429 double dir = _prob->optimizationDirection(); 430 if (dir > 0.0) { 431 return MIN; 432 } else { 433 return MAX; 434 } 435 } 436 _clear()437 void ClpLp::_clear() { 438 delete _prob; 439 _prob = new ClpSimplex(); 440 _col_names_ref.clear(); 441 _clear_temporals(); 442 } 443 _messageLevel(MessageLevel level)444 void ClpLp::_messageLevel(MessageLevel level) { 445 switch (level) { 446 case MESSAGE_NOTHING: 447 _prob->setLogLevel(0); 448 break; 449 case MESSAGE_ERROR: 450 _prob->setLogLevel(1); 451 break; 452 case MESSAGE_WARNING: 453 _prob->setLogLevel(2); 454 break; 455 case MESSAGE_NORMAL: 456 _prob->setLogLevel(3); 457 break; 458 case MESSAGE_VERBOSE: 459 _prob->setLogLevel(4); 460 break; 461 } 462 } 463 464 } //END OF NAMESPACE LEMON 465