Changeset 1445:4635352e5524 in lemon-0.x

Timestamp:

06/04/05 14:50:15 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1925

Message:

DualExpr? added.

Files:

• lemon/lp_base.h (modified) (6 diffs)
• test/lp_test.cc (modified) (1 diff)

lemon/lp_base.h

@@ -411 +411 @@
     };
     
+    ///Linear expression of rows
+    
+    ///This data structure represents a column of the matrix,
+    ///thas is it strores a linear expression of the dual variables
+    ///(\ref Row "Row"s).
+    ///
+    ///There are several ways to access and modify the contents of this
+    ///container.
+    ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
+    ///if \c e is an DualExpr and \c v
+    ///and \c w are of type \ref Row, then you can
+    ///read and modify the coefficients like
+    ///these.
+    ///\code
+    ///e[v]=5;
+    ///e[v]+=12;
+    ///e.erase(v);
+    ///\endcode
+    ///or you can also iterate through its elements.
+    ///\code
+    ///double s=0;
+    ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
+    ///  s+=i->second;
+    ///\endcode
+    ///(This code computes the sum of all coefficients).
+    ///- Numbers (<tt>double</tt>'s)
+    ///and variables (\ref Row "Row"s) directly convert to an
+    ///\ref DualExpr and the usual linear operations are defined so  
+    ///\code
+    ///v+w
+    ///2*v-3.12*(v-w/2)
+    ///v*2.1+(3*v+(v*12+w)*3)/2
+    ///\endcode
+    ///are valid \ref DualExpr "DualExpr"essions.
+    ///The usual assignment operations are also defined.
+    ///\code
+    ///e=v+w;
+    ///e+=2*v-3.12*(v-w/2);
+    ///e*=3.4;
+    ///e/=5;
+    ///\endcode
+    ///
+    ///\sa Expr
+    ///
+    class DualExpr : public std::map<Row,Value>
+    {
+    public:
+      typedef LpSolverBase::Row Key; 
+      typedef LpSolverBase::Value Value;
+      
+    protected:
+      typedef std::map<Row,Value> Base;
+      
+    public:
+      typedef True IsLinExpression;
+      ///\e
+      DualExpr() : Base() { }
+      ///\e
+      DualExpr(const Key &v) {
+        Base::insert(std::make_pair(v, 1));
+      }
+      ///\e
+      DualExpr(const Value &v) {}
+      ///\e
+      void set(const Key &v,const Value &c) {
+        Base::insert(std::make_pair(v, c));
+      }
+      
+      ///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;
+        }
+      }
+
+      ///Sets all coefficients to 0.
+      void clear() {
+        Base::clear();
+      }
+
+      ///\e
+      DualExpr &operator+=(const DualExpr &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"
+        return *this;
+      }
+      ///\e
+      DualExpr &operator-=(const DualExpr &e) {
+        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
+          (*this)[j->first]-=j->second;
+        return *this;
+      }
+      ///\e
+      DualExpr &operator*=(const Value &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second*=c;
+        return *this;
+      }
+      ///\e
+      DualExpr &operator/=(const Value &c) {
+        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
+          j->second/=c;
+        return *this;
+      }
+    };
+    
 
   protected:
@@ -548 +658 @@
 #endif
 
-    ///Add a new empty row (i.e a new constaint) to the LP
-
-    ///This function adds a new empty row (i.e a new constaint) to the LP.
+    ///Set a column (i.e a dual constraint) of the LP
+
+    ///\param c is the column to be modified
+    ///\param e is a dual linear expression (see \ref DualExpr)
+    ///\bug This is a temportary function. The interface will change to
+    ///a better one.
+    void setCol(Col c,const DualExpr &e) {
+      std::vector<int> indices;
+      std::vector<Value> values;
+      indices.push_back(0);
+      values.push_back(0);
+      for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
+        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
+          indices.push_back(cols.floatingId((*i).first.id));
+          values.push_back((*i).second);
+        }
+      _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
+                    &indices[0],&values[0]);
+    }
+
+    ///Add a new column to the LP
+
+    ///\param e is a dual linear expression (see \ref DualExpr)
+    ///\param obj is the corresponding component of the objective
+    ///function. It is 0 by default.
+    ///\return The created column.
+    ///\bug This is a temportary function. The interface will change to
+    ///a better one.
+    Col addCol(Value l,const DualExpr &e, Value obj=0) {
+      Col c=addCol();
+      setCol(c,e);
+      objCoeff(c,0);
+      return c;
+    }
+
+    ///Add a new empty row (i.e a new constraint) to the LP
+
+    ///This function adds a new empty row (i.e a new constraint) to the LP.
     ///\return The created row
     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
 
-    ///Set a row (i.e a constaint) of the LP
+    ///\brief Adds several new row
+    ///(i.e a variables) at once
+    ///
+    ///This magic function takes a container as its argument
+    ///and fills its elements
+    ///with new row (i.e. variables)
+    ///\param t can be
+    ///- a standard STL compatible iterable container with
+    ///\ref Row as its \c values_type
+    ///like
+    ///\code
+    ///std::vector<LpSolverBase::Row>
+    ///std::list<LpSolverBase::Row>
+    ///\endcode
+    ///- a standard STL compatible iterable container with
+    ///\ref Row as its \c mapped_type
+    ///like
+    ///\code
+    ///std::map<AnyType,LpSolverBase::Row>
+    ///\endcode
+    ///- an iterable lemon \ref concept::WriteMap "write map" like 
+    ///\code
+    ///ListGraph::NodeMap<LpSolverBase::Row>
+    ///ListGraph::EdgeMap<LpSolverBase::Row>
+    ///\endcode
+    ///\return The number of rows created.
+#ifdef DOXYGEN
+    template<class T>
+    int addRowSet(T &t) { return 0;} 
+#else
+    template<class T>
+    typename enable_if<typename T::value_type::LpSolverRow,int>::type
+    addRowSet(T &t,dummy<0> = 0) {
+      int s=0;
+      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
+      return s;
+    }
+    template<class T>
+    typename enable_if<typename T::value_type::second_type::LpSolverRow,
+                       int>::type
+    addRowSet(T &t,dummy<1> = 1) { 
+      int s=0;
+      for(typename T::iterator i=t.begin();i!=t.end();++i) {
+        i->second=addRow();
+        s++;
+      }
+      return s;
+    }
+    template<class T>
+    typename enable_if<typename T::ValueSet::value_type::LpSolverRow,
+                       int>::type
+    addRowSet(T &t,dummy<2> = 2) { 
+      ///\bug <tt>return addRowSet(t.valueSet());</tt> should also work.
+      int s=0;
+      for(typename T::ValueSet::iterator i=t.valueSet().begin();
+          i!=t.valueSet().end();
+          ++i)
+        {
+          *i=addRow();
+          s++;
+        }
+      return s;
+    }
+#endif
+
+    ///Set a row (i.e a constraint) of the LP
 
     ///\param r is the row to be modified
@@ -581 +791 @@
     }
 
-    ///Set a row (i.e a constaint) of the LP
+    ///Set a row (i.e a constraint) of the LP
 
     ///\param r is the row to be modified
@@ -592 +802 @@
     }
 
-    ///Add a new row (i.e a new constaint) to the LP
+    ///Add a new row (i.e a new constraint) to the LP
 
     ///\param l is the lower bound (-\ref INF means no bound)
@@ -606 +816 @@
     }
 
-    ///Add a new row (i.e a new constaint) to the LP
+    ///Add a new row (i.e a new constraint) to the LP
 
     ///\param c is a linear expression (see \ref Constr)
@@ -918 +1128 @@
   }
 
+  ///\e
+  
+  ///\relates LpSolverBase::DualExpr
+  ///
+  inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
+                                      const LpSolverBase::DualExpr &b) 
+  {
+    LpSolverBase::DualExpr tmp(a);
+    tmp+=b; ///\todo Doesn't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::DualExpr
+  ///
+  inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
+                                      const LpSolverBase::DualExpr &b) 
+  {
+    LpSolverBase::DualExpr tmp(a);
+    tmp-=b; ///\todo Doesn't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::DualExpr
+  ///
+  inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
+                                      const LpSolverBase::Value &b) 
+  {
+    LpSolverBase::DualExpr tmp(a);
+    tmp*=b; ///\todo Doesn't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
+  ///\e
+  
+  ///\relates LpSolverBase::DualExpr
+  ///
+  inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
+                                      const LpSolverBase::DualExpr &b) 
+  {
+    LpSolverBase::DualExpr tmp(b);
+    tmp*=a; ///\todo Doesn't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  ///\e
+  
+  ///\relates LpSolverBase::DualExpr
+  ///
+  inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
+                                      const LpSolverBase::Value &b) 
+  {
+    LpSolverBase::DualExpr tmp(a);
+    tmp/=b; ///\todo Doesn't STL have some special 'merge' algorithm?
+    return tmp;
+  }
+  
 
 } //namespace lemon

test/lp_test.cc

@@ -35 +35 @@
   lp.addColSet(z);
 
+  {
+    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
+       );
 
-  LP::Expr e,f,g;
-  LP::Col p1,p2,p3,p4,p5;
-  LP::Constr c;
+
+    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.addRow(LP::INF,e,23);
+    lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
+    lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
+    
+    lp.addRow(x[1]+x[3]<=x[5]-3);
+    lp.addRow(-7<=x[1]+x[3]-12<=3);
+    lp.addRow(x[1]<=x[5]);
+  }
   
-  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
-     );
+  {
+    LP::DualExpr e,f,g;
+    LP::Row p1,p2,p3,p4,p5;
+    
+    e[p1]=2;
+    e[p1]+=2;
+    e[p1]-=2;
+    
+    e=p1;
+    e=f;
+    
+    e+=p1;
+    e+=f;
+    
+    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)+
+       (p1+f)+(f+p1)+(f+g)+
+       (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.addRow(LP::INF,e,23);
-  lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
-  lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
-
-  lp.addRow(x[1]+x[3]<=x[5]-3);
-  lp.addRow(-7<=x[1]+x[3]-12<=3);
-  lp.addRow(x[1]<=x[5]);
-
-
-  
 }