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