COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1259:11a09f1319b3 in lemon-0.x for src/work


Ignore:
Timestamp:
03/25/05 13:58:52 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1686
Message:
  • Largely extended linear expressions
  • Better docs
Location:
src/work/athos/lp
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • src/work/athos/lp/lin_expr.h

    r1253 r1259  
    2828 
    2929  /// Class to handle sparse linear expressions
    30   template <class _V,class _C>
    31   class SparseLinExpr : public std::map<_V, _C>
     30  template <class _V>
     31  class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
    3232  {
    3333  public:
    3434    typedef _V Var;
    35     typedef _C Coeff;
     35    typedef typename _V::ExprValue Coeff;
    3636   
    3737  protected:
    38     typedef typename std::map<_V, _C> Base;
     38    typedef typename std::map<_V, typename _V::ExprValue> Base;
    3939
    4040    Coeff const_comp;
    4141  public:
    42     SparseLinExpr() { }
    43     SparseLinExpr(const Var &v) : const_comp(v) {
     42    ///\e
     43    SparseLinExpr() : Base(), const_comp(0) { }
     44    ///\e
     45    SparseLinExpr(const Var &v) : const_comp(0) {
    4446      Base::insert(std::make_pair(v, 1));
    4547    }
     48    ///\e
    4649    SparseLinExpr(const Coeff &v) : const_comp(v) {}
    4750   
     51    ///\e
    4852    void set(const Var &v,const Coeff &c) {
    4953      return Base::insert(std::make_pair(v, c));
    … …  
    5256//     const Coeff &operator[](const Var &v) const { return data[v]; }
    5357
     58    ///\e
    5459    Coeff &constComp() { return const_comp; }
     60    ///\e
    5561    const Coeff &constComp() const { return const_comp; }
    5662
    … …  
    6571    }
    6672   
     73    ///\e
     74    SparseLinExpr &operator+=(const SparseLinExpr &e) {
     75      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     76        (*this)[j->first]+=j->second;
     77      ///\todo it might be speeded up using "hints"
     78      const_comp+=e.const_comp;
     79      return *this;
     80    }
     81    ///\e
     82    SparseLinExpr &operator-=(const SparseLinExpr &e) {
     83      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     84        (*this)[j->first]-=j->second;
     85      const_comp-=e.const_comp;
     86      return *this;
     87    }
     88    ///\e
     89    SparseLinExpr &operator*=(const Coeff &c) {
     90      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     91        j->second*=c;
     92      const_comp*=c;
     93      return *this;
     94    }
     95    ///\e
     96    SparseLinExpr &operator/=(const Coeff &c) {
     97      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     98        j->second/=c;
     99      const_comp/=c;
     100      return *this;
     101    }
     102   
    67103  };
    68104
     105  ///\e
     106 
     107  ///\relates SparseLinExpr
     108  ///
     109  template <class V>
     110  SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,
     111                                const SparseLinExpr<V> &b) {
     112    SparseLinExpr<V> tmp(a);
     113    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
     114    return tmp;
     115  }
     116 
     117  ///\e
     118 
     119  ///\relates SparseLinExpr
     120  ///
     121  template <class V>
     122  SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,
     123                                const SparseLinExpr<V> &b) {
     124    SparseLinExpr<V> tmp(a);
     125    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
     126    return tmp;
     127  }
     128 
     129  ///\e
     130 
     131  ///\relates SparseLinExpr
     132  ///
     133  template <class V>
     134  SparseLinExpr<V> operator*(const typename V::ExprValue &c,
     135                               const SparseLinExpr<V> &e) {
     136    SparseLinExpr<V> tmp(e);
     137    tmp*=c;
     138    return tmp;
     139  }
     140 
     141  ///\e
     142 
     143  ///\relates SparseLinExpr
     144  ///
     145  template <class V>
     146  SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
     147                               const typename V::ExprValue &c) {
     148    SparseLinExpr<V> tmp(e);
     149    tmp*=c;
     150    return tmp;
     151  }
     152 
     153 
     154  ///\e
     155 
     156  ///\relates SparseLinExpr
     157  ///
     158  template <class V>
     159  SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,
     160                               const typename V::ExprValue &c) {
     161    SparseLinExpr<V> tmp(e);
     162    tmp/=c;
     163    return tmp;
     164  }
     165 
     166  ///\e
     167 
     168  ///\relates SparseLinExpr
     169  ///
     170  template <class V>
     171  SparseLinExpr<V> operator+(const typename V::ExprValue &c,
     172                             const SparseLinExpr<V> &e) {
     173    SparseLinExpr<V> tmp(e);
     174    tmp.constComp()+=c;
     175    return tmp;
     176  }
     177
     178  ///\e
     179 
     180  ///\relates SparseLinExpr
     181  ///
     182  template <class V>
     183  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
     184                             const typename V::ExprValue &c) {
     185    SparseLinExpr<V> tmp(e);
     186    tmp.constComp()+=c;
     187    return tmp;
     188  }
     189
     190  ///\e
     191 
     192  ///\relates SparseLinExpr
     193  ///
     194  template <class V>
     195  SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
     196    SparseLinExpr<V> tmp(e);
     197    tmp[v]+=1;
     198    return tmp;
     199  }
     200
     201  ///\e
     202 
     203  ///\relates SparseLinExpr
     204  ///
     205  template <class V>
     206  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {
     207    SparseLinExpr<V> tmp(e);
     208    tmp[v]+=1;
     209    return tmp;
     210  }
     211
     212  ///\e
     213 
     214  ///\relates SparseLinExpr
     215  ///
     216  template <class V>
     217  SparseLinExpr<V> operator-(const typename V::ExprValue &c,
     218                             const SparseLinExpr<V> &e) {
     219    SparseLinExpr<V> tmp(e);
     220    tmp*=-1;
     221    tmp.constComp()+=c;
     222    return tmp;
     223  }
     224
     225  ///\e
     226 
     227  ///\relates SparseLinExpr
     228  ///
     229  template <class V>
     230  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,
     231                             const typename V::ExprValue &c) {
     232    SparseLinExpr<V> tmp(e);
     233    tmp.constComp()-=c;
     234    return tmp;
     235  }
     236
     237  ///\e
     238 
     239  ///\relates SparseLinExpr
     240  ///
     241  template <class V>
     242  SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
     243    SparseLinExpr<V> tmp(e);
     244    tmp*=-1;
     245    tmp[v]+=1;
     246    return tmp;
     247  }
     248
     249  ///\e
     250 
     251  ///\relates SparseLinExpr
     252  ///
     253  template <class V>
     254  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
     255    SparseLinExpr<V> tmp(e);
     256    tmp[v]-=1;
     257    return tmp;
     258  }
     259
     260  ///\e
     261 
     262  ///\relates SparseLinExpr
     263  ///
     264  template <class V>
     265  SparseLinExpr<V> operator+(const V &v1,const V &v2) {
     266    SparseLinExpr<V> tmp(v1);
     267    tmp[v2]+=1;
     268    return tmp;
     269  }
     270
     271  ///\e
     272 
     273  ///\relates SparseLinExpr
     274  ///
     275  template <class V>
     276  SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
     277    SparseLinExpr<V> tmp;
     278    tmp[v]=c;
     279    return tmp;
     280  }
     281
     282  ///\e
     283 
     284  ///\relates SparseLinExpr
     285  ///
     286  template <class V>
     287  SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
     288    SparseLinExpr<V> tmp;
     289    tmp[v]=c;
     290    return tmp;
     291  }
     292
     293  ///\e
     294 
     295  ///\relates SparseLinExpr
     296  ///
     297  template <class V>
     298  SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
     299    SparseLinExpr<V> tmp;
     300    tmp[v]=1/c;
     301    return tmp;
     302  }
     303
     304
    69305} //namespace lemon
    70306

  • src/work/athos/lp/lp_base.h

    r1258 r1259  
    121121      friend class LpSolverBase;
    122122    public:
     123      typedef Value ExprValue;
    123124      typedef True LpSolverCol;
    124125      Col() {}
    … …  
    143144      friend class LpSolverBase;
    144145    public:
     146      typedef Value ExprValue;
    145147      typedef True LpSolverRow;
    146148      Row() {}
    … …  
    151153      bool operator!=(Row c) const  {return id==c.id;}
    152154   };
    153 
    154     typedef SparseLinExpr<Col, Value> Expr;
     155   
     156    ///Linear expression
     157    typedef SparseLinExpr<Col> Expr;
    155158
    156159  protected:
    … …  
    185188    /// The lower bound of a variable (column) have to be given by an
    186189    /// extended number of type Value, i.e. a finite number of type
    187     /// Value or -INF.
     190    /// Value or -\ref INF.
    188191    virtual void _setColLowerBound(int i, Value value) = 0;
    189192    /// \e
    … …  
    191194    /// The upper bound of a variable (column) have to be given by an
    192195    /// extended number of type Value, i.e. a finite number of type
    193     /// Value or INF.
     196    /// Value or \ref INF.
    194197    virtual void _setColUpperBound(int i, Value value) = 0;
    195198    /// \e
    … …  
    197200    /// The lower bound of a linear expression (row) have to be given by an
    198201    /// extended number of type Value, i.e. a finite number of type
    199     /// Value or -INF.
     202    /// Value or -\ref INF.
    200203    virtual void _setRowLowerBound(int i, Value value) = 0;
    201204    /// \e
    … …  
    203206    /// The upper bound of a linear expression (row) have to be given by an
    204207    /// extended number of type Value, i.e. a finite number of type
    205     /// Value or INF.
     208    /// Value or \ref INF.
    206209    virtual void _setRowUpperBound(int i, Value value) = 0;
    207210
    … …  
    268271
    269272    ///\param r is the row to be modified
    270     ///\param l is lower bound (-INF means no bound)
     273    ///\param l is lower bound (-\ref INF means no bound)
    271274    ///\param e is a linear expression (see \ref Expr)
    272     ///\param u is the upper bound (INF means no bound)
     275    ///\param u is the upper bound (\ref INF means no bound)
    273276    ///\bug This is a temportary function. The interface will change to
    274277    ///a better one.
    … …  
    291294    ///Add a new row (i.e a new constaint) to the LP
    292295
    293     ///\param l is the lower bound (-INF means no bound)
     296    ///\param l is the lower bound (-\ref INF means no bound)
    294297    ///\param e is a linear expression (see \ref Expr)
    295     ///\param u is the upper bound (INF means no bound)
     298    ///\param u is the upper bound (\ref INF means no bound)
    296299    ///\return The created row.
    297300    ///\bug This is a temportary function. The interface will change to
    … …  
    307310    /// The upper bound of a variable (column) have to be given by an
    308311    /// extended number of type Value, i.e. a finite number of type
    309     /// Value or -INF.
     312    /// Value or -\ref INF.
    310313    virtual void setColLowerBound(Col c, Value value) {
    311314      _setColLowerBound(cols.floatingId(c.id),value);
    … …  
    315318    /// The upper bound of a variable (column) have to be given by an
    316319    /// extended number of type Value, i.e. a finite number of type
    317     /// Value or INF.
     320    /// Value or \ref INF.
    318321    virtual void setColUpperBound(Col c, Value value) {
    319322      _setColUpperBound(cols.floatingId(c.id),value);
    … …  
    323326    /// The lower bound of a linear expression (row) have to be given by an
    324327    /// extended number of type Value, i.e. a finite number of type
    325     /// Value or -INF.
     328    /// Value or -\ref INF.
    326329    virtual void setRowLowerBound(Row r, Value value) {
    327330      _setRowLowerBound(rows.floatingId(r.id),value);
    … …  
    331334    /// The upper bound of a linear expression (row) have to be given by an
    332335    /// extended number of type Value, i.e. a finite number of type
    333     /// Value or INF.
     336    /// Value or \ref INF.
    334337    virtual void setRowUpperBound(Row r, Value value) {
    335338      _setRowUpperBound(rows.floatingId(r.id),value);

  • src/work/athos/lp/lp_test.cc

    r1256 r1259  
    2929  e[x[3]]=1;
    3030  e.constComp()=12;
     31
     32  LP::Col p1,p2,p3,p4,p5;
     33 
    3134  lp.addRow(LP::INF,e,23);
    32 
     35  lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
     36  lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
     37  lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
     38  lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
    3339}
Note: See TracChangeset for help on using the changeset viewer.