1.1 --- a/src/work/athos/lp/lp_base.cc Tue Mar 29 13:30:29 2005 +0000
1.2 +++ b/src/work/athos/lp/lp_base.cc Wed Mar 30 08:28:44 2005 +0000
1.3 @@ -25,5 +25,9 @@
1.4 const LpSolverBase::Value
1.5 LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
1.6
1.7 -
1.8 + const LpSolverBase::Constr::Coeff
1.9 + LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
1.10 + const LpSolverBase::Constr::Coeff
1.11 + LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
1.12 +
1.13 } //namespace lemon
2.1 --- a/src/work/athos/lp/lp_base.h Tue Mar 29 13:30:29 2005 +0000
2.2 +++ b/src/work/athos/lp/lp_base.h Wed Mar 30 08:28:44 2005 +0000
2.3 @@ -18,13 +18,15 @@
2.4 #define LEMON_LP_BASE_H
2.5
2.6 #include<vector>
2.7 +#include<map>
2.8 #include<limits>
2.9
2.10 #include<lemon/utility.h>
2.11 #include<lemon/error.h>
2.12 #include<lemon/invalid.h>
2.13
2.14 -#include"lin_expr.h"
2.15 +//#include"lin_expr.h"
2.16 +
2.17 ///\file
2.18 ///\brief The interface of the LP solver interface.
2.19 namespace lemon {
2.20 @@ -168,9 +170,105 @@
2.21 };
2.22
2.23 ///Linear expression
2.24 - typedef SparseLinExpr<Col> Expr;
2.25 + // typedef SparseLinExpr<Col> Expr;
2.26 + class Expr : public std::map<Col,Col::ExprValue>
2.27 + {
2.28 + public:
2.29 + typedef Col Var;
2.30 + typedef Col::ExprValue Coeff;
2.31 +
2.32 + protected:
2.33 + typedef std::map<Col,Col::ExprValue> Base;
2.34 +
2.35 + Coeff const_comp;
2.36 + public:
2.37 + typedef True IsLinExpression;
2.38 + ///\e
2.39 + Expr() : Base(), const_comp(0) { }
2.40 + ///\e
2.41 + Expr(const Var &v) : const_comp(0) {
2.42 + Base::insert(std::make_pair(v, 1));
2.43 + }
2.44 + ///\e
2.45 + Expr(const Coeff &v) : const_comp(v) {}
2.46 + ///\e
2.47 + void set(const Var &v,const Coeff &c) {
2.48 + Base::insert(std::make_pair(v, c));
2.49 + }
2.50 + ///\e
2.51 + Coeff &constComp() { return const_comp; }
2.52 + ///\e
2.53 + const Coeff &constComp() const { return const_comp; }
2.54 +
2.55 + ///Removes the components with zero coefficient.
2.56 + void simplify() {
2.57 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
2.58 + Base::iterator j=i;
2.59 + ++j;
2.60 + if ((*i).second==0) Base::erase(i);
2.61 + j=i;
2.62 + }
2.63 + }
2.64 +
2.65 + ///\e
2.66 + Expr &operator+=(const Expr &e) {
2.67 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
2.68 + (*this)[j->first]+=j->second;
2.69 + ///\todo it might be speeded up using "hints"
2.70 + const_comp+=e.const_comp;
2.71 + return *this;
2.72 + }
2.73 + ///\e
2.74 + Expr &operator-=(const Expr &e) {
2.75 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
2.76 + (*this)[j->first]-=j->second;
2.77 + const_comp-=e.const_comp;
2.78 + return *this;
2.79 + }
2.80 + ///\e
2.81 + Expr &operator*=(const Coeff &c) {
2.82 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
2.83 + j->second*=c;
2.84 + const_comp*=c;
2.85 + return *this;
2.86 + }
2.87 + ///\e
2.88 + Expr &operator/=(const Coeff &c) {
2.89 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
2.90 + j->second/=c;
2.91 + const_comp/=c;
2.92 + return *this;
2.93 + }
2.94 + };
2.95 +
2.96 ///Linear constraint
2.97 - typedef LinConstr<Expr> Constr;
2.98 + //typedef LinConstr<Expr> Constr;
2.99 + class Constr
2.100 + {
2.101 + public:
2.102 + typedef LpSolverBase::Expr Expr;
2.103 + typedef Expr::Var Var;
2.104 + typedef Expr::Coeff Coeff;
2.105 +
2.106 + static const Coeff INF;
2.107 + static const Coeff NaN;
2.108 + // static const Coeff INF=0;
2.109 + // static const Coeff NaN=1;
2.110 +
2.111 + Expr expr;
2.112 + Coeff lb,ub;
2.113 +
2.114 + Constr() : expr(), lb(NaN), ub(NaN) {}
2.115 + Constr(Coeff _lb,const Expr &e,Coeff _ub) :
2.116 + expr(e), lb(_lb), ub(_ub) {}
2.117 + Constr(const Expr &e,Coeff _ub) :
2.118 + expr(e), lb(NaN), ub(_ub) {}
2.119 + Constr(Coeff _lb,const Expr &e) :
2.120 + expr(e), lb(_lb), ub(NaN) {}
2.121 + Constr(const Expr &e) :
2.122 + expr(e), lb(NaN), ub(NaN) {}
2.123 + };
2.124 +
2.125
2.126 protected:
2.127 _FixId rows;
2.128 @@ -290,6 +388,21 @@
2.129 }
2.130 return s;
2.131 }
2.132 + template<class T>
2.133 + typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
2.134 + int>::type
2.135 + addColSet(T &t,dummy<2> = 2) {
2.136 + ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
2.137 + int s=0;
2.138 + for(typename T::ValueSet::iterator i=t.valueSet().begin();
2.139 + i!=t.valueSet().end();
2.140 + ++i)
2.141 + {
2.142 + *i=addCol();
2.143 + s++;
2.144 + }
2.145 + return s;
2.146 + }
2.147 #endif
2.148
2.149 ///Add a new empty row (i.e a new constaint) to the LP
2.150 @@ -326,8 +439,6 @@
2.151
2.152 ///\param r is the row to be modified
2.153 ///\param c is a linear expression (see \ref Constr)
2.154 - ///\bug This is a temportary function. The interface will change to
2.155 - ///a better one.
2.156 void setRow(Row r, const Constr &c) {
2.157 Value lb= c.lb==NaN?-INF:lb;
2.158 Value ub= c.ub==NaN?INF:lb;
2.159 @@ -352,8 +463,6 @@
2.160
2.161 ///\param c is a linear expression (see \ref Constr)
2.162 ///\return The created row.
2.163 - ///\bug This is a temportary function. The interface will change to
2.164 - ///a better one.
2.165 Row addRow(const Constr &c) {
2.166 Row r=addRow();
2.167 setRow(r,c);
2.168 @@ -427,6 +536,186 @@
2.169
2.170 };
2.171
2.172 + ///\e
2.173 +
2.174 + ///\relates LpSolverBase::Expr
2.175 + ///
2.176 + inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
2.177 + const LpSolverBase::Expr &b)
2.178 + {
2.179 + LpSolverBase::Expr tmp(a);
2.180 + tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
2.181 + return tmp;
2.182 + }
2.183 + ///\e
2.184 +
2.185 + ///\relates LpSolverBase::Expr
2.186 + ///
2.187 + inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
2.188 + const LpSolverBase::Expr &b)
2.189 + {
2.190 + LpSolverBase::Expr tmp(a);
2.191 + tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
2.192 + return tmp;
2.193 + }
2.194 + ///\e
2.195 +
2.196 + ///\relates LpSolverBase::Expr
2.197 + ///
2.198 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
2.199 + const LpSolverBase::Expr::Coeff &b)
2.200 + {
2.201 + LpSolverBase::Expr tmp(a);
2.202 + tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
2.203 + return tmp;
2.204 + }
2.205 +
2.206 + ///\e
2.207 +
2.208 + ///\relates LpSolverBase::Expr
2.209 + ///
2.210 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
2.211 + const LpSolverBase::Expr &b)
2.212 + {
2.213 + LpSolverBase::Expr tmp(b);
2.214 + tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
2.215 + return tmp;
2.216 + }
2.217 + ///\e
2.218 +
2.219 + ///\relates LpSolverBase::Expr
2.220 + ///
2.221 + inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
2.222 + const LpSolverBase::Expr::Coeff &b)
2.223 + {
2.224 + LpSolverBase::Expr tmp(a);
2.225 + tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
2.226 + return tmp;
2.227 + }
2.228 +
2.229 + ///\e
2.230 +
2.231 + ///\relates LpSolverBase::Constr
2.232 + ///
2.233 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
2.234 + const LpSolverBase::Expr &f)
2.235 + {
2.236 + return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
2.237 + }
2.238 +
2.239 + ///\e
2.240 +
2.241 + ///\relates LpSolverBase::Constr
2.242 + ///
2.243 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
2.244 + const LpSolverBase::Expr &f)
2.245 + {
2.246 + return LpSolverBase::Constr(e,f);
2.247 + }
2.248 +
2.249 + ///\e
2.250 +
2.251 + ///\relates LpSolverBase::Constr
2.252 + ///
2.253 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
2.254 + const LpSolverBase::Expr::Coeff &f)
2.255 + {
2.256 + return LpSolverBase::Constr(e,f);
2.257 + }
2.258 +
2.259 + ///\e
2.260 +
2.261 + ///\relates LpSolverBase::Constr
2.262 + ///
2.263 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
2.264 + const LpSolverBase::Expr &f)
2.265 + {
2.266 + return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
2.267 + }
2.268 +
2.269 +
2.270 + ///\e
2.271 +
2.272 + ///\relates LpSolverBase::Constr
2.273 + ///
2.274 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
2.275 + const LpSolverBase::Expr &f)
2.276 + {
2.277 + return LpSolverBase::Constr(f,e);
2.278 + }
2.279 +
2.280 +
2.281 + ///\e
2.282 +
2.283 + ///\relates LpSolverBase::Constr
2.284 + ///
2.285 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
2.286 + const LpSolverBase::Expr::Coeff &f)
2.287 + {
2.288 + return LpSolverBase::Constr(f,e);
2.289 + }
2.290 +
2.291 + ///\e
2.292 +
2.293 + ///\relates LpSolverBase::Constr
2.294 + ///
2.295 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
2.296 + const LpSolverBase::Expr &f)
2.297 + {
2.298 + return LpSolverBase::Constr(0,e-f,0);
2.299 + }
2.300 +
2.301 + ///\e
2.302 +
2.303 + ///\relates LpSolverBase::Constr
2.304 + ///
2.305 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
2.306 + const LpSolverBase::Constr&c)
2.307 + {
2.308 + LpSolverBase::Constr tmp(c);
2.309 + if(tmp.lb!=tmp.NaN) throw LogicError();
2.310 + else tmp.lb=n;
2.311 + return tmp;
2.312 + }
2.313 + ///\e
2.314 +
2.315 + ///\relates LpSolverBase::Constr
2.316 + ///
2.317 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
2.318 + const LpSolverBase::Constr::Coeff &n)
2.319 + {
2.320 + LpSolverBase::Constr tmp(c);
2.321 + if(tmp.ub!=tmp.NaN) throw LogicError();
2.322 + else tmp.ub=n;
2.323 + return tmp;
2.324 + }
2.325 +
2.326 + ///\e
2.327 +
2.328 + ///\relates LpSolverBase::Constr
2.329 + ///
2.330 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
2.331 + const LpSolverBase::Constr&c)
2.332 + {
2.333 + LpSolverBase::Constr tmp(c);
2.334 + if(tmp.ub!=tmp.NaN) throw LogicError();
2.335 + else tmp.ub=n;
2.336 + return tmp;
2.337 + }
2.338 + ///\e
2.339 +
2.340 + ///\relates LpSolverBase::Constr
2.341 + ///
2.342 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
2.343 + const LpSolverBase::Constr::Coeff &n)
2.344 + {
2.345 + LpSolverBase::Constr tmp(c);
2.346 + if(tmp.lb!=tmp.NaN) throw LogicError();
2.347 + else tmp.lb=n;
2.348 + return tmp;
2.349 + }
2.350 +
2.351 +
2.352 } //namespace lemon
2.353
2.354 #endif //LEMON_LP_BASE_H
3.1 --- a/src/work/athos/lp/lp_test.cc Tue Mar 29 13:30:29 2005 +0000
3.2 +++ b/src/work/athos/lp/lp_test.cc Wed Mar 30 08:28:44 2005 +0000
3.3 @@ -24,13 +24,96 @@
3.4 lp.addColSet(z);
3.5
3.6
3.7 - LP::Expr e;
3.8 + LP::Expr e,f,g;
3.9 + LP::Col p1,p2,p3,p4,p5;
3.10 + LP::Constr c;
3.11 +
3.12 + e[p1]=2;
3.13 + e.constComp()=12;
3.14 + e[p1]+=2;
3.15 + e.constComp()+=12;
3.16 + e[p1]-=2;
3.17 + e.constComp()-=12;
3.18 +
3.19 + e=2;
3.20 + e=2.2;
3.21 + e=p1;
3.22 + e=f;
3.23 +
3.24 + e+=2;
3.25 + e+=2.2;
3.26 + e+=p1;
3.27 + e+=f;
3.28 +
3.29 + e-=2;
3.30 + e-=2.2;
3.31 + e-=p1;
3.32 + e-=f;
3.33 +
3.34 + e*=2;
3.35 + e*=2.2;
3.36 + e/=2;
3.37 + e/=2.2;
3.38 +
3.39 + e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
3.40 + (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
3.41 + (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
3.42 + 2.2*f+f*2.2+f/2.2+
3.43 + 2*f+f*2+f/2+
3.44 + 2.2*p1+p1*2.2+p1/2.2+
3.45 + 2*p1+p1*2+p1/2
3.46 + );
3.47 +
3.48 +
3.49 + c = (e <= f );
3.50 + c = (e <= 2.2);
3.51 + c = (e <= 2 );
3.52 + c = (e <= p1 );
3.53 + c = (2.2<= f );
3.54 + c = (2 <= f );
3.55 + c = (p1 <= f );
3.56 + c = (p1 <= p2 );
3.57 + c = (p1 <= 2.2);
3.58 + c = (p1 <= 2 );
3.59 + c = (2.2<= p2 );
3.60 + c = (2 <= p2 );
3.61 +
3.62 + c = (e >= f );
3.63 + c = (e >= 2.2);
3.64 + c = (e >= 2 );
3.65 + c = (e >= p1 );
3.66 + c = (2.2>= f );
3.67 + c = (2 >= f );
3.68 + c = (p1 >= f );
3.69 + c = (p1 >= p2 );
3.70 + c = (p1 >= 2.2);
3.71 + c = (p1 >= 2 );
3.72 + c = (2.2>= p2 );
3.73 + c = (2 >= p2 );
3.74 +
3.75 + c = (e == f );
3.76 + c = (e == 2.2);
3.77 + c = (e == 2 );
3.78 + c = (e == p1 );
3.79 + c = (2.2== f );
3.80 + c = (2 == f );
3.81 + c = (p1 == f );
3.82 + //c = (p1 == p2 );
3.83 + c = (p1 == 2.2);
3.84 + c = (p1 == 2 );
3.85 + c = (2.2== p2 );
3.86 + c = (2 == p2 );
3.87 +
3.88 + c = (2 <= e <= 3);
3.89 + c = (2 <= p1<= 3);
3.90 +
3.91 + c = (2 >= e >= 3);
3.92 + c = (2 >= p1>= 3);
3.93 +
3.94 e[x[3]]=2;
3.95 e[x[3]]=4;
3.96 e[x[3]]=1;
3.97 e.constComp()=12;
3.98 -
3.99 - LP::Col p1,p2,p3,p4,p5;
3.100
3.101 lp.addRow(LP::INF,e,23);
3.102 lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
3.103 @@ -40,6 +123,8 @@
3.104
3.105 lp.addRow(x[1]+x[3]<=x[5]-3);
3.106 lp.addRow(-7<=x[1]+x[3]-12<=3);
3.107 + //lp.addRow(x[1]<=x[5]);
3.108 +
3.109 }
3.110
3.111
3.112 @@ -57,8 +142,8 @@
3.113 typedef typename G::InEdgeIt InEdgeIt;
3.114
3.115 typename G::EdgeMap<LpGlpk::Col> x(g);
3.116 - // lp.addColSet(x);
3.117 - for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
3.118 + lp.addColSet(x);
3.119 + //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
3.120
3.121 for(EdgeIt e(g);e!=INVALID;++e) {
3.122 lp.setColUpperBound(x[e],cap[e]);