1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/lp_base.h Tue Apr 05 09:08:23 2005 +0000
1.3 @@ -0,0 +1,823 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_LP_BASE_H
1.21 +#define LEMON_LP_BASE_H
1.22 +
1.23 +#include<vector>
1.24 +#include<map>
1.25 +#include<limits>
1.26 +#include<math.h>
1.27 +
1.28 +#include<lemon/utility.h>
1.29 +#include<lemon/error.h>
1.30 +#include<lemon/invalid.h>
1.31 +
1.32 +//#include"lin_expr.h"
1.33 +
1.34 +///\file
1.35 +///\brief The interface of the LP solver interface.
1.36 +namespace lemon {
1.37 +
1.38 + ///Internal data structure to convert floating id's to fix one's
1.39 +
1.40 + ///\todo This might be implemented to be also usable in other places.
1.41 + class _FixId
1.42 + {
1.43 + std::vector<int> index;
1.44 + std::vector<int> cross;
1.45 + int first_free;
1.46 + public:
1.47 + _FixId() : first_free(-1) {};
1.48 + ///Convert a floating id to a fix one
1.49 +
1.50 + ///\param n is a floating id
1.51 + ///\return the corresponding fix id
1.52 + int fixId(int n) {return cross[n];}
1.53 + ///Convert a fix id to a floating one
1.54 +
1.55 + ///\param n is a fix id
1.56 + ///\return the corresponding floating id
1.57 + int floatingId(int n) { return index[n];}
1.58 + ///Add a new floating id.
1.59 +
1.60 + ///\param n is a floating id
1.61 + ///\return the fix id of the new value
1.62 + ///\todo Multiple additions should also be handled.
1.63 + int insert(int n)
1.64 + {
1.65 + if(n>=int(cross.size())) {
1.66 + cross.resize(n+1);
1.67 + if(first_free==-1) {
1.68 + cross[n]=index.size();
1.69 + index.push_back(n);
1.70 + }
1.71 + else {
1.72 + cross[n]=first_free;
1.73 + int next=index[first_free];
1.74 + index[first_free]=n;
1.75 + first_free=next;
1.76 + }
1.77 + return cross[n];
1.78 + }
1.79 + ///\todo Create an own exception type.
1.80 + else throw LogicError(); //floatingId-s must form a continuous range;
1.81 + }
1.82 + ///Remove a fix id.
1.83 +
1.84 + ///\param n is a fix id
1.85 + ///
1.86 + void erase(int n)
1.87 + {
1.88 + int fl=index[n];
1.89 + index[n]=first_free;
1.90 + first_free=n;
1.91 + for(int i=fl+1;i<int(cross.size());++i) {
1.92 + cross[i-1]=cross[i];
1.93 + index[cross[i]]--;
1.94 + }
1.95 + cross.pop_back();
1.96 + }
1.97 + ///An upper bound on the largest fix id.
1.98 +
1.99 + ///\todo Do we need this?
1.100 + ///
1.101 + std::size_t maxFixId() { return cross.size()-1; }
1.102 +
1.103 + };
1.104 +
1.105 + ///Common base class for LP solvers
1.106 + class LpSolverBase {
1.107 +
1.108 + public:
1.109 +
1.110 + ///\e
1.111 + enum SolveExitStatus {
1.112 + ///\e
1.113 + SOLVED = 0,
1.114 + ///\e
1.115 + UNSOLVED = 1
1.116 + };
1.117 +
1.118 + ///\e
1.119 + enum SolutionStatus {
1.120 + ///Feasible solution has'n been found (but may exist).
1.121 +
1.122 + ///\todo NOTFOUND might be a better name.
1.123 + ///
1.124 + UNDEFINED = 0,
1.125 + ///The problem has no feasible solution
1.126 + INFEASIBLE = 1,
1.127 + ///Feasible solution found
1.128 + FEASIBLE = 2,
1.129 + ///Optimal solution exists and found
1.130 + OPTIMAL = 3,
1.131 + ///The cost function is unbounded
1.132 +
1.133 + ///\todo Give a feasible solution and an infinite ray (and the
1.134 + ///corresponding bases)
1.135 + INFINITE = 4
1.136 + };
1.137 +
1.138 + ///The floating point type used by the solver
1.139 + typedef double Value;
1.140 + ///The infinity constant
1.141 + static const Value INF;
1.142 + ///The not a number constant
1.143 + static const Value NaN;
1.144 +
1.145 + ///Refer to a column of the LP.
1.146 +
1.147 + ///This type is used to refer to a column of the LP.
1.148 + ///
1.149 + ///Its value remains valid and correct even after the addition or erase of
1.150 + ///other columns.
1.151 + ///
1.152 + ///\todo Document what can one do with a Col (INVALID, comparing,
1.153 + ///it is similar to Node/Edge)
1.154 + class Col {
1.155 + protected:
1.156 + int id;
1.157 + friend class LpSolverBase;
1.158 + public:
1.159 + typedef Value ExprValue;
1.160 + typedef True LpSolverCol;
1.161 + Col() {}
1.162 + Col(const Invalid&) : id(-1) {}
1.163 + bool operator<(Col c) const {return id<c.id;}
1.164 + bool operator==(Col c) const {return id==c.id;}
1.165 + bool operator!=(Col c) const {return id==c.id;}
1.166 + };
1.167 +
1.168 + ///Refer to a row of the LP.
1.169 +
1.170 + ///This type is used to refer to a row of the LP.
1.171 + ///
1.172 + ///Its value remains valid and correct even after the addition or erase of
1.173 + ///other rows.
1.174 + ///
1.175 + ///\todo Document what can one do with a Row (INVALID, comparing,
1.176 + ///it is similar to Node/Edge)
1.177 + class Row {
1.178 + protected:
1.179 + int id;
1.180 + friend class LpSolverBase;
1.181 + public:
1.182 + typedef Value ExprValue;
1.183 + typedef True LpSolverRow;
1.184 + Row() {}
1.185 + Row(const Invalid&) : id(-1) {}
1.186 + typedef True LpSolverRow;
1.187 + bool operator<(Row c) const {return id<c.id;}
1.188 + bool operator==(Row c) const {return id==c.id;}
1.189 + bool operator!=(Row c) const {return id==c.id;}
1.190 + };
1.191 +
1.192 + ///Linear expression of variables and a constant component
1.193 +
1.194 + ///This data structure strores a linear expression of the variables
1.195 + ///(\ref Col "Col"s) and also has a constant component.
1.196 + ///
1.197 + ///There are several ways to access and modify the contents of this
1.198 + ///container.
1.199 + ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
1.200 + ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can
1.201 + ///read and modify the coefficients like
1.202 + ///these.
1.203 + ///\code
1.204 + ///e[v]=5;
1.205 + ///e[v]+=12;
1.206 + ///e.erase(v);
1.207 + ///\endcode
1.208 + ///or you can also iterate through its elements.
1.209 + ///\code
1.210 + ///double s=0;
1.211 + ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
1.212 + /// s+=i->second;
1.213 + ///\endcode
1.214 + ///(This code computes the sum of all coefficients).
1.215 + ///- Numbers (<tt>double</tt>'s)
1.216 + ///and variables (\ref Col "Col"s) directly convert to an
1.217 + ///\ref Expr and the usual linear operations are defined so
1.218 + ///\code
1.219 + ///v+w
1.220 + ///2*v-3.12*(v-w/2)+2
1.221 + ///v*2.1+(3*v+(v*12+w+6)*3)/2
1.222 + ///\endcode
1.223 + ///are valid expressions. The usual assignment operations are also defined.
1.224 + ///\code
1.225 + ///e=v+w;
1.226 + ///e+=2*v-3.12*(v-w/2)+2;
1.227 + ///e*=3.4;
1.228 + ///e/=5;
1.229 + ///\endcode
1.230 + ///- The constant member can be set and read by \ref constComp()
1.231 + ///\code
1.232 + ///e.constComp()=12;
1.233 + ///double c=e.constComp();
1.234 + ///\endcode
1.235 + ///
1.236 + ///\note that \ref clear() not only sets all coefficients to 0 but also
1.237 + ///clears the constant components.
1.238 + class Expr : public std::map<Col,Value>
1.239 + {
1.240 + public:
1.241 + typedef LpSolverBase::Col Key;
1.242 + typedef LpSolverBase::Value Value;
1.243 +
1.244 + protected:
1.245 + typedef std::map<Col,Value> Base;
1.246 +
1.247 + Value const_comp;
1.248 + public:
1.249 + typedef True IsLinExpression;
1.250 + ///\e
1.251 + Expr() : Base(), const_comp(0) { }
1.252 + ///\e
1.253 + Expr(const Key &v) : const_comp(0) {
1.254 + Base::insert(std::make_pair(v, 1));
1.255 + }
1.256 + ///\e
1.257 + Expr(const Value &v) : const_comp(v) {}
1.258 + ///\e
1.259 + void set(const Key &v,const Value &c) {
1.260 + Base::insert(std::make_pair(v, c));
1.261 + }
1.262 + ///\e
1.263 + Value &constComp() { return const_comp; }
1.264 + ///\e
1.265 + const Value &constComp() const { return const_comp; }
1.266 +
1.267 + ///Removes the components with zero coefficient.
1.268 + void simplify() {
1.269 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
1.270 + Base::iterator j=i;
1.271 + ++j;
1.272 + if ((*i).second==0) Base::erase(i);
1.273 + j=i;
1.274 + }
1.275 + }
1.276 +
1.277 + ///Sets all coefficients and the constant component to 0.
1.278 + void clear() {
1.279 + Base::clear();
1.280 + const_comp=0;
1.281 + }
1.282 +
1.283 + ///\e
1.284 + Expr &operator+=(const Expr &e) {
1.285 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.286 + (*this)[j->first]+=j->second;
1.287 + ///\todo it might be speeded up using "hints"
1.288 + const_comp+=e.const_comp;
1.289 + return *this;
1.290 + }
1.291 + ///\e
1.292 + Expr &operator-=(const Expr &e) {
1.293 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.294 + (*this)[j->first]-=j->second;
1.295 + const_comp-=e.const_comp;
1.296 + return *this;
1.297 + }
1.298 + ///\e
1.299 + Expr &operator*=(const Value &c) {
1.300 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.301 + j->second*=c;
1.302 + const_comp*=c;
1.303 + return *this;
1.304 + }
1.305 + ///\e
1.306 + Expr &operator/=(const Value &c) {
1.307 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.308 + j->second/=c;
1.309 + const_comp/=c;
1.310 + return *this;
1.311 + }
1.312 + };
1.313 +
1.314 + ///Linear constraint
1.315 + //typedef LinConstr<Expr> Constr;
1.316 + class Constr
1.317 + {
1.318 + public:
1.319 + typedef LpSolverBase::Expr Expr;
1.320 + typedef Expr::Key Key;
1.321 + typedef Expr::Value Value;
1.322 +
1.323 + static const Value INF;
1.324 + static const Value NaN;
1.325 + // static const Value INF=0;
1.326 + // static const Value NaN=1;
1.327 +
1.328 + protected:
1.329 + Expr _expr;
1.330 + Value _lb,_ub;
1.331 + public:
1.332 + ///\e
1.333 + Constr() : _expr(), _lb(NaN), _ub(NaN) {}
1.334 + ///\e
1.335 + Constr(Value lb,const Expr &e,Value ub) :
1.336 + _expr(e), _lb(lb), _ub(ub) {}
1.337 + ///\e
1.338 + Constr(const Expr &e,Value ub) :
1.339 + _expr(e), _lb(NaN), _ub(ub) {}
1.340 + ///\e
1.341 + Constr(Value lb,const Expr &e) :
1.342 + _expr(e), _lb(lb), _ub(NaN) {}
1.343 + ///\e
1.344 + Constr(const Expr &e) :
1.345 + _expr(e), _lb(NaN), _ub(NaN) {}
1.346 + ///\e
1.347 + void clear()
1.348 + {
1.349 + _expr.clear();
1.350 + _lb=_ub=NaN;
1.351 + }
1.352 + ///\e
1.353 + Expr &expr() { return _expr; }
1.354 + ///\e
1.355 + const Expr &expr() const { return _expr; }
1.356 + ///\e
1.357 + Value &lowerBound() { return _lb; }
1.358 + ///\e
1.359 + const Value &lowerBound() const { return _lb; }
1.360 + ///\e
1.361 + Value &upperBound() { return _ub; }
1.362 + ///\e
1.363 + const Value &upperBound() const { return _ub; }
1.364 + ///\e
1.365 + bool lowerBounded() const {
1.366 + using namespace std;
1.367 + return isfinite(_lb);
1.368 + }
1.369 + ///\e
1.370 + bool upperBounded() const {
1.371 + using namespace std;
1.372 + return isfinite(_ub);
1.373 + }
1.374 + };
1.375 +
1.376 +
1.377 + protected:
1.378 + _FixId rows;
1.379 + _FixId cols;
1.380 +
1.381 + virtual int _addCol() = 0;
1.382 + virtual int _addRow() = 0;
1.383 + virtual void _setRowCoeffs(int i,
1.384 + int length,
1.385 + int const * indices,
1.386 + Value const * values ) = 0;
1.387 + virtual void _setColCoeffs(int i,
1.388 + int length,
1.389 + int const * indices,
1.390 + Value const * values ) = 0;
1.391 + virtual void _setColLowerBound(int i, Value value) = 0;
1.392 + virtual void _setColUpperBound(int i, Value value) = 0;
1.393 + virtual void _setRowLowerBound(int i, Value value) = 0;
1.394 + virtual void _setRowUpperBound(int i, Value value) = 0;
1.395 + virtual void _setObjCoeff(int i, Value obj_coef) = 0;
1.396 + virtual SolveExitStatus _solve() = 0;
1.397 + virtual Value _getPrimal(int i) = 0;
1.398 + virtual SolutionStatus _getPrimalType() = 0;
1.399 +
1.400 +
1.401 + void clearObj() {}
1.402 + public:
1.403 +
1.404 +
1.405 + ///\e
1.406 + virtual ~LpSolverBase() {}
1.407 +
1.408 + ///\name Build up and modify of the LP
1.409 +
1.410 + ///@{
1.411 +
1.412 + ///Add a new empty column (i.e a new variable) to the LP
1.413 + Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
1.414 +
1.415 + ///\brief Adds several new columns
1.416 + ///(i.e a variables) at once
1.417 + ///
1.418 + ///This magic function takes a container as its argument
1.419 + ///and fills its elements
1.420 + ///with new columns (i.e. variables)
1.421 + ///\param t can be
1.422 + ///- a standard STL compatible iterable container with
1.423 + ///\ref Col as its \c values_type
1.424 + ///like
1.425 + ///\code
1.426 + ///std::vector<LpSolverBase::Col>
1.427 + ///std::list<LpSolverBase::Col>
1.428 + ///\endcode
1.429 + ///- a standard STL compatible iterable container with
1.430 + ///\ref Col as its \c mapped_type
1.431 + ///like
1.432 + ///\code
1.433 + ///std::map<AnyType,LpSolverBase::Col>
1.434 + ///\endcode
1.435 + ///- an iterable lemon \ref concept::WriteMap "write map" like
1.436 + ///\code
1.437 + ///ListGraph::NodeMap<LpSolverBase::Col>
1.438 + ///ListGraph::EdgeMap<LpSolverBase::Col>
1.439 + ///\endcode
1.440 + ///\return The number of the created column.
1.441 + ///\bug Iterable nodemap hasn't been implemented yet.
1.442 +#ifdef DOXYGEN
1.443 + template<class T>
1.444 + int addColSet(T &t) { return 0;}
1.445 +#else
1.446 + template<class T>
1.447 + typename enable_if<typename T::value_type::LpSolverCol,int>::type
1.448 + addColSet(T &t,dummy<0> = 0) {
1.449 + int s=0;
1.450 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
1.451 + return s;
1.452 + }
1.453 + template<class T>
1.454 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
1.455 + int>::type
1.456 + addColSet(T &t,dummy<1> = 1) {
1.457 + int s=0;
1.458 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.459 + i->second=addCol();
1.460 + s++;
1.461 + }
1.462 + return s;
1.463 + }
1.464 + template<class T>
1.465 + typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
1.466 + int>::type
1.467 + addColSet(T &t,dummy<2> = 2) {
1.468 + ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
1.469 + int s=0;
1.470 + for(typename T::ValueSet::iterator i=t.valueSet().begin();
1.471 + i!=t.valueSet().end();
1.472 + ++i)
1.473 + {
1.474 + *i=addCol();
1.475 + s++;
1.476 + }
1.477 + return s;
1.478 + }
1.479 +#endif
1.480 +
1.481 + ///Add a new empty row (i.e a new constaint) to the LP
1.482 +
1.483 + ///This function adds a new empty row (i.e a new constaint) to the LP.
1.484 + ///\return The created row
1.485 + Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
1.486 +
1.487 + ///Set a row (i.e a constaint) of the LP
1.488 +
1.489 + ///\param r is the row to be modified
1.490 + ///\param l is lower bound (-\ref INF means no bound)
1.491 + ///\param e is a linear expression (see \ref Expr)
1.492 + ///\param u is the upper bound (\ref INF means no bound)
1.493 + ///\bug This is a temportary function. The interface will change to
1.494 + ///a better one.
1.495 + void setRow(Row r, Value l,const Expr &e, Value u) {
1.496 + std::vector<int> indices;
1.497 + std::vector<Value> values;
1.498 + indices.push_back(0);
1.499 + values.push_back(0);
1.500 + for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
1.501 + if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
1.502 + indices.push_back(cols.floatingId((*i).first.id));
1.503 + values.push_back((*i).second);
1.504 + }
1.505 + _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
1.506 + &indices[0],&values[0]);
1.507 + _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
1.508 + _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
1.509 + }
1.510 +
1.511 + ///Set a row (i.e a constaint) of the LP
1.512 +
1.513 + ///\param r is the row to be modified
1.514 + ///\param c is a linear expression (see \ref Constr)
1.515 + void setRow(Row r, const Constr &c) {
1.516 + setRow(r,
1.517 + c.lowerBounded()?c.lowerBound():-INF,
1.518 + c.expr(),
1.519 + c.upperBounded()?c.upperBound():INF);
1.520 + }
1.521 +
1.522 + ///Add a new row (i.e a new constaint) to the LP
1.523 +
1.524 + ///\param l is the lower bound (-\ref INF means no bound)
1.525 + ///\param e is a linear expression (see \ref Expr)
1.526 + ///\param u is the upper bound (\ref INF means no bound)
1.527 + ///\return The created row.
1.528 + ///\bug This is a temportary function. The interface will change to
1.529 + ///a better one.
1.530 + Row addRow(Value l,const Expr &e, Value u) {
1.531 + Row r=addRow();
1.532 + setRow(r,l,e,u);
1.533 + return r;
1.534 + }
1.535 +
1.536 + ///Add a new row (i.e a new constaint) to the LP
1.537 +
1.538 + ///\param c is a linear expression (see \ref Constr)
1.539 + ///\return The created row.
1.540 + Row addRow(const Constr &c) {
1.541 + Row r=addRow();
1.542 + setRow(r,c);
1.543 + return r;
1.544 + }
1.545 +
1.546 + /// Set the lower bound of a column (i.e a variable)
1.547 +
1.548 + /// The upper bound of a variable (column) has to be given by an
1.549 + /// extended number of type Value, i.e. a finite number of type
1.550 + /// Value or -\ref INF.
1.551 + void colLowerBound(Col c, Value value) {
1.552 + _setColLowerBound(cols.floatingId(c.id),value);
1.553 + }
1.554 + /// Set the upper bound of a column (i.e a variable)
1.555 +
1.556 + /// The upper bound of a variable (column) has to be given by an
1.557 + /// extended number of type Value, i.e. a finite number of type
1.558 + /// Value or \ref INF.
1.559 + void colUpperBound(Col c, Value value) {
1.560 + _setColUpperBound(cols.floatingId(c.id),value);
1.561 + };
1.562 + /// Set the lower and the upper bounds of a column (i.e a variable)
1.563 +
1.564 + /// The lower and the upper bounds of
1.565 + /// a variable (column) have to be given by an
1.566 + /// extended number of type Value, i.e. a finite number of type
1.567 + /// Value, -\ref INF or \ref INF.
1.568 + void colBounds(Col c, Value lower, Value upper) {
1.569 + _setColLowerBound(cols.floatingId(c.id),lower);
1.570 + _setColUpperBound(cols.floatingId(c.id),upper);
1.571 + }
1.572 +
1.573 + /// Set the lower bound of a row (i.e a constraint)
1.574 +
1.575 + /// The lower bound of a linear expression (row) has to be given by an
1.576 + /// extended number of type Value, i.e. a finite number of type
1.577 + /// Value or -\ref INF.
1.578 + void rowLowerBound(Row r, Value value) {
1.579 + _setRowLowerBound(rows.floatingId(r.id),value);
1.580 + };
1.581 + /// Set the upper bound of a row (i.e a constraint)
1.582 +
1.583 + /// The upper bound of a linear expression (row) has to be given by an
1.584 + /// extended number of type Value, i.e. a finite number of type
1.585 + /// Value or \ref INF.
1.586 + void rowUpperBound(Row r, Value value) {
1.587 + _setRowUpperBound(rows.floatingId(r.id),value);
1.588 + };
1.589 + /// Set the lower and the upper bounds of a row (i.e a variable)
1.590 +
1.591 + /// The lower and the upper bounds of
1.592 + /// a constraint (row) have to be given by an
1.593 + /// extended number of type Value, i.e. a finite number of type
1.594 + /// Value, -\ref INF or \ref INF.
1.595 + void rowBounds(Row c, Value lower, Value upper) {
1.596 + _setRowLowerBound(rows.floatingId(c.id),lower);
1.597 + _setRowUpperBound(rows.floatingId(c.id),upper);
1.598 + }
1.599 +
1.600 + ///Set an element of the objective function
1.601 + void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
1.602 + ///Set the objective function
1.603 +
1.604 + ///\param e is a linear expression of type \ref Expr.
1.605 + ///\todo What to do with the constant component?
1.606 + void setObj(Expr e) {
1.607 + clearObj();
1.608 + for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
1.609 + objCoeff((*i).first,(*i).second);
1.610 + }
1.611 +
1.612 + ///@}
1.613 +
1.614 +
1.615 + ///\name Solve the LP
1.616 +
1.617 + ///@{
1.618 +
1.619 + ///\e
1.620 + SolveExitStatus solve() { return _solve(); }
1.621 +
1.622 + ///@}
1.623 +
1.624 + ///\name Obtain the solution
1.625 +
1.626 + ///@{
1.627 +
1.628 + ///\e
1.629 + SolutionStatus primalType() {
1.630 + return _getPrimalType();
1.631 + }
1.632 +
1.633 + ///\e
1.634 + Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
1.635 +
1.636 + ///@}
1.637 +
1.638 + };
1.639 +
1.640 + ///\e
1.641 +
1.642 + ///\relates LpSolverBase::Expr
1.643 + ///
1.644 + inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1.645 + const LpSolverBase::Expr &b)
1.646 + {
1.647 + LpSolverBase::Expr tmp(a);
1.648 + tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
1.649 + return tmp;
1.650 + }
1.651 + ///\e
1.652 +
1.653 + ///\relates LpSolverBase::Expr
1.654 + ///
1.655 + inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1.656 + const LpSolverBase::Expr &b)
1.657 + {
1.658 + LpSolverBase::Expr tmp(a);
1.659 + tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
1.660 + return tmp;
1.661 + }
1.662 + ///\e
1.663 +
1.664 + ///\relates LpSolverBase::Expr
1.665 + ///
1.666 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1.667 + const LpSolverBase::Value &b)
1.668 + {
1.669 + LpSolverBase::Expr tmp(a);
1.670 + tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
1.671 + return tmp;
1.672 + }
1.673 +
1.674 + ///\e
1.675 +
1.676 + ///\relates LpSolverBase::Expr
1.677 + ///
1.678 + inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1.679 + const LpSolverBase::Expr &b)
1.680 + {
1.681 + LpSolverBase::Expr tmp(b);
1.682 + tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
1.683 + return tmp;
1.684 + }
1.685 + ///\e
1.686 +
1.687 + ///\relates LpSolverBase::Expr
1.688 + ///
1.689 + inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1.690 + const LpSolverBase::Value &b)
1.691 + {
1.692 + LpSolverBase::Expr tmp(a);
1.693 + tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
1.694 + return tmp;
1.695 + }
1.696 +
1.697 + ///\e
1.698 +
1.699 + ///\relates LpSolverBase::Constr
1.700 + ///
1.701 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1.702 + const LpSolverBase::Expr &f)
1.703 + {
1.704 + return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1.705 + }
1.706 +
1.707 + ///\e
1.708 +
1.709 + ///\relates LpSolverBase::Constr
1.710 + ///
1.711 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1.712 + const LpSolverBase::Expr &f)
1.713 + {
1.714 + return LpSolverBase::Constr(e,f);
1.715 + }
1.716 +
1.717 + ///\e
1.718 +
1.719 + ///\relates LpSolverBase::Constr
1.720 + ///
1.721 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1.722 + const LpSolverBase::Value &f)
1.723 + {
1.724 + return LpSolverBase::Constr(e,f);
1.725 + }
1.726 +
1.727 + ///\e
1.728 +
1.729 + ///\relates LpSolverBase::Constr
1.730 + ///
1.731 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1.732 + const LpSolverBase::Expr &f)
1.733 + {
1.734 + return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1.735 + }
1.736 +
1.737 +
1.738 + ///\e
1.739 +
1.740 + ///\relates LpSolverBase::Constr
1.741 + ///
1.742 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1.743 + const LpSolverBase::Expr &f)
1.744 + {
1.745 + return LpSolverBase::Constr(f,e);
1.746 + }
1.747 +
1.748 +
1.749 + ///\e
1.750 +
1.751 + ///\relates LpSolverBase::Constr
1.752 + ///
1.753 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1.754 + const LpSolverBase::Value &f)
1.755 + {
1.756 + return LpSolverBase::Constr(f,e);
1.757 + }
1.758 +
1.759 + ///\e
1.760 +
1.761 + ///\relates LpSolverBase::Constr
1.762 + ///
1.763 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1.764 + const LpSolverBase::Expr &f)
1.765 + {
1.766 + return LpSolverBase::Constr(0,e-f,0);
1.767 + }
1.768 +
1.769 + ///\e
1.770 +
1.771 + ///\relates LpSolverBase::Constr
1.772 + ///
1.773 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1.774 + const LpSolverBase::Constr&c)
1.775 + {
1.776 + LpSolverBase::Constr tmp(c);
1.777 + ///\todo Create an own exception type.
1.778 + if(!isnan(tmp.lowerBound())) throw LogicError();
1.779 + else tmp.lowerBound()=n;
1.780 + return tmp;
1.781 + }
1.782 + ///\e
1.783 +
1.784 + ///\relates LpSolverBase::Constr
1.785 + ///
1.786 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1.787 + const LpSolverBase::Value &n)
1.788 + {
1.789 + LpSolverBase::Constr tmp(c);
1.790 + ///\todo Create an own exception type.
1.791 + if(!isnan(tmp.upperBound())) throw LogicError();
1.792 + else tmp.upperBound()=n;
1.793 + return tmp;
1.794 + }
1.795 +
1.796 + ///\e
1.797 +
1.798 + ///\relates LpSolverBase::Constr
1.799 + ///
1.800 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1.801 + const LpSolverBase::Constr&c)
1.802 + {
1.803 + LpSolverBase::Constr tmp(c);
1.804 + ///\todo Create an own exception type.
1.805 + if(!isnan(tmp.upperBound())) throw LogicError();
1.806 + else tmp.upperBound()=n;
1.807 + return tmp;
1.808 + }
1.809 + ///\e
1.810 +
1.811 + ///\relates LpSolverBase::Constr
1.812 + ///
1.813 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1.814 + const LpSolverBase::Value &n)
1.815 + {
1.816 + LpSolverBase::Constr tmp(c);
1.817 + ///\todo Create an own exception type.
1.818 + if(!isnan(tmp.lowerBound())) throw LogicError();
1.819 + else tmp.lowerBound()=n;
1.820 + return tmp;
1.821 + }
1.822 +
1.823 +
1.824 +} //namespace lemon
1.825 +
1.826 +#endif //LEMON_LP_BASE_H