1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/soplex.cc Mon Jan 12 12:26:01 2009 +0000
1.3 @@ -0,0 +1,423 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +#include <lemon/soplex.h>
1.24 +
1.25 +#include <soplex/soplex.h>
1.26 +
1.27 +
1.28 +///\file
1.29 +///\brief Implementation of the LEMON-SOPLEX lp solver interface.
1.30 +namespace lemon {
1.31 +
1.32 + LpSoplex::LpSoplex() {
1.33 + soplex = new soplex::SoPlex;
1.34 + }
1.35 +
1.36 + LpSoplex::~LpSoplex() {
1.37 + delete soplex;
1.38 + }
1.39 +
1.40 + LpSoplex::LpSoplex(const LpSoplex& lp) {
1.41 + rows = lp.rows;
1.42 + cols = lp.cols;
1.43 +
1.44 + soplex = new soplex::SoPlex;
1.45 + (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
1.46 +
1.47 + _col_names = lp._col_names;
1.48 + _col_names_ref = lp._col_names_ref;
1.49 +
1.50 + _row_names = lp._row_names;
1.51 + _row_names_ref = lp._row_names_ref;
1.52 +
1.53 + }
1.54 +
1.55 + void LpSoplex::_clear_temporals() {
1.56 + _primal_values.clear();
1.57 + _dual_values.clear();
1.58 + }
1.59 +
1.60 + LpSoplex* LpSoplex::_newSolver() const {
1.61 + LpSoplex* newlp = new LpSoplex();
1.62 + return newlp;
1.63 + }
1.64 +
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 + _col_names.push_back(std::string());
1.79 +
1.80 + return soplex->nCols() - 1;
1.81 + }
1.82 +
1.83 + int LpSoplex::_addRow() {
1.84 + soplex::LPRow r;
1.85 + r.setLhs(-soplex::infinity);
1.86 + r.setRhs(soplex::infinity);
1.87 + soplex->addRow(r);
1.88 +
1.89 + _row_names.push_back(std::string());
1.90 +
1.91 + return soplex->nRows() - 1;
1.92 + }
1.93 +
1.94 +
1.95 + void LpSoplex::_eraseCol(int i) {
1.96 + soplex->removeCol(i);
1.97 + _col_names_ref.erase(_col_names[i]);
1.98 + _col_names[i] = _col_names.back();
1.99 + _col_names_ref[_col_names.back()] = i;
1.100 + _col_names.pop_back();
1.101 + }
1.102 +
1.103 + void LpSoplex::_eraseRow(int i) {
1.104 + soplex->removeRow(i);
1.105 + _row_names_ref.erase(_row_names[i]);
1.106 + _row_names[i] = _row_names.back();
1.107 + _row_names_ref[_row_names.back()] = i;
1.108 + _row_names.pop_back();
1.109 + }
1.110 +
1.111 + void LpSoplex::_eraseColId(int i) {
1.112 + cols.eraseIndex(i);
1.113 + cols.relocateIndex(i, cols.maxIndex());
1.114 + }
1.115 + void LpSoplex::_eraseRowId(int i) {
1.116 + rows.eraseIndex(i);
1.117 + rows.relocateIndex(i, rows.maxIndex());
1.118 + }
1.119 +
1.120 + void LpSoplex::_getColName(int c, std::string &name) const {
1.121 + name = _col_names[c];
1.122 + }
1.123 +
1.124 + void LpSoplex::_setColName(int c, const std::string &name) {
1.125 + _col_names_ref.erase(_col_names[c]);
1.126 + _col_names[c] = name;
1.127 + if (!name.empty()) {
1.128 + _col_names_ref.insert(std::make_pair(name, c));
1.129 + }
1.130 + }
1.131 +
1.132 + int LpSoplex::_colByName(const std::string& name) const {
1.133 + std::map<std::string, int>::const_iterator it =
1.134 + _col_names_ref.find(name);
1.135 + if (it != _col_names_ref.end()) {
1.136 + return it->second;
1.137 + } else {
1.138 + return -1;
1.139 + }
1.140 + }
1.141 +
1.142 + void LpSoplex::_getRowName(int r, std::string &name) const {
1.143 + name = _row_names[r];
1.144 + }
1.145 +
1.146 + void LpSoplex::_setRowName(int r, const std::string &name) {
1.147 + _row_names_ref.erase(_row_names[r]);
1.148 + _row_names[r] = name;
1.149 + if (!name.empty()) {
1.150 + _row_names_ref.insert(std::make_pair(name, r));
1.151 + }
1.152 + }
1.153 +
1.154 + int LpSoplex::_rowByName(const std::string& name) const {
1.155 + std::map<std::string, int>::const_iterator it =
1.156 + _row_names_ref.find(name);
1.157 + if (it != _row_names_ref.end()) {
1.158 + return it->second;
1.159 + } else {
1.160 + return -1;
1.161 + }
1.162 + }
1.163 +
1.164 +
1.165 + void LpSoplex::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
1.166 + for (int j = 0; j < soplex->nCols(); ++j) {
1.167 + soplex->changeElement(i, j, 0.0);
1.168 + }
1.169 + for(ExprIterator it = b; it != e; ++it) {
1.170 + soplex->changeElement(i, it->first, it->second);
1.171 + }
1.172 + }
1.173 +
1.174 + void LpSoplex::_getRowCoeffs(int i, InsertIterator b) const {
1.175 + const soplex::SVector& vec = soplex->rowVector(i);
1.176 + for (int k = 0; k < vec.size(); ++k) {
1.177 + *b = std::make_pair(vec.index(k), vec.value(k));
1.178 + ++b;
1.179 + }
1.180 + }
1.181 +
1.182 + void LpSoplex::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
1.183 + for (int i = 0; i < soplex->nRows(); ++i) {
1.184 + soplex->changeElement(i, j, 0.0);
1.185 + }
1.186 + for(ExprIterator it = b; it != e; ++it) {
1.187 + soplex->changeElement(it->first, j, it->second);
1.188 + }
1.189 + }
1.190 +
1.191 + void LpSoplex::_getColCoeffs(int i, InsertIterator b) const {
1.192 + const soplex::SVector& vec = soplex->colVector(i);
1.193 + for (int k = 0; k < vec.size(); ++k) {
1.194 + *b = std::make_pair(vec.index(k), vec.value(k));
1.195 + ++b;
1.196 + }
1.197 + }
1.198 +
1.199 + void LpSoplex::_setCoeff(int i, int j, Value value) {
1.200 + soplex->changeElement(i, j, value);
1.201 + }
1.202 +
1.203 + LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
1.204 + return soplex->rowVector(i)[j];
1.205 + }
1.206 +
1.207 + void LpSoplex::_setColLowerBound(int i, Value value) {
1.208 + LEMON_ASSERT(value != INF, "Invalid bound");
1.209 + soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
1.210 + }
1.211 +
1.212 + LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
1.213 + double value = soplex->lower(i);
1.214 + return value != -soplex::infinity ? value : -INF;
1.215 + }
1.216 +
1.217 + void LpSoplex::_setColUpperBound(int i, Value value) {
1.218 + LEMON_ASSERT(value != -INF, "Invalid bound");
1.219 + soplex->changeUpper(i, value != INF ? value : soplex::infinity);
1.220 + }
1.221 +
1.222 + LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
1.223 + double value = soplex->upper(i);
1.224 + return value != soplex::infinity ? value : INF;
1.225 + }
1.226 +
1.227 + void LpSoplex::_setRowLowerBound(int i, Value lb) {
1.228 + LEMON_ASSERT(lb != INF, "Invalid bound");
1.229 + soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
1.230 + }
1.231 +
1.232 + LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const {
1.233 + double res = soplex->lhs(i);
1.234 + return res == -soplex::infinity ? -INF : res;
1.235 + }
1.236 +
1.237 + void LpSoplex::_setRowUpperBound(int i, Value ub) {
1.238 + LEMON_ASSERT(ub != -INF, "Invalid bound");
1.239 + soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
1.240 + }
1.241 +
1.242 + LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const {
1.243 + double res = soplex->rhs(i);
1.244 + return res == soplex::infinity ? INF : res;
1.245 + }
1.246 +
1.247 + void LpSoplex::_setObjCoeffs(ExprIterator b, ExprIterator e) {
1.248 + for (int j = 0; j < soplex->nCols(); ++j) {
1.249 + soplex->changeObj(j, 0.0);
1.250 + }
1.251 + for (ExprIterator it = b; it != e; ++it) {
1.252 + soplex->changeObj(it->first, it->second);
1.253 + }
1.254 + }
1.255 +
1.256 + void LpSoplex::_getObjCoeffs(InsertIterator b) const {
1.257 + for (int j = 0; j < soplex->nCols(); ++j) {
1.258 + Value coef = soplex->obj(j);
1.259 + if (coef != 0.0) {
1.260 + *b = std::make_pair(j, coef);
1.261 + ++b;
1.262 + }
1.263 + }
1.264 + }
1.265 +
1.266 + void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
1.267 + soplex->changeObj(i, obj_coef);
1.268 + }
1.269 +
1.270 + LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
1.271 + return soplex->obj(i);
1.272 + }
1.273 +
1.274 + LpSoplex::SolveExitStatus LpSoplex::_solve() {
1.275 +
1.276 + _clear_temporals();
1.277 +
1.278 + soplex::SPxSolver::Status status = soplex->solve();
1.279 +
1.280 + switch (status) {
1.281 + case soplex::SPxSolver::OPTIMAL:
1.282 + case soplex::SPxSolver::INFEASIBLE:
1.283 + case soplex::SPxSolver::UNBOUNDED:
1.284 + return SOLVED;
1.285 + default:
1.286 + return UNSOLVED;
1.287 + }
1.288 + }
1.289 +
1.290 + LpSoplex::Value LpSoplex::_getPrimal(int i) const {
1.291 + if (_primal_values.empty()) {
1.292 + _primal_values.resize(soplex->nCols());
1.293 + soplex::Vector pv(_primal_values.size(), &_primal_values.front());
1.294 + soplex->getPrimal(pv);
1.295 + }
1.296 + return _primal_values[i];
1.297 + }
1.298 +
1.299 + LpSoplex::Value LpSoplex::_getDual(int i) const {
1.300 + if (_dual_values.empty()) {
1.301 + _dual_values.resize(soplex->nRows());
1.302 + soplex::Vector dv(_dual_values.size(), &_dual_values.front());
1.303 + soplex->getDual(dv);
1.304 + }
1.305 + return _dual_values[i];
1.306 + }
1.307 +
1.308 + LpSoplex::Value LpSoplex::_getPrimalValue() const {
1.309 + return soplex->objValue();
1.310 + }
1.311 +
1.312 + LpSoplex::VarStatus LpSoplex::_getColStatus(int i) const {
1.313 + switch (soplex->getBasisColStatus(i)) {
1.314 + case soplex::SPxSolver::BASIC:
1.315 + return BASIC;
1.316 + case soplex::SPxSolver::ON_UPPER:
1.317 + return UPPER;
1.318 + case soplex::SPxSolver::ON_LOWER:
1.319 + return LOWER;
1.320 + case soplex::SPxSolver::FIXED:
1.321 + return FIXED;
1.322 + case soplex::SPxSolver::ZERO:
1.323 + return FREE;
1.324 + default:
1.325 + LEMON_ASSERT(false, "Wrong column status");
1.326 + return VarStatus();
1.327 + }
1.328 + }
1.329 +
1.330 + LpSoplex::VarStatus LpSoplex::_getRowStatus(int i) const {
1.331 + switch (soplex->getBasisRowStatus(i)) {
1.332 + case soplex::SPxSolver::BASIC:
1.333 + return BASIC;
1.334 + case soplex::SPxSolver::ON_UPPER:
1.335 + return UPPER;
1.336 + case soplex::SPxSolver::ON_LOWER:
1.337 + return LOWER;
1.338 + case soplex::SPxSolver::FIXED:
1.339 + return FIXED;
1.340 + case soplex::SPxSolver::ZERO:
1.341 + return FREE;
1.342 + default:
1.343 + LEMON_ASSERT(false, "Wrong row status");
1.344 + return VarStatus();
1.345 + }
1.346 + }
1.347 +
1.348 + LpSoplex::Value LpSoplex::_getPrimalRay(int i) const {
1.349 + if (_primal_ray.empty()) {
1.350 + _primal_ray.resize(soplex->nCols());
1.351 + soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
1.352 + soplex->getDualfarkas(pv);
1.353 + }
1.354 + return _primal_ray[i];
1.355 + }
1.356 +
1.357 + LpSoplex::Value LpSoplex::_getDualRay(int i) const {
1.358 + if (_dual_ray.empty()) {
1.359 + _dual_ray.resize(soplex->nRows());
1.360 + soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
1.361 + soplex->getDualfarkas(dv);
1.362 + }
1.363 + return _dual_ray[i];
1.364 + }
1.365 +
1.366 + LpSoplex::ProblemType LpSoplex::_getPrimalType() const {
1.367 + switch (soplex->status()) {
1.368 + case soplex::SPxSolver::OPTIMAL:
1.369 + return OPTIMAL;
1.370 + case soplex::SPxSolver::UNBOUNDED:
1.371 + return UNBOUNDED;
1.372 + case soplex::SPxSolver::INFEASIBLE:
1.373 + return INFEASIBLE;
1.374 + default:
1.375 + return UNDEFINED;
1.376 + }
1.377 + }
1.378 +
1.379 + LpSoplex::ProblemType LpSoplex::_getDualType() const {
1.380 + switch (soplex->status()) {
1.381 + case soplex::SPxSolver::OPTIMAL:
1.382 + return OPTIMAL;
1.383 + case soplex::SPxSolver::UNBOUNDED:
1.384 + return UNBOUNDED;
1.385 + case soplex::SPxSolver::INFEASIBLE:
1.386 + return INFEASIBLE;
1.387 + default:
1.388 + return UNDEFINED;
1.389 + }
1.390 + }
1.391 +
1.392 + void LpSoplex::_setSense(Sense sense) {
1.393 + switch (sense) {
1.394 + case MIN:
1.395 + soplex->changeSense(soplex::SPxSolver::MINIMIZE);
1.396 + break;
1.397 + case MAX:
1.398 + soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
1.399 + }
1.400 + }
1.401 +
1.402 + LpSoplex::Sense LpSoplex::_getSense() const {
1.403 + switch (soplex->spxSense()) {
1.404 + case soplex::SPxSolver::MAXIMIZE:
1.405 + return MAX;
1.406 + case soplex::SPxSolver::MINIMIZE:
1.407 + return MIN;
1.408 + default:
1.409 + LEMON_ASSERT(false, "Wrong sense.");
1.410 + return LpSoplex::Sense();
1.411 + }
1.412 + }
1.413 +
1.414 + void LpSoplex::_clear() {
1.415 + soplex->clear();
1.416 + _col_names.clear();
1.417 + _col_names_ref.clear();
1.418 + _row_names.clear();
1.419 + _row_names_ref.clear();
1.420 + cols.clear();
1.421 + rows.clear();
1.422 + _clear_temporals();
1.423 + }
1.424 +
1.425 +} //namespace lemon
1.426 +