COIN-OR::LEMON - Graph Library

Changeset 1445:4635352e5524 in lemon-0.x


Ignore:
Timestamp:
06/04/05 14:50:15 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1925
Message:

DualExpr? added.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_base.h

    r1439 r1445  
    411411    };
    412412   
     413    ///Linear expression of rows
     414   
     415    ///This data structure represents a column of the matrix,
     416    ///thas is it strores a linear expression of the dual variables
     417    ///(\ref Row "Row"s).
     418    ///
     419    ///There are several ways to access and modify the contents of this
     420    ///container.
     421    ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
     422    ///if \c e is an DualExpr and \c v
     423    ///and \c w are of type \ref Row, then you can
     424    ///read and modify the coefficients like
     425    ///these.
     426    ///\code
     427    ///e[v]=5;
     428    ///e[v]+=12;
     429    ///e.erase(v);
     430    ///\endcode
     431    ///or you can also iterate through its elements.
     432    ///\code
     433    ///double s=0;
     434    ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
     435    ///  s+=i->second;
     436    ///\endcode
     437    ///(This code computes the sum of all coefficients).
     438    ///- Numbers (<tt>double</tt>'s)
     439    ///and variables (\ref Row "Row"s) directly convert to an
     440    ///\ref DualExpr and the usual linear operations are defined so 
     441    ///\code
     442    ///v+w
     443    ///2*v-3.12*(v-w/2)
     444    ///v*2.1+(3*v+(v*12+w)*3)/2
     445    ///\endcode
     446    ///are valid \ref DualExpr "DualExpr"essions.
     447    ///The usual assignment operations are also defined.
     448    ///\code
     449    ///e=v+w;
     450    ///e+=2*v-3.12*(v-w/2);
     451    ///e*=3.4;
     452    ///e/=5;
     453    ///\endcode
     454    ///
     455    ///\sa Expr
     456    ///
     457    class DualExpr : public std::map<Row,Value>
     458    {
     459    public:
     460      typedef LpSolverBase::Row Key;
     461      typedef LpSolverBase::Value Value;
     462     
     463    protected:
     464      typedef std::map<Row,Value> Base;
     465     
     466    public:
     467      typedef True IsLinExpression;
     468      ///\e
     469      DualExpr() : Base() { }
     470      ///\e
     471      DualExpr(const Key &v) {
     472        Base::insert(std::make_pair(v, 1));
     473      }
     474      ///\e
     475      DualExpr(const Value &v) {}
     476      ///\e
     477      void set(const Key &v,const Value &c) {
     478        Base::insert(std::make_pair(v, c));
     479      }
     480     
     481      ///Removes the components with zero coefficient.
     482      void simplify() {
     483        for (Base::iterator i=Base::begin(); i!=Base::end();) {
     484          Base::iterator j=i;
     485          ++j;
     486          if ((*i).second==0) Base::erase(i);
     487          j=i;
     488        }
     489      }
     490
     491      ///Sets all coefficients to 0.
     492      void clear() {
     493        Base::clear();
     494      }
     495
     496      ///\e
     497      DualExpr &operator+=(const DualExpr &e) {
     498        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     499          (*this)[j->first]+=j->second;
     500        ///\todo it might be speeded up using "hints"
     501        return *this;
     502      }
     503      ///\e
     504      DualExpr &operator-=(const DualExpr &e) {
     505        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
     506          (*this)[j->first]-=j->second;
     507        return *this;
     508      }
     509      ///\e
     510      DualExpr &operator*=(const Value &c) {
     511        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     512          j->second*=c;
     513        return *this;
     514      }
     515      ///\e
     516      DualExpr &operator/=(const Value &c) {
     517        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
     518          j->second/=c;
     519        return *this;
     520      }
     521    };
     522   
    413523
    414524  protected:
     
    548658#endif
    549659
    550     ///Add a new empty row (i.e a new constaint) to the LP
    551 
    552     ///This function adds a new empty row (i.e a new constaint) to the LP.
     660    ///Set a column (i.e a dual constraint) of the LP
     661
     662    ///\param c is the column to be modified
     663    ///\param e is a dual linear expression (see \ref DualExpr)
     664    ///\bug This is a temportary function. The interface will change to
     665    ///a better one.
     666    void setCol(Col c,const DualExpr &e) {
     667      std::vector<int> indices;
     668      std::vector<Value> values;
     669      indices.push_back(0);
     670      values.push_back(0);
     671      for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
     672        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
     673          indices.push_back(cols.floatingId((*i).first.id));
     674          values.push_back((*i).second);
     675        }
     676      _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
     677                    &indices[0],&values[0]);
     678    }
     679
     680    ///Add a new column to the LP
     681
     682    ///\param e is a dual linear expression (see \ref DualExpr)
     683    ///\param obj is the corresponding component of the objective
     684    ///function. It is 0 by default.
     685    ///\return The created column.
     686    ///\bug This is a temportary function. The interface will change to
     687    ///a better one.
     688    Col addCol(Value l,const DualExpr &e, Value obj=0) {
     689      Col c=addCol();
     690      setCol(c,e);
     691      objCoeff(c,0);
     692      return c;
     693    }
     694
     695    ///Add a new empty row (i.e a new constraint) to the LP
     696
     697    ///This function adds a new empty row (i.e a new constraint) to the LP.
    553698    ///\return The created row
    554699    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
    555700
    556     ///Set a row (i.e a constaint) of the LP
     701    ///\brief Adds several new row
     702    ///(i.e a variables) at once
     703    ///
     704    ///This magic function takes a container as its argument
     705    ///and fills its elements
     706    ///with new row (i.e. variables)
     707    ///\param t can be
     708    ///- a standard STL compatible iterable container with
     709    ///\ref Row as its \c values_type
     710    ///like
     711    ///\code
     712    ///std::vector<LpSolverBase::Row>
     713    ///std::list<LpSolverBase::Row>
     714    ///\endcode
     715    ///- a standard STL compatible iterable container with
     716    ///\ref Row as its \c mapped_type
     717    ///like
     718    ///\code
     719    ///std::map<AnyType,LpSolverBase::Row>
     720    ///\endcode
     721    ///- an iterable lemon \ref concept::WriteMap "write map" like
     722    ///\code
     723    ///ListGraph::NodeMap<LpSolverBase::Row>
     724    ///ListGraph::EdgeMap<LpSolverBase::Row>
     725    ///\endcode
     726    ///\return The number of rows created.
     727#ifdef DOXYGEN
     728    template<class T>
     729    int addRowSet(T &t) { return 0;}
     730#else
     731    template<class T>
     732    typename enable_if<typename T::value_type::LpSolverRow,int>::type
     733    addRowSet(T &t,dummy<0> = 0) {
     734      int s=0;
     735      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
     736      return s;
     737    }
     738    template<class T>
     739    typename enable_if<typename T::value_type::second_type::LpSolverRow,
     740                       int>::type
     741    addRowSet(T &t,dummy<1> = 1) {
     742      int s=0;
     743      for(typename T::iterator i=t.begin();i!=t.end();++i) {
     744        i->second=addRow();
     745        s++;
     746      }
     747      return s;
     748    }
     749    template<class T>
     750    typename enable_if<typename T::ValueSet::value_type::LpSolverRow,
     751                       int>::type
     752    addRowSet(T &t,dummy<2> = 2) {
     753      ///\bug <tt>return addRowSet(t.valueSet());</tt> should also work.
     754      int s=0;
     755      for(typename T::ValueSet::iterator i=t.valueSet().begin();
     756          i!=t.valueSet().end();
     757          ++i)
     758        {
     759          *i=addRow();
     760          s++;
     761        }
     762      return s;
     763    }
     764#endif
     765
     766    ///Set a row (i.e a constraint) of the LP
    557767
    558768    ///\param r is the row to be modified
     
    581791    }
    582792
    583     ///Set a row (i.e a constaint) of the LP
     793    ///Set a row (i.e a constraint) of the LP
    584794
    585795    ///\param r is the row to be modified
     
    592802    }
    593803
    594     ///Add a new row (i.e a new constaint) to the LP
     804    ///Add a new row (i.e a new constraint) to the LP
    595805
    596806    ///\param l is the lower bound (-\ref INF means no bound)
     
    606816    }
    607817
    608     ///Add a new row (i.e a new constaint) to the LP
     818    ///Add a new row (i.e a new constraint) to the LP
    609819
    610820    ///\param c is a linear expression (see \ref Constr)
     
    9181128  }
    9191129
     1130  ///\e
     1131 
     1132  ///\relates LpSolverBase::DualExpr
     1133  ///
     1134  inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
     1135                                      const LpSolverBase::DualExpr &b)
     1136  {
     1137    LpSolverBase::DualExpr tmp(a);
     1138    tmp+=b; ///\todo Doesn't STL have some special 'merge' algorithm?
     1139    return tmp;
     1140  }
     1141  ///\e
     1142 
     1143  ///\relates LpSolverBase::DualExpr
     1144  ///
     1145  inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
     1146                                      const LpSolverBase::DualExpr &b)
     1147  {
     1148    LpSolverBase::DualExpr tmp(a);
     1149    tmp-=b; ///\todo Doesn't STL have some special 'merge' algorithm?
     1150    return tmp;
     1151  }
     1152  ///\e
     1153 
     1154  ///\relates LpSolverBase::DualExpr
     1155  ///
     1156  inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
     1157                                      const LpSolverBase::Value &b)
     1158  {
     1159    LpSolverBase::DualExpr tmp(a);
     1160    tmp*=b; ///\todo Doesn't STL have some special 'merge' algorithm?
     1161    return tmp;
     1162  }
     1163 
     1164  ///\e
     1165 
     1166  ///\relates LpSolverBase::DualExpr
     1167  ///
     1168  inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
     1169                                      const LpSolverBase::DualExpr &b)
     1170  {
     1171    LpSolverBase::DualExpr tmp(b);
     1172    tmp*=a; ///\todo Doesn't STL have some special 'merge' algorithm?
     1173    return tmp;
     1174  }
     1175  ///\e
     1176 
     1177  ///\relates LpSolverBase::DualExpr
     1178  ///
     1179  inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
     1180                                      const LpSolverBase::Value &b)
     1181  {
     1182    LpSolverBase::DualExpr tmp(a);
     1183    tmp/=b; ///\todo Doesn't STL have some special 'merge' algorithm?
     1184    return tmp;
     1185  }
     1186 
    9201187
    9211188} //namespace lemon
  • test/lp_test.cc

    r1437 r1445  
    3535  lp.addColSet(z);
    3636
     37  {
     38    LP::Expr e,f,g;
     39    LP::Col p1,p2,p3,p4,p5;
     40    LP::Constr c;
     41   
     42    e[p1]=2;
     43    e.constComp()=12;
     44    e[p1]+=2;
     45    e.constComp()+=12;
     46    e[p1]-=2;
     47    e.constComp()-=12;
     48   
     49    e=2;
     50    e=2.2;
     51    e=p1;
     52    e=f;
     53   
     54    e+=2;
     55    e+=2.2;
     56    e+=p1;
     57    e+=f;
     58   
     59    e-=2;
     60    e-=2.2;
     61    e-=p1;
     62    e-=f;
     63   
     64    e*=2;
     65    e*=2.2;
     66    e/=2;
     67    e/=2.2;
     68   
     69    e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
     70       (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
     71       (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
     72       2.2*f+f*2.2+f/2.2+
     73       2*f+f*2+f/2+
     74       2.2*p1+p1*2.2+p1/2.2+
     75       2*p1+p1*2+p1/2
     76       );
    3777
    38   LP::Expr e,f,g;
    39   LP::Col p1,p2,p3,p4,p5;
    40   LP::Constr c;
     78
     79    c = (e  <= f  );
     80    c = (e  <= 2.2);
     81    c = (e  <= 2  );
     82    c = (e  <= p1 );
     83    c = (2.2<= f  );
     84    c = (2  <= f  );
     85    c = (p1 <= f  );
     86    c = (p1 <= p2 );
     87    c = (p1 <= 2.2);
     88    c = (p1 <= 2  );
     89    c = (2.2<= p2 );
     90    c = (2  <= p2 );
     91   
     92    c = (e  >= f  );
     93    c = (e  >= 2.2);
     94    c = (e  >= 2  );
     95    c = (e  >= p1 );
     96    c = (2.2>= f  );
     97    c = (2  >= f  );
     98    c = (p1 >= f  );
     99    c = (p1 >= p2 );
     100    c = (p1 >= 2.2);
     101    c = (p1 >= 2  );
     102    c = (2.2>= p2 );
     103    c = (2  >= p2 );
     104   
     105    c = (e  == f  );
     106    c = (e  == 2.2);
     107    c = (e  == 2  );
     108    c = (e  == p1 );
     109    c = (2.2== f  );
     110    c = (2  == f  );
     111    c = (p1 == f  );
     112    //c = (p1 == p2 );
     113    c = (p1 == 2.2);
     114    c = (p1 == 2  );
     115    c = (2.2== p2 );
     116    c = (2  == p2 );
     117   
     118    c = (2 <= e <= 3);
     119    c = (2 <= p1<= 3);
     120   
     121    c = (2 >= e >= 3);
     122    c = (2 >= p1>= 3);
     123   
     124    e[x[3]]=2;
     125    e[x[3]]=4;
     126    e[x[3]]=1;
     127    e.constComp()=12;
     128   
     129    lp.addRow(LP::INF,e,23);
     130    lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
     131    lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
     132   
     133    lp.addRow(x[1]+x[3]<=x[5]-3);
     134    lp.addRow(-7<=x[1]+x[3]-12<=3);
     135    lp.addRow(x[1]<=x[5]);
     136  }
    41137 
    42   e[p1]=2;
    43   e.constComp()=12;
    44   e[p1]+=2;
    45   e.constComp()+=12;
    46   e[p1]-=2;
    47   e.constComp()-=12;
    48  
    49   e=2;
    50   e=2.2;
    51   e=p1;
    52   e=f;
    53 
    54   e+=2;
    55   e+=2.2;
    56   e+=p1;
    57   e+=f;
    58 
    59   e-=2;
    60   e-=2.2;
    61   e-=p1;
    62   e-=f;
    63 
    64   e*=2;
    65   e*=2.2;
    66   e/=2;
    67   e/=2.2;
    68 
    69   e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
    70       (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
    71       (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
    72       2.2*f+f*2.2+f/2.2+
    73       2*f+f*2+f/2+
    74       2.2*p1+p1*2.2+p1/2.2+
    75       2*p1+p1*2+p1/2
    76      );
     138  {
     139    LP::DualExpr e,f,g;
     140    LP::Row p1,p2,p3,p4,p5;
     141   
     142    e[p1]=2;
     143    e[p1]+=2;
     144    e[p1]-=2;
     145   
     146    e=p1;
     147    e=f;
     148   
     149    e+=p1;
     150    e+=f;
     151   
     152    e-=p1;
     153    e-=f;
     154   
     155    e*=2;
     156    e*=2.2;
     157    e/=2;
     158    e/=2.2;
     159   
     160    e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
     161       (p1+f)+(f+p1)+(f+g)+
     162       (p1-f)+(f-p1)+(f-g)+
     163       2.2*f+f*2.2+f/2.2+
     164       2*f+f*2+f/2+
     165       2.2*p1+p1*2.2+p1/2.2+
     166       2*p1+p1*2+p1/2
     167       );
     168  }
    77169 
    78170
    79   c = (e  <= f  );
    80   c = (e  <= 2.2);
    81   c = (e  <= 2  );
    82   c = (e  <= p1 );
    83   c = (2.2<= f  );
    84   c = (2  <= f  );
    85   c = (p1 <= f  );
    86   c = (p1 <= p2 );
    87   c = (p1 <= 2.2);
    88   c = (p1 <= 2  );
    89   c = (2.2<= p2 );
    90   c = (2  <= p2 );
    91 
    92   c = (e  >= f  );
    93   c = (e  >= 2.2);
    94   c = (e  >= 2  );
    95   c = (e  >= p1 );
    96   c = (2.2>= f  );
    97   c = (2  >= f  );
    98   c = (p1 >= f  );
    99   c = (p1 >= p2 );
    100   c = (p1 >= 2.2);
    101   c = (p1 >= 2  );
    102   c = (2.2>= p2 );
    103   c = (2  >= p2 );
    104 
    105   c = (e  == f  );
    106   c = (e  == 2.2);
    107   c = (e  == 2  );
    108   c = (e  == p1 );
    109   c = (2.2== f  );
    110   c = (2  == f  );
    111   c = (p1 == f  );
    112   //c = (p1 == p2 );
    113   c = (p1 == 2.2);
    114   c = (p1 == 2  );
    115   c = (2.2== p2 );
    116   c = (2  == p2 );
    117 
    118   c = (2 <= e <= 3);
    119   c = (2 <= p1<= 3);
    120 
    121   c = (2 >= e >= 3);
    122   c = (2 >= p1>= 3);
    123 
    124   e[x[3]]=2;
    125   e[x[3]]=4;
    126   e[x[3]]=1;
    127   e.constComp()=12;
    128  
    129   lp.addRow(LP::INF,e,23);
    130   lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
    131   lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
    132 
    133   lp.addRow(x[1]+x[3]<=x[5]-3);
    134   lp.addRow(-7<=x[1]+x[3]-12<=3);
    135   lp.addRow(x[1]<=x[5]);
    136 
    137 
    138  
    139171}
    140172
Note: See TracChangeset for help on using the changeset viewer.