1.1 --- a/src/lemon/lp_base.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,907 +0,0 @@
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 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