lemon-0.x: src/work/athos/lp/lin

     1 /* -*- C++ -*-

     2  * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_LIN_EXPR_H

    18 #define LEMON_LIN_EXPR_H

    20 #include<vector>

    21 #include<map>

    22 #include<lemon/utility.h>

    23 ///\file

    24 ///\brief Classes to handle linear expressions

    25 namespace lemon {

    27   /// Class to handle sparse linear expressions

    28   template <class _V>

    29   class SparseLinExpr : public std::map<_V, typename _V::ExprValue>

    30   {

    31   public:

    32     typedef _V Var;

    33     typedef typename _V::ExprValue Coeff;

    35   protected:

    36     typedef typename std::map<_V, typename _V::ExprValue> Base;

    38     Coeff const_comp;

    39   public:

    40     typedef True IsLinExpression;

    41     ///\e

    42     SparseLinExpr() : Base(), const_comp(0) { }

    43     ///\e

    44     SparseLinExpr(const Var &v) : const_comp(0) {

    45       Base::insert(std::make_pair(v, 1));

    46     }

    47     ///\e

    48     SparseLinExpr(const Coeff &v) : const_comp(v) {}

    50     ///\e

    51     void set(const Var &v,const Coeff &c) {

    52       return Base::insert(std::make_pair(v, c));

    53     }

    54 //     Coeff &operator[](const Var &v) { return data[v]; }

    55 //     const Coeff &operator[](const Var &v) const { return data[v]; }

    57     ///\e

    58     Coeff &constComp() { return const_comp; }

    59     ///\e

    60     const Coeff &constComp() const { return const_comp; }

    62     ///Removes the components with zero coefficient.

    63     void simplify() {

    64       for (typename Base::iterator i=Base::begin(); i!=Base::end();) {

    65 	typename Base::iterator j=i;

    66 	++j;

    67 	if ((*i).second==0) Base::erase(i);

    68 	j=i;

    69       }

    70     }

    72     ///\e

    73     SparseLinExpr &operator+=(const SparseLinExpr &e) {

    74       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)

    75 	(*this)[j->first]+=j->second;

    76       ///\todo it might be speeded up using "hints"

    77       const_comp+=e.const_comp;

    78       return *this;

    79     }

    80     ///\e

    81     SparseLinExpr &operator-=(const SparseLinExpr &e) {

    82       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)

    83 	(*this)[j->first]-=j->second;

    84       const_comp-=e.const_comp;

    85       return *this;

    86     }

    87     ///\e

    88     SparseLinExpr &operator*=(const Coeff &c) {

    89       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)

    90 	j->second*=c;

    91       const_comp*=c;

    92       return *this;

    93     }

    94     ///\e

    95     SparseLinExpr &operator/=(const Coeff &c) {

    96       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)

    97 	j->second/=c;

    98       const_comp/=c;

    99       return *this;

   100     }

   102   };

   104   ///\e

   106   ///\relates SparseLinExpr

   107   ///

   108   template <class V>

   109   SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,

   110 				const SparseLinExpr<V> &b) {

   111     SparseLinExpr<V> tmp(a);

   112     tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?

   113     return tmp;

   114   }

   116   ///\e

   118   ///\relates SparseLinExpr

   119   ///

   120   template <class V>

   121   SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,

   122 				const SparseLinExpr<V> &b) {

   123     SparseLinExpr<V> tmp(a);

   124     tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?

   125     return tmp;

   126   }

   128   ///\e

   130   ///\relates SparseLinExpr

   131   ///

   132   template <class V>

   133   SparseLinExpr<V> operator*(const typename V::ExprValue &c,

   134 			       const SparseLinExpr<V> &e) {

   135     SparseLinExpr<V> tmp(e);

   136     tmp*=c;

   137     return tmp;

   138   }

   140   ///\e

   142   ///\relates SparseLinExpr

   143   ///

   144   template <class V>

   145   SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,

   146 			       const typename V::ExprValue &c) {

   147     SparseLinExpr<V> tmp(e);

   148     tmp*=c;

   149     return tmp;

   150   }

   153   ///\e

   155   ///\relates SparseLinExpr

   156   ///

   157   template <class V>

   158   SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,

   159 			       const typename V::ExprValue &c) {

   160     SparseLinExpr<V> tmp(e);

   161     tmp/=c;

   162     return tmp;

   163   }

   165   ///\e

   167   ///\relates SparseLinExpr

   168   ///

   169   template <class V>

   170   SparseLinExpr<V> operator+(const typename V::ExprValue &c,

   171 			     const SparseLinExpr<V> &e) {

   172     SparseLinExpr<V> tmp(e);

   173     tmp.constComp()+=c;

   174     return tmp;

   175   }

   177   ///\e

   179   ///\relates SparseLinExpr

   180   ///

   181   template <class V>

   182   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,

   183 			     const typename V::ExprValue &c) {

   184     SparseLinExpr<V> tmp(e);

   185     tmp.constComp()+=c;

   186     return tmp;

   187   }

   189   ///\e

   191   ///\relates SparseLinExpr

   192   ///

   193   template <class V>

   194   SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {

   195     SparseLinExpr<V> tmp(e);

   196     tmp[v]+=1;

   197     return tmp;

   198   }

   200   ///\e

   202   ///\relates SparseLinExpr

   203   ///

   204   template <class V>

   205   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {

   206     SparseLinExpr<V> tmp(e);

   207     tmp[v]+=1;

   208     return tmp;

   209   }

   211   ///\e

   213   ///\relates SparseLinExpr

   214   ///

   215   template <class V>

   216   SparseLinExpr<V> operator-(const typename V::ExprValue &c,

   217 			     const SparseLinExpr<V> &e) {

   218     SparseLinExpr<V> tmp(e);

   219     tmp*=-1;

   220     tmp.constComp()+=c;

   221     return tmp;

   222   }

   224   ///\e

   226   ///\relates SparseLinExpr

   227   ///

   228   template <class V>

   229   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,

   230 			     const typename V::ExprValue &c) {

   231     SparseLinExpr<V> tmp(e);

   232     tmp.constComp()-=c;

   233     return tmp;

   234   }

   236   ///\e

   238   ///\relates SparseLinExpr

   239   ///

   240   template <class V>

   241   SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {

   242     SparseLinExpr<V> tmp(e);

   243     tmp*=-1;

   244     tmp[v]+=1;

   245     return tmp;

   246   }

   248   ///\e

   250   ///\relates SparseLinExpr

   251   ///

   252   template <class V>

   253   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {

   254     SparseLinExpr<V> tmp(e);

   255     tmp[v]-=1;

   256     return tmp;

   257   }

   259   ///\e

   261   ///\relates SparseLinExpr

   262   ///

   263   template <class V>

   264   SparseLinExpr<V> operator+(const V &v,const typename V::ExprValue &c) {

   265     SparseLinExpr<V> tmp(v);

   266     tmp.constComp()=c;

   267     return tmp;

   268   }

   270   ///\e

   272   ///\relates SparseLinExpr

   273   ///

   274   template <class V>

   275   SparseLinExpr<V> operator-(const V &v,const typename V::ExprValue &c) {

   276     SparseLinExpr<V> tmp(v);

   277     tmp.constComp()=-c;

   278     return tmp;

   279   }

   281   ///\e

   283   ///\relates SparseLinExpr

   284   ///

   285   template <class V>

   286   SparseLinExpr<V> operator+(const typename V::ExprValue &c,const V &v) {

   287     SparseLinExpr<V> tmp(v);

   288     tmp.constComp()=c;

   289     return tmp;

   290   }

   292   ///\e

   294   ///\relates SparseLinExpr

   295   ///

   296   template <class V>

   297   SparseLinExpr<V> operator-(const typename V::ExprValue &c,const V &v) {

   298     SparseLinExpr<V> tmp(c);

   299     tmp[v]=-1;

   300     return tmp;

   301   }

   303   ///\e

   305   ///\relates SparseLinExpr

   306   ///

   307   template <class V>

   308   SparseLinExpr<V> operator+(const V &v1,const V &v2) {

   309     SparseLinExpr<V> tmp(v1);

   310     tmp[v2]+=1;

   311     return tmp;

   312   }

   314   ///\e

   316   ///\relates SparseLinExpr

   317   ///

   318   template <class V>

   319   SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {

   320     SparseLinExpr<V> tmp;

   321     tmp[v]=c;

   322     return tmp;

   323   }

   325   ///\e

   327   ///\relates SparseLinExpr

   328   ///

   329   template <class V>

   330   SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {

   331     SparseLinExpr<V> tmp;

   332     tmp[v]=c;

   333     return tmp;

   334   }

   336   ///\e

   338   ///\relates SparseLinExpr

   339   ///

   340   template <class V>

   341   SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {

   342     SparseLinExpr<V> tmp;

   343     tmp[v]=1/c;

   344     return tmp;

   345   }

   348   //////////////////////////////////////////////////////////////////////

   349   /// Constraints

   350   //////////////////////////////////////////////////////////////////////

   352   template <class E>

   353   class LinConstr

   354   {

   355   public:

   356     typedef E Expr;

   357     typedef typename E::Var Var;

   358     typedef typename E::Coeff Coeff;

   360     static const Coeff INF;

   361     static const Coeff NaN;

   362 //     static const Coeff INF=0;

   363 //     static const Coeff NaN=1;

   365     Expr expr;

   366     Coeff lb,ub;

   368     LinConstr() : expr(), lb(NaN), ub(NaN) {}

   369     LinConstr(Coeff _lb,const Expr &e,Coeff _ub) :

   370       expr(e), lb(_lb), ub(_ub) {}

   371     LinConstr(const Expr &e,Coeff _ub) :

   372       expr(e), lb(NaN), ub(_ub) {}

   373     LinConstr(Coeff _lb,const Expr &e) :

   374       expr(e), lb(_lb), ub(NaN) {}

   375   };

   377   template<class E>

   378   const typename LinConstr<E>::Coeff LinConstr<E>::INF=

   379     std::numeric_limits<Coeff>::infinity();

   380   template<class E>

   381   const typename LinConstr<E>::Coeff LinConstr<E>::NaN=

   382     std::numeric_limits<Coeff>::quiet_NaN();

   385   template<class E>

   386   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   387   operator<=(const E &e,const E &f)

   388   {

   389     return LinConstr<E>(-LinConstr<E>::INF,e-f,0);

   390   }

   392   template<class E>

   393   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   394   operator>=(const E &e,const E &f)

   395   {

   396     return LinConstr<E>(-LinConstr<E>::INF,f-e,0);

   397   }

   399   template<class E>

   400   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   401   operator==(const E &e,const E &f)

   402   {

   403     return LinConstr<E>(0,e-f,0);

   404   }

   406   //////////////////////////////

   408   template<class E>

   409   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   410   operator<=(const E &e,const typename E::Coeff &n)

   411   {

   412     return LinConstr<E>(e,n);

   413   }

   415   template<class E>

   416   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   417   operator>=(const E &e,const typename E::Coeff &n)

   418   {

   419     return LinConstr<E>(n,e);

   420   }

   422   template<class E>

   423   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   424   operator==(const E &e,const typename E::Coeff &n)

   425   {

   426     return LinConstr<E>(n,e,n);

   427   }

   429   //////////////////////////////

   431   template<class E>

   432   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   433   operator<=(const typename E::Coeff &n,const E &e)

   434   {

   435     return LinConstr<E>(n,e);

   436   }

   438   template<class E>

   439   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   440   operator>=(const typename E::Coeff &n,const E &e)

   441   {

   442     return LinConstr<E>(e,n);

   443   }

   445   template<class E>

   446   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   447   operator==(const typename E::Coeff &n,const E &e)

   448   {

   449     return LinConstr<E>(n,e,n);

   450   }

   452   //////////////////////////////

   454   template<class E>

   455   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   456   operator<=(const typename E::Coeff &n,const LinConstr<E> &c)

   457   {

   458     LinConstr<E> tmp(c);

   459     if(tmp.lb!=tmp.NaN) throw LogicError();

   460     else tmp.lb=n;

   461     return tmp;

   462   }

   464   template<class E>

   465   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   466   operator>=(const typename E::Coeff &n,const LinConstr<E> &c)

   467   {

   468     LinConstr<E> tmp(c);

   469     if(tmp.ub!=tmp.NaN) throw LogicError();

   470     else tmp.ub=n;

   471     return tmp;

   472   }

   474   template<class E>

   475   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   476   operator<=(const LinConstr<E> &c,const typename E::Coeff &n)

   477   {

   478     LinConstr<E> tmp(c);

   479     if(tmp.ub!=tmp.NaN) throw LogicError();

   480     else tmp.ub=n;

   481     return tmp;

   482   }

   484   template<class E>

   485   typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

   486   operator>=(const LinConstr<E> &c,const typename E::Coeff &n)

   487   {

   488     LinConstr<E> tmp(c);

   489     if(tmp.lb!=tmp.NaN) throw LogicError();

   490     else tmp.lb=n;

   491     return tmp;

   492   }

   496 } //namespace lemon

   498 #endif //LEMON_LIN_EXPR_H

author	alpar
	Fri, 01 Apr 2005 19:50:29 +0000
changeset 1293	8ede2a6b2594
parent 1259	11a09f1319b3
permissions	-rw-r--r--