Changeset 1272:17be4c5bc6c6 in lemon-0.x for src/work/athos/lp

Timestamp:

03/30/05 10:28:44 (20 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:

• lp_base.cc (modified) (1 diff)
• lp_base.h (modified) (7 diffs)
• lp_test.cc (modified) (3 diffs)

src/work/athos/lp/lp_base.cc

@@ -26 +26 @@
   LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
 
-
+  const LpSolverBase::Constr::Coeff
+  LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
+  const LpSolverBase::Constr::Coeff
+  LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
+  
 } //namespace lemon

src/work/athos/lp/lp_base.h

@@ -19 +19 @@
 
 #include<vector>
+#include<map>
 #include<limits>
 
@@ -25 +26 @@
 #include<lemon/invalid.h>
 
-#include"lin_expr.h"
+//#include"lin_expr.h"
+
 ///\file
 ///\brief The interface of the LP solver interface.
@@ -169 +171 @@
     
     ///Linear expression
-    typedef SparseLinExpr<Col> Expr;
+    //    typedef SparseLinExpr<Col> Expr;
+    class Expr : public std::map<Col,Col::ExprValue>
+    {
+    public:
+      typedef Col Var; 
+      typedef Col::ExprValue Coeff;
+      
+    protected:
+      typedef std::map<Col,Col::ExprValue> Base;
+      
+      Coeff const_comp;
+  public:
+      typedef True IsLinExpression;
+      ///\e
+      Expr() : Base(), const_comp(0) { }
+      ///\e
+      Expr(const Var &v) : const_comp(0) {
+        Base::insert(std::make_pair(v, 1));
+      }
+      ///\e
+      Expr(const Coeff &v) : const_comp(v) {}
+      ///\e
+      void set(const Var &v,const Coeff &c) {
+        Base::insert(std::make_pair(v, c));
+      }
+      ///\e
+      Coeff &constComp() { return const_comp; }
+      ///\e
+      const Coeff &constComp() const { return const_comp; }
+      
+      ///Removes the components with zero coefficient.
+      void simplify() {
+        for (Base::iterator i=Base::begin(); i!=Base::end();) {
+          Base::iterator j=i;
+          ++j;
+          if ((*i).second==0) Base::erase(i);
+          j=i;
+        }
+      }
+      
+      ///\e
+      Expr &operator+=(const Expr &e) {
+        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
+          (*this)[j->first]+=j->second;
+        ///\todo it might be speeded up using "hints"
+        const_comp+=e.const_comp;
+        return *this;
+      }
+      ///\e
+      Expr &operator-=(const Expr &e) {
+        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
+          (*this)[j->first]-=j->second;
+        const_comp-=e.const_comp;
+        return *this;
+      }
+      ///\e
+      Expr &operator*=(const Coeff &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second*=c;
+        const_comp*=c;
+        return *this;
+      }
+      ///\e
+      Expr &operator/=(const Coeff &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second/=c;
+        const_comp/=c;
+        return *this;
+      }
+    };
+    
     ///Linear constraint
-    typedef LinConstr<Expr> Constr;
+    //typedef LinConstr<Expr> Constr;
+    class Constr
+    {
+    public:
+      typedef LpSolverBase::Expr Expr;
+      typedef Expr::Var Var;
+      typedef Expr::Coeff Coeff;
+      
+      static const Coeff INF;
+      static const Coeff NaN;
+      //     static const Coeff INF=0;
+      //     static const Coeff NaN=1;
+      
+      Expr expr;
+      Coeff lb,ub;
+      
+      Constr() : expr(), lb(NaN), ub(NaN) {}
+      Constr(Coeff _lb,const Expr &e,Coeff _ub) :
+        expr(e), lb(_lb), ub(_ub) {}
+      Constr(const Expr &e,Coeff _ub) : 
+        expr(e), lb(NaN), ub(_ub) {}
+      Constr(Coeff _lb,const Expr &e) :
+        expr(e), lb(_lb), ub(NaN) {}
+      Constr(const Expr &e) : 
+        expr(e), lb(NaN), ub(NaN) {}
+    };
+    
 
   protected:
@@ -291 +389 @@
       return s;
     }
+    template<class T>
+    typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
+                       int>::type
+    addColSet(T &t,dummy<2> = 2) { 
+      ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
+      int s=0;
+      for(typename T::ValueSet::iterator i=t.valueSet().begin();
+          i!=t.valueSet().end();
+          ++i)
+        {
+          *i=addCol();
+          s++;
+        }
+      return s;
+    }
 #endif
 
@@ -327 +440 @@
     ///\param r is the row to be modified
     ///\param c is a linear expression (see \ref Constr)
-    ///\bug This is a temportary function. The interface will change to
-    ///a better one.
     void setRow(Row r, const Constr &c) {
       Value lb= c.lb==NaN?-INF:lb;
@@ -353 +464 @@
     ///\param c is a linear expression (see \ref Constr)
     ///\return The created row.
-    ///\bug This is a temportary function. The interface will change to
-    ///a better one.
     Row addRow(const Constr &c) {
       Row r=addRow();
@@ -428 +537 @@
   };  
 
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr::Coeff &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
+                                      const LpSolverBase::Expr &b) 
+  {
+    LpSolverBase::Expr tmp(b);
+    tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Expr
+  ///
+  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
+                                      const LpSolverBase::Expr::Coeff &b) 
+  {
+    LpSolverBase::Expr tmp(a);
+    tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(e,f);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr::Coeff &f) 
+  {
+    return LpSolverBase::Constr(e,f);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
+  }
+
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(f,e);
+  }
+
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr::Coeff &f) 
+  {
+    return LpSolverBase::Constr(f,e);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
+                                         const LpSolverBase::Expr &f) 
+  {
+    return LpSolverBase::Constr(0,e-f,0);
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
+                                         const LpSolverBase::Constr&c) 
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.lb!=tmp.NaN) throw LogicError();
+    else tmp.lb=n;
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
+                                         const LpSolverBase::Constr::Coeff &n)
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.ub!=tmp.NaN) throw LogicError();
+    else tmp.ub=n;
+    return tmp;
+  }
+
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
+                                         const LpSolverBase::Constr&c) 
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.ub!=tmp.NaN) throw LogicError();
+    else tmp.ub=n;
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::Constr
+  ///
+  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
+                                         const LpSolverBase::Constr::Coeff &n)
+  {
+    LpSolverBase::Constr tmp(c);
+    if(tmp.lb!=tmp.NaN) throw LogicError();
+    else tmp.lb=n;
+    return tmp;
+  }
+
+
 } //namespace lemon
 

src/work/athos/lp/lp_test.cc

@@ -25 +25 @@
 
 
-  LP::Expr e;
+  LP::Expr e,f,g;
+  LP::Col p1,p2,p3,p4,p5;
+  LP::Constr c;
+  
+  e[p1]=2;
+  e.constComp()=12;
+  e[p1]+=2;
+  e.constComp()+=12;
+  e[p1]-=2;
+  e.constComp()-=12;
+  
+  e=2;
+  e=2.2;
+  e=p1;
+  e=f;
+
+  e+=2;
+  e+=2.2;
+  e+=p1;
+  e+=f;
+
+  e-=2;
+  e-=2.2;
+  e-=p1;
+  e-=f;
+
+  e*=2;
+  e*=2.2;
+  e/=2;
+  e/=2.2;
+
+  e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
+      (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
+      (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
+      2.2*f+f*2.2+f/2.2+
+      2*f+f*2+f/2+
+      2.2*p1+p1*2.2+p1/2.2+
+      2*p1+p1*2+p1/2
+     );
+  
+
+  c = (e  <= f  );
+  c = (e  <= 2.2);
+  c = (e  <= 2  );
+  c = (e  <= p1 );
+  c = (2.2<= f  );
+  c = (2  <= f  );
+  c = (p1 <= f  );
+  c = (p1 <= p2 );
+  c = (p1 <= 2.2);
+  c = (p1 <= 2  );
+  c = (2.2<= p2 );
+  c = (2  <= p2 );
+
+  c = (e  >= f  );
+  c = (e  >= 2.2);
+  c = (e  >= 2  );
+  c = (e  >= p1 );
+  c = (2.2>= f  );
+  c = (2  >= f  );
+  c = (p1 >= f  );
+  c = (p1 >= p2 );
+  c = (p1 >= 2.2);
+  c = (p1 >= 2  );
+  c = (2.2>= p2 );
+  c = (2  >= p2 );
+
+  c = (e  == f  );
+  c = (e  == 2.2);
+  c = (e  == 2  );
+  c = (e  == p1 );
+  c = (2.2== f  );
+  c = (2  == f  );
+  c = (p1 == f  );
+  //c = (p1 == p2 );
+  c = (p1 == 2.2);
+  c = (p1 == 2  );
+  c = (2.2== p2 );
+  c = (2  == p2 );
+
+  c = (2 <= e <= 3);
+  c = (2 <= p1<= 3);
+
+  c = (2 >= e >= 3);
+  c = (2 >= p1>= 3);
+
   e[x[3]]=2;
   e[x[3]]=4;
   e[x[3]]=1;
   e.constComp()=12;
-
-  LP::Col p1,p2,p3,p4,p5;
   
   lp.addRow(LP::INF,e,23);
@@ -41 +124 @@
   lp.addRow(x[1]+x[3]<=x[5]-3);
   lp.addRow(-7<=x[1]+x[3]-12<=3);
+  //lp.addRow(x[1]<=x[5]);
+
 }
 
@@ -58 +143 @@
   
   typename G::EdgeMap<LpGlpk::Col> x(g);
-  // lp.addColSet(x);
-  for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
+  lp.addColSet(x);
+   //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
   
   for(EdgeIt e(g);e!=INVALID;++e) {