1.1 --- a/lemon/lp_soplex.cc Tue Dec 02 21:40:33 2008 +0100
1.2 +++ b/lemon/lp_soplex.cc Tue Dec 02 22:48:28 2008 +0100
1.3 @@ -16,8 +16,8 @@
1.4 *
1.5 */
1.6
1.7 -#include<iostream>
1.8 -#include<lemon/lp_soplex.h>
1.9 +#include <iostream>
1.10 +#include <lemon/lp_soplex.h>
1.11
1.12 #include <soplex/soplex.h>
1.13
1.14 @@ -26,54 +26,53 @@
1.15 ///\brief Implementation of the LEMON-SOPLEX lp solver interface.
1.16 namespace lemon {
1.17
1.18 - LpSoplex::LpSoplex() : LpSolverBase() {
1.19 - rows.setIdHandler(relocateIdHandler);
1.20 - cols.setIdHandler(relocateIdHandler);
1.21 + LpSoplex::LpSoplex() {
1.22 soplex = new soplex::SoPlex;
1.23 - solved = false;
1.24 }
1.25
1.26 LpSoplex::~LpSoplex() {
1.27 delete soplex;
1.28 }
1.29
1.30 - LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
1.31 + LpSoplex::LpSoplex(const LpSoplex& lp) {
1.32 rows = lp.rows;
1.33 - rows.setIdHandler(relocateIdHandler);
1.34 -
1.35 cols = lp.cols;
1.36 - cols.setIdHandler(relocateIdHandler);
1.37
1.38 soplex = new soplex::SoPlex;
1.39 (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
1.40
1.41 - colNames = lp.colNames;
1.42 - invColNames = lp.invColNames;
1.43 + _col_names = lp._col_names;
1.44 + _col_names_ref = lp._col_names_ref;
1.45
1.46 - primal_value = lp.primal_value;
1.47 - dual_value = lp.dual_value;
1.48 + _row_names = lp._row_names;
1.49 + _row_names_ref = lp._row_names_ref;
1.50
1.51 }
1.52
1.53 - LpSolverBase* LpSoplex::_newLp() {
1.54 + void LpSoplex::_clear_temporals() {
1.55 + _primal_values.clear();
1.56 + _dual_values.clear();
1.57 + }
1.58 +
1.59 + LpSoplex* LpSoplex::_newSolver() const {
1.60 LpSoplex* newlp = new LpSoplex();
1.61 return newlp;
1.62 }
1.63
1.64 - LpSolverBase* LpSoplex::_copyLp() {
1.65 + LpSoplex* LpSoplex::_cloneSolver() const {
1.66 LpSoplex* newlp = new LpSoplex(*this);
1.67 return newlp;
1.68 }
1.69
1.70 + const char* LpSoplex::_solverName() const { return "LpSoplex"; }
1.71 +
1.72 int LpSoplex::_addCol() {
1.73 soplex::LPCol c;
1.74 c.setLower(-soplex::infinity);
1.75 c.setUpper(soplex::infinity);
1.76 soplex->addCol(c);
1.77
1.78 - colNames.push_back(std::string());
1.79 - primal_value.push_back(0.0);
1.80 - solved = false;
1.81 + _col_names.push_back(std::string());
1.82
1.83 return soplex->nCols() - 1;
1.84 }
1.85 @@ -84,8 +83,7 @@
1.86 r.setRhs(soplex::infinity);
1.87 soplex->addRow(r);
1.88
1.89 - dual_value.push_back(0.0);
1.90 - solved = false;
1.91 + _row_names.push_back(std::string());
1.92
1.93 return soplex->nRows() - 1;
1.94 }
1.95 @@ -93,56 +91,84 @@
1.96
1.97 void LpSoplex::_eraseCol(int i) {
1.98 soplex->removeCol(i);
1.99 - invColNames.erase(colNames[i]);
1.100 - colNames[i] = colNames.back();
1.101 - invColNames[colNames.back()] = i;
1.102 - colNames.pop_back();
1.103 - primal_value[i] = primal_value.back();
1.104 - primal_value.pop_back();
1.105 - solved = false;
1.106 + _col_names_ref.erase(_col_names[i]);
1.107 + _col_names[i] = _col_names.back();
1.108 + _col_names_ref[_col_names.back()] = i;
1.109 + _col_names.pop_back();
1.110 }
1.111
1.112 void LpSoplex::_eraseRow(int i) {
1.113 soplex->removeRow(i);
1.114 - dual_value[i] = dual_value.back();
1.115 - dual_value.pop_back();
1.116 - solved = false;
1.117 + _row_names_ref.erase(_row_names[i]);
1.118 + _row_names[i] = _row_names.back();
1.119 + _row_names_ref[_row_names.back()] = i;
1.120 + _row_names.pop_back();
1.121 + }
1.122 +
1.123 + void LpSoplex::_eraseColId(int i) {
1.124 + cols.eraseIndex(i);
1.125 + cols.relocateIndex(i, cols.maxIndex());
1.126 + }
1.127 + void LpSoplex::_eraseRowId(int i) {
1.128 + rows.eraseIndex(i);
1.129 + rows.relocateIndex(i, rows.maxIndex());
1.130 }
1.131
1.132 void LpSoplex::_getColName(int c, std::string &name) const {
1.133 - name = colNames[c];
1.134 + name = _col_names[c];
1.135 }
1.136
1.137 void LpSoplex::_setColName(int c, const std::string &name) {
1.138 - invColNames.erase(colNames[c]);
1.139 - colNames[c] = name;
1.140 + _col_names_ref.erase(_col_names[c]);
1.141 + _col_names[c] = name;
1.142 if (!name.empty()) {
1.143 - invColNames.insert(std::make_pair(name, c));
1.144 + _col_names_ref.insert(std::make_pair(name, c));
1.145 }
1.146 }
1.147
1.148 int LpSoplex::_colByName(const std::string& name) const {
1.149 std::map<std::string, int>::const_iterator it =
1.150 - invColNames.find(name);
1.151 - if (it != invColNames.end()) {
1.152 + _col_names_ref.find(name);
1.153 + if (it != _col_names_ref.end()) {
1.154 return it->second;
1.155 } else {
1.156 return -1;
1.157 }
1.158 }
1.159
1.160 + void LpSoplex::_getRowName(int r, std::string &name) const {
1.161 + name = _row_names[r];
1.162 + }
1.163
1.164 - void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
1.165 + void LpSoplex::_setRowName(int r, const std::string &name) {
1.166 + _row_names_ref.erase(_row_names[r]);
1.167 + _row_names[r] = name;
1.168 + if (!name.empty()) {
1.169 + _row_names_ref.insert(std::make_pair(name, r));
1.170 + }
1.171 + }
1.172 +
1.173 + int LpSoplex::_rowByName(const std::string& name) const {
1.174 + std::map<std::string, int>::const_iterator it =
1.175 + _row_names_ref.find(name);
1.176 + if (it != _row_names_ref.end()) {
1.177 + return it->second;
1.178 + } else {
1.179 + return -1;
1.180 + }
1.181 + }
1.182 +
1.183 +
1.184 + void LpSoplex::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
1.185 for (int j = 0; j < soplex->nCols(); ++j) {
1.186 soplex->changeElement(i, j, 0.0);
1.187 }
1.188 - for(ConstRowIterator it = b; it != e; ++it) {
1.189 + for(ExprIterator it = b; it != e; ++it) {
1.190 soplex->changeElement(i, it->first, it->second);
1.191 }
1.192 - solved = false;
1.193 }
1.194
1.195 - void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
1.196 + void LpSoplex::_getRowCoeffs(int i, InsertIterator b) const {
1.197 const soplex::SVector& vec = soplex->rowVector(i);
1.198 for (int k = 0; k < vec.size(); ++k) {
1.199 *b = std::make_pair(vec.index(k), vec.value(k));
1.200 @@ -150,17 +176,16 @@
1.201 }
1.202 }
1.203
1.204 - void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
1.205 + void LpSoplex::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
1.206 for (int i = 0; i < soplex->nRows(); ++i) {
1.207 soplex->changeElement(i, j, 0.0);
1.208 }
1.209 - for(ConstColIterator it = b; it != e; ++it) {
1.210 + for(ExprIterator it = b; it != e; ++it) {
1.211 soplex->changeElement(it->first, j, it->second);
1.212 }
1.213 - solved = false;
1.214 }
1.215
1.216 - void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
1.217 + void LpSoplex::_getColCoeffs(int i, InsertIterator b) const {
1.218 const soplex::SVector& vec = soplex->colVector(i);
1.219 for (int k = 0; k < vec.size(); ++k) {
1.220 *b = std::make_pair(vec.index(k), vec.value(k));
1.221 @@ -170,7 +195,6 @@
1.222
1.223 void LpSoplex::_setCoeff(int i, int j, Value value) {
1.224 soplex->changeElement(i, j, value);
1.225 - solved = false;
1.226 }
1.227
1.228 LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
1.229 @@ -178,8 +202,8 @@
1.230 }
1.231
1.232 void LpSoplex::_setColLowerBound(int i, Value value) {
1.233 + LEMON_ASSERT(value != INF, "Invalid bound");
1.234 soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
1.235 - solved = false;
1.236 }
1.237
1.238 LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
1.239 @@ -188,8 +212,8 @@
1.240 }
1.241
1.242 void LpSoplex::_setColUpperBound(int i, Value value) {
1.243 + LEMON_ASSERT(value != -INF, "Invalid bound");
1.244 soplex->changeUpper(i, value != INF ? value : soplex::infinity);
1.245 - solved = false;
1.246 }
1.247
1.248 LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
1.249 @@ -197,48 +221,63 @@
1.250 return value != soplex::infinity ? value : INF;
1.251 }
1.252
1.253 - void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
1.254 - soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
1.255 - ub != INF ? ub : soplex::infinity);
1.256 - solved = false;
1.257 + void LpSoplex::_setRowLowerBound(int i, Value lb) {
1.258 + LEMON_ASSERT(lb != INF, "Invalid bound");
1.259 + soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
1.260 }
1.261 - void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
1.262 - lower = soplex->lhs(i);
1.263 - if (lower == -soplex::infinity) lower = -INF;
1.264 - upper = soplex->rhs(i);
1.265 - if (upper == -soplex::infinity) upper = INF;
1.266 +
1.267 + LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const {
1.268 + double res = soplex->lhs(i);
1.269 + return res == -soplex::infinity ? -INF : res;
1.270 + }
1.271 +
1.272 + void LpSoplex::_setRowUpperBound(int i, Value ub) {
1.273 + LEMON_ASSERT(ub != -INF, "Invalid bound");
1.274 + soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
1.275 + }
1.276 +
1.277 + LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const {
1.278 + double res = soplex->rhs(i);
1.279 + return res == soplex::infinity ? INF : res;
1.280 + }
1.281 +
1.282 + void LpSoplex::_setObjCoeffs(ExprIterator b, ExprIterator e) {
1.283 + for (int j = 0; j < soplex->nCols(); ++j) {
1.284 + soplex->changeObj(j, 0.0);
1.285 + }
1.286 + for (ExprIterator it = b; it != e; ++it) {
1.287 + soplex->changeObj(it->first, it->second);
1.288 + }
1.289 + }
1.290 +
1.291 + void LpSoplex::_getObjCoeffs(InsertIterator b) const {
1.292 + for (int j = 0; j < soplex->nCols(); ++j) {
1.293 + Value coef = soplex->obj(j);
1.294 + if (coef != 0.0) {
1.295 + *b = std::make_pair(j, coef);
1.296 + ++b;
1.297 + }
1.298 + }
1.299 }
1.300
1.301 void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
1.302 soplex->changeObj(i, obj_coef);
1.303 - solved = false;
1.304 }
1.305
1.306 LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
1.307 return soplex->obj(i);
1.308 }
1.309
1.310 - void LpSoplex::_clearObj() {
1.311 - for (int i = 0; i < soplex->nCols(); ++i) {
1.312 - soplex->changeObj(i, 0.0);
1.313 - }
1.314 - solved = false;
1.315 - }
1.316 + LpSoplex::SolveExitStatus LpSoplex::_solve() {
1.317
1.318 - LpSoplex::SolveExitStatus LpSoplex::_solve() {
1.319 + _clear_temporals();
1.320 +
1.321 soplex::SPxSolver::Status status = soplex->solve();
1.322
1.323 - soplex::Vector pv(primal_value.size(), &primal_value[0]);
1.324 - soplex->getPrimal(pv);
1.325 -
1.326 - soplex::Vector dv(dual_value.size(), &dual_value[0]);
1.327 - soplex->getDual(dv);
1.328 -
1.329 switch (status) {
1.330 case soplex::SPxSolver::OPTIMAL:
1.331 case soplex::SPxSolver::INFEASIBLE:
1.332 case soplex::SPxSolver::UNBOUNDED:
1.333 - solved = true;
1.334 return SOLVED;
1.335 default:
1.336 return UNSOLVED;
1.337 @@ -246,28 +285,87 @@
1.338 }
1.339
1.340 LpSoplex::Value LpSoplex::_getPrimal(int i) const {
1.341 - return primal_value[i];
1.342 + if (_primal_values.empty()) {
1.343 + _primal_values.resize(soplex->nCols());
1.344 + soplex::Vector pv(_primal_values.size(), &_primal_values.front());
1.345 + soplex->getPrimal(pv);
1.346 + }
1.347 + return _primal_values[i];
1.348 }
1.349
1.350 LpSoplex::Value LpSoplex::_getDual(int i) const {
1.351 - return dual_value[i];
1.352 + if (_dual_values.empty()) {
1.353 + _dual_values.resize(soplex->nRows());
1.354 + soplex::Vector dv(_dual_values.size(), &_dual_values.front());
1.355 + soplex->getDual(dv);
1.356 + }
1.357 + return _dual_values[i];
1.358 }
1.359
1.360 LpSoplex::Value LpSoplex::_getPrimalValue() const {
1.361 return soplex->objValue();
1.362 }
1.363
1.364 - bool LpSoplex::_isBasicCol(int i) const {
1.365 - return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
1.366 + LpSoplex::VarStatus LpSoplex::_getColStatus(int i) const {
1.367 + switch (soplex->getBasisColStatus(i)) {
1.368 + case soplex::SPxSolver::BASIC:
1.369 + return BASIC;
1.370 + case soplex::SPxSolver::ON_UPPER:
1.371 + return UPPER;
1.372 + case soplex::SPxSolver::ON_LOWER:
1.373 + return LOWER;
1.374 + case soplex::SPxSolver::FIXED:
1.375 + return FIXED;
1.376 + case soplex::SPxSolver::ZERO:
1.377 + return FREE;
1.378 + default:
1.379 + LEMON_ASSERT(false, "Wrong column status");
1.380 + return VarStatus();
1.381 + }
1.382 }
1.383
1.384 - LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
1.385 - if (!solved) return UNDEFINED;
1.386 + LpSoplex::VarStatus LpSoplex::_getRowStatus(int i) const {
1.387 + switch (soplex->getBasisRowStatus(i)) {
1.388 + case soplex::SPxSolver::BASIC:
1.389 + return BASIC;
1.390 + case soplex::SPxSolver::ON_UPPER:
1.391 + return UPPER;
1.392 + case soplex::SPxSolver::ON_LOWER:
1.393 + return LOWER;
1.394 + case soplex::SPxSolver::FIXED:
1.395 + return FIXED;
1.396 + case soplex::SPxSolver::ZERO:
1.397 + return FREE;
1.398 + default:
1.399 + LEMON_ASSERT(false, "Wrong row status");
1.400 + return VarStatus();
1.401 + }
1.402 + }
1.403 +
1.404 + LpSoplex::Value LpSoplex::_getPrimalRay(int i) const {
1.405 + if (_primal_ray.empty()) {
1.406 + _primal_ray.resize(soplex->nCols());
1.407 + soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
1.408 + soplex->getDualfarkas(pv);
1.409 + }
1.410 + return _primal_ray[i];
1.411 + }
1.412 +
1.413 + LpSoplex::Value LpSoplex::_getDualRay(int i) const {
1.414 + if (_dual_ray.empty()) {
1.415 + _dual_ray.resize(soplex->nRows());
1.416 + soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
1.417 + soplex->getDualfarkas(dv);
1.418 + }
1.419 + return _dual_ray[i];
1.420 + }
1.421 +
1.422 + LpSoplex::ProblemType LpSoplex::_getPrimalType() const {
1.423 switch (soplex->status()) {
1.424 case soplex::SPxSolver::OPTIMAL:
1.425 return OPTIMAL;
1.426 case soplex::SPxSolver::UNBOUNDED:
1.427 - return INFINITE;
1.428 + return UNBOUNDED;
1.429 case soplex::SPxSolver::INFEASIBLE:
1.430 return INFEASIBLE;
1.431 default:
1.432 @@ -275,42 +373,51 @@
1.433 }
1.434 }
1.435
1.436 - LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
1.437 - if (!solved) return UNDEFINED;
1.438 + LpSoplex::ProblemType LpSoplex::_getDualType() const {
1.439 switch (soplex->status()) {
1.440 case soplex::SPxSolver::OPTIMAL:
1.441 return OPTIMAL;
1.442 case soplex::SPxSolver::UNBOUNDED:
1.443 + return UNBOUNDED;
1.444 + case soplex::SPxSolver::INFEASIBLE:
1.445 return INFEASIBLE;
1.446 default:
1.447 return UNDEFINED;
1.448 }
1.449 }
1.450
1.451 - LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
1.452 - if (!solved) return UNKNOWN;
1.453 - switch (soplex->status()) {
1.454 - case soplex::SPxSolver::OPTIMAL:
1.455 - return PRIMAL_DUAL_FEASIBLE;
1.456 - case soplex::SPxSolver::UNBOUNDED:
1.457 - return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
1.458 - default:
1.459 - return UNKNOWN;
1.460 + void LpSoplex::_setSense(Sense sense) {
1.461 + switch (sense) {
1.462 + case MIN:
1.463 + soplex->changeSense(soplex::SPxSolver::MINIMIZE);
1.464 + break;
1.465 + case MAX:
1.466 + soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
1.467 }
1.468 }
1.469
1.470 - void LpSoplex::_setMax() {
1.471 - soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
1.472 - solved = false;
1.473 - }
1.474 - void LpSoplex::_setMin() {
1.475 - soplex->changeSense(soplex::SPxSolver::MINIMIZE);
1.476 - solved = false;
1.477 - }
1.478 - bool LpSoplex::_isMax() const {
1.479 - return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;
1.480 + LpSoplex::Sense LpSoplex::_getSense() const {
1.481 + switch (soplex->spxSense()) {
1.482 + case soplex::SPxSolver::MAXIMIZE:
1.483 + return MAX;
1.484 + case soplex::SPxSolver::MINIMIZE:
1.485 + return MIN;
1.486 + default:
1.487 + LEMON_ASSERT(false, "Wrong sense.");
1.488 + return LpSoplex::Sense();
1.489 + }
1.490 }
1.491
1.492 + void LpSoplex::_clear() {
1.493 + soplex->clear();
1.494 + _col_names.clear();
1.495 + _col_names_ref.clear();
1.496 + _row_names.clear();
1.497 + _row_names_ref.clear();
1.498 + cols.clear();
1.499 + rows.clear();
1.500 + _clear_temporals();
1.501 + }
1.502
1.503 } //namespace lemon
1.504