COIN-OR::LEMON - Graph Library

Changeset 1272:17be4c5bc6c6 in lemon-0.x


Ignore:
Timestamp:
03/30/05 10:28:44 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1702
Message:
  • Non-template expressions and constraints (lin_expr.h isn't used)
Location:
src/work/athos/lp
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/lp/lp_base.cc

    r1264 r1272  
    2626  LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
    2727
    28 
     28  const LpSolverBase::Constr::Coeff
     29  LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
     30  const LpSolverBase::Constr::Coeff
     31  LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
     32 
    2933} //namespace lemon
  • src/work/athos/lp/lp_base.h

    r1264 r1272  
    1919
    2020#include<vector>
     21#include<map>
    2122#include<limits>
    2223
     
    2526#include<lemon/invalid.h>
    2627
    27 #include"lin_expr.h"
     28//#include"lin_expr.h"
     29
    2830///\file
    2931///\brief The interface of the LP solver interface.
     
    169171   
    170172    ///Linear expression
    171     typedef SparseLinExpr<Col> Expr;
     173    //    typedef SparseLinExpr<Col> Expr;
     174    class Expr : public std::map<Col,Col::ExprValue>
     175    {
     176    public:
     177      typedef Col Var;
     178      typedef Col::ExprValue Coeff;
     179     
     180    protected:
     181      typedef std::map<Col,Col::ExprValue> Base;
     182     
     183      Coeff const_comp;
     184  public:
     185      typedef True IsLinExpression;
     186      ///\e
     187      Expr() : Base(), const_comp(0) { }
     188      ///\e
     189      Expr(const Var &v) : const_comp(0) {
     190        Base::insert(std::make_pair(v, 1));
     191      }
     192      ///\e
     193      Expr(const Coeff &v) : const_comp(v) {}
     194      ///\e
     195      void set(const Var &v,const Coeff &c) {
     196        Base::insert(std::make_pair(v, c));
     197      }
     198      ///\e
     199      Coeff &constComp() { return const_comp; }
     200      ///\e
     201      const Coeff &constComp() const { return const_comp; }
     202     
     203      ///Removes the components with zero coefficient.
     204      void simplify() {
     205        for (Base::iterator i=Base::begin(); i!=Base::end();) {
     206          Base::iterator j=i;
     207          ++j;
     208          if ((*i).second==0) Base::erase(i);
     209          j=i;
     210        }
     211      }
     212     
     213      ///\e
     214      Expr &operator+=(const Expr &e) {
     215        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     216          (*this)[j->first]+=j->second;
     217        ///\todo it might be speeded up using "hints"
     218        const_comp+=e.const_comp;
     219        return *this;
     220      }
     221      ///\e
     222      Expr &operator-=(const Expr &e) {
     223        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     224          (*this)[j->first]-=j->second;
     225        const_comp-=e.const_comp;
     226        return *this;
     227      }
     228      ///\e
     229      Expr &operator*=(const Coeff &c) {
     230        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     231          j->second*=c;
     232        const_comp*=c;
     233        return *this;
     234      }
     235      ///\e
     236      Expr &operator/=(const Coeff &c) {
     237        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     238          j->second/=c;
     239        const_comp/=c;
     240        return *this;
     241      }
     242    };
     243   
    172244    ///Linear constraint
    173     typedef LinConstr<Expr> Constr;
     245    //typedef LinConstr<Expr> Constr;
     246    class Constr
     247    {
     248    public:
     249      typedef LpSolverBase::Expr Expr;
     250      typedef Expr::Var Var;
     251      typedef Expr::Coeff Coeff;
     252     
     253      static const Coeff INF;
     254      static const Coeff NaN;
     255      //     static const Coeff INF=0;
     256      //     static const Coeff NaN=1;
     257     
     258      Expr expr;
     259      Coeff lb,ub;
     260     
     261      Constr() : expr(), lb(NaN), ub(NaN) {}
     262      Constr(Coeff _lb,const Expr &e,Coeff _ub) :
     263        expr(e), lb(_lb), ub(_ub) {}
     264      Constr(const Expr &e,Coeff _ub) :
     265        expr(e), lb(NaN), ub(_ub) {}
     266      Constr(Coeff _lb,const Expr &e) :
     267        expr(e), lb(_lb), ub(NaN) {}
     268      Constr(const Expr &e) :
     269        expr(e), lb(NaN), ub(NaN) {}
     270    };
     271   
    174272
    175273  protected:
     
    291389      return s;
    292390    }
     391    template<class T>
     392    typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
     393                       int>::type
     394    addColSet(T &t,dummy<2> = 2) {
     395      ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
     396      int s=0;
     397      for(typename T::ValueSet::iterator i=t.valueSet().begin();
     398          i!=t.valueSet().end();
     399          ++i)
     400        {
     401          *i=addCol();
     402          s++;
     403        }
     404      return s;
     405    }
    293406#endif
    294407
     
    327440    ///\param r is the row to be modified
    328441    ///\param c is a linear expression (see \ref Constr)
    329     ///\bug This is a temportary function. The interface will change to
    330     ///a better one.
    331442    void setRow(Row r, const Constr &c) {
    332443      Value lb= c.lb==NaN?-INF:lb;
     
    353464    ///\param c is a linear expression (see \ref Constr)
    354465    ///\return The created row.
    355     ///\bug This is a temportary function. The interface will change to
    356     ///a better one.
    357466    Row addRow(const Constr &c) {
    358467      Row r=addRow();
     
    428537  }; 
    429538
     539  ///\e
     540 
     541  ///\relates LpSolverBase::Expr
     542  ///
     543  inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
     544                                      const LpSolverBase::Expr &b)
     545  {
     546    LpSolverBase::Expr tmp(a);
     547    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
     548    return tmp;
     549  }
     550  ///\e
     551 
     552  ///\relates LpSolverBase::Expr
     553  ///
     554  inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
     555                                      const LpSolverBase::Expr &b)
     556  {
     557    LpSolverBase::Expr tmp(a);
     558    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
     559    return tmp;
     560  }
     561  ///\e
     562 
     563  ///\relates LpSolverBase::Expr
     564  ///
     565  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
     566                                      const LpSolverBase::Expr::Coeff &b)
     567  {
     568    LpSolverBase::Expr tmp(a);
     569    tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
     570    return tmp;
     571  }
     572 
     573  ///\e
     574 
     575  ///\relates LpSolverBase::Expr
     576  ///
     577  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
     578                                      const LpSolverBase::Expr &b)
     579  {
     580    LpSolverBase::Expr tmp(b);
     581    tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
     582    return tmp;
     583  }
     584  ///\e
     585 
     586  ///\relates LpSolverBase::Expr
     587  ///
     588  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
     589                                      const LpSolverBase::Expr::Coeff &b)
     590  {
     591    LpSolverBase::Expr tmp(a);
     592    tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
     593    return tmp;
     594  }
     595 
     596  ///\e
     597 
     598  ///\relates LpSolverBase::Constr
     599  ///
     600  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
     601                                         const LpSolverBase::Expr &f)
     602  {
     603    return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
     604  }
     605
     606  ///\e
     607 
     608  ///\relates LpSolverBase::Constr
     609  ///
     610  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
     611                                         const LpSolverBase::Expr &f)
     612  {
     613    return LpSolverBase::Constr(e,f);
     614  }
     615
     616  ///\e
     617 
     618  ///\relates LpSolverBase::Constr
     619  ///
     620  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
     621                                         const LpSolverBase::Expr::Coeff &f)
     622  {
     623    return LpSolverBase::Constr(e,f);
     624  }
     625
     626  ///\e
     627 
     628  ///\relates LpSolverBase::Constr
     629  ///
     630  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
     631                                         const LpSolverBase::Expr &f)
     632  {
     633    return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
     634  }
     635
     636
     637  ///\e
     638 
     639  ///\relates LpSolverBase::Constr
     640  ///
     641  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
     642                                         const LpSolverBase::Expr &f)
     643  {
     644    return LpSolverBase::Constr(f,e);
     645  }
     646
     647
     648  ///\e
     649 
     650  ///\relates LpSolverBase::Constr
     651  ///
     652  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
     653                                         const LpSolverBase::Expr::Coeff &f)
     654  {
     655    return LpSolverBase::Constr(f,e);
     656  }
     657
     658  ///\e
     659 
     660  ///\relates LpSolverBase::Constr
     661  ///
     662  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
     663                                         const LpSolverBase::Expr &f)
     664  {
     665    return LpSolverBase::Constr(0,e-f,0);
     666  }
     667
     668  ///\e
     669 
     670  ///\relates LpSolverBase::Constr
     671  ///
     672  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
     673                                         const LpSolverBase::Constr&c)
     674  {
     675    LpSolverBase::Constr tmp(c);
     676    if(tmp.lb!=tmp.NaN) throw LogicError();
     677    else tmp.lb=n;
     678    return tmp;
     679  }
     680  ///\e
     681 
     682  ///\relates LpSolverBase::Constr
     683  ///
     684  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
     685                                         const LpSolverBase::Constr::Coeff &n)
     686  {
     687    LpSolverBase::Constr tmp(c);
     688    if(tmp.ub!=tmp.NaN) throw LogicError();
     689    else tmp.ub=n;
     690    return tmp;
     691  }
     692
     693  ///\e
     694 
     695  ///\relates LpSolverBase::Constr
     696  ///
     697  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
     698                                         const LpSolverBase::Constr&c)
     699  {
     700    LpSolverBase::Constr tmp(c);
     701    if(tmp.ub!=tmp.NaN) throw LogicError();
     702    else tmp.ub=n;
     703    return tmp;
     704  }
     705  ///\e
     706 
     707  ///\relates LpSolverBase::Constr
     708  ///
     709  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
     710                                         const LpSolverBase::Constr::Coeff &n)
     711  {
     712    LpSolverBase::Constr tmp(c);
     713    if(tmp.lb!=tmp.NaN) throw LogicError();
     714    else tmp.lb=n;
     715    return tmp;
     716  }
     717
     718
    430719} //namespace lemon
    431720
  • src/work/athos/lp/lp_test.cc

    r1264 r1272  
    2525
    2626
    27   LP::Expr e;
     27  LP::Expr e,f,g;
     28  LP::Col p1,p2,p3,p4,p5;
     29  LP::Constr c;
     30 
     31  e[p1]=2;
     32  e.constComp()=12;
     33  e[p1]+=2;
     34  e.constComp()+=12;
     35  e[p1]-=2;
     36  e.constComp()-=12;
     37 
     38  e=2;
     39  e=2.2;
     40  e=p1;
     41  e=f;
     42
     43  e+=2;
     44  e+=2.2;
     45  e+=p1;
     46  e+=f;
     47
     48  e-=2;
     49  e-=2.2;
     50  e-=p1;
     51  e-=f;
     52
     53  e*=2;
     54  e*=2.2;
     55  e/=2;
     56  e/=2.2;
     57
     58  e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
     59      (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
     60      (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
     61      2.2*f+f*2.2+f/2.2+
     62      2*f+f*2+f/2+
     63      2.2*p1+p1*2.2+p1/2.2+
     64      2*p1+p1*2+p1/2
     65     );
     66 
     67
     68  c = (e  <= f  );
     69  c = (e  <= 2.2);
     70  c = (e  <= 2  );
     71  c = (e  <= p1 );
     72  c = (2.2<= f  );
     73  c = (2  <= f  );
     74  c = (p1 <= f  );
     75  c = (p1 <= p2 );
     76  c = (p1 <= 2.2);
     77  c = (p1 <= 2  );
     78  c = (2.2<= p2 );
     79  c = (2  <= p2 );
     80
     81  c = (e  >= f  );
     82  c = (e  >= 2.2);
     83  c = (e  >= 2  );
     84  c = (e  >= p1 );
     85  c = (2.2>= f  );
     86  c = (2  >= f  );
     87  c = (p1 >= f  );
     88  c = (p1 >= p2 );
     89  c = (p1 >= 2.2);
     90  c = (p1 >= 2  );
     91  c = (2.2>= p2 );
     92  c = (2  >= p2 );
     93
     94  c = (e  == f  );
     95  c = (e  == 2.2);
     96  c = (e  == 2  );
     97  c = (e  == p1 );
     98  c = (2.2== f  );
     99  c = (2  == f  );
     100  c = (p1 == f  );
     101  //c = (p1 == p2 );
     102  c = (p1 == 2.2);
     103  c = (p1 == 2  );
     104  c = (2.2== p2 );
     105  c = (2  == p2 );
     106
     107  c = (2 <= e <= 3);
     108  c = (2 <= p1<= 3);
     109
     110  c = (2 >= e >= 3);
     111  c = (2 >= p1>= 3);
     112
    28113  e[x[3]]=2;
    29114  e[x[3]]=4;
    30115  e[x[3]]=1;
    31116  e.constComp()=12;
    32 
    33   LP::Col p1,p2,p3,p4,p5;
    34117 
    35118  lp.addRow(LP::INF,e,23);
     
    41124  lp.addRow(x[1]+x[3]<=x[5]-3);
    42125  lp.addRow(-7<=x[1]+x[3]-12<=3);
     126  //lp.addRow(x[1]<=x[5]);
     127
    43128}
    44129
     
    58143 
    59144  typename G::EdgeMap<LpGlpk::Col> x(g);
    60   // lp.addColSet(x);
    61   for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
     145  lp.addColSet(x);
     146   //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
    62147 
    63148  for(EdgeIt e(g);e!=INVALID;++e) {
Note: See TracChangeset for help on using the changeset viewer.