1.1 --- a/src/work/athos/lp/lp_base.h Tue Mar 29 13:30:29 2005 +0000
1.2 +++ b/src/work/athos/lp/lp_base.h Wed Mar 30 08:28:44 2005 +0000
1.3 @@ -18,13 +18,15 @@
1.4 #define LEMON_LP_BASE_H
1.5
1.6 #include<vector>
1.7 +#include<map>
1.8 #include<limits>
1.9
1.10 #include<lemon/utility.h>
1.11 #include<lemon/error.h>
1.12 #include<lemon/invalid.h>
1.13
1.14 -#include"lin_expr.h"
1.15 +//#include"lin_expr.h"
1.16 +
1.17 ///\file
1.18 ///\brief The interface of the LP solver interface.
1.19 namespace lemon {
1.20 @@ -168,9 +170,105 @@
1.21 };
1.22
1.23 ///Linear expression
1.24 - typedef SparseLinExpr<Col> Expr;
1.25 + // typedef SparseLinExpr<Col> Expr;
1.26 + class Expr : public std::map<Col,Col::ExprValue>
1.27 + {
1.28 + public:
1.29 + typedef Col Var;
1.30 + typedef Col::ExprValue Coeff;
1.31 +
1.32 + protected:
1.33 + typedef std::map<Col,Col::ExprValue> Base;
1.34 +
1.35 + Coeff const_comp;
1.36 + public:
1.37 + typedef True IsLinExpression;
1.38 + ///\e
1.39 + Expr() : Base(), const_comp(0) { }
1.40 + ///\e
1.41 + Expr(const Var &v) : const_comp(0) {
1.42 + Base::insert(std::make_pair(v, 1));
1.43 + }
1.44 + ///\e
1.45 + Expr(const Coeff &v) : const_comp(v) {}
1.46 + ///\e
1.47 + void set(const Var &v,const Coeff &c) {
1.48 + Base::insert(std::make_pair(v, c));
1.49 + }
1.50 + ///\e
1.51 + Coeff &constComp() { return const_comp; }
1.52 + ///\e
1.53 + const Coeff &constComp() const { return const_comp; }
1.54 +
1.55 + ///Removes the components with zero coefficient.
1.56 + void simplify() {
1.57 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
1.58 + Base::iterator j=i;
1.59 + ++j;
1.60 + if ((*i).second==0) Base::erase(i);
1.61 + j=i;
1.62 + }
1.63 + }
1.64 +
1.65 + ///\e
1.66 + Expr &operator+=(const Expr &e) {
1.67 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.68 + (*this)[j->first]+=j->second;
1.69 + ///\todo it might be speeded up using "hints"
1.70 + const_comp+=e.const_comp;
1.71 + return *this;
1.72 + }
1.73 + ///\e
1.74 + Expr &operator-=(const Expr &e) {
1.75 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
1.76 + (*this)[j->first]-=j->second;
1.77 + const_comp-=e.const_comp;
1.78 + return *this;
1.79 + }
1.80 + ///\e
1.81 + Expr &operator*=(const Coeff &c) {
1.82 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.83 + j->second*=c;
1.84 + const_comp*=c;
1.85 + return *this;
1.86 + }
1.87 + ///\e
1.88 + Expr &operator/=(const Coeff &c) {
1.89 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
1.90 + j->second/=c;
1.91 + const_comp/=c;
1.92 + return *this;
1.93 + }
1.94 + };
1.95 +
1.96 ///Linear constraint
1.97 - typedef LinConstr<Expr> Constr;
1.98 + //typedef LinConstr<Expr> Constr;
1.99 + class Constr
1.100 + {
1.101 + public:
1.102 + typedef LpSolverBase::Expr Expr;
1.103 + typedef Expr::Var Var;
1.104 + typedef Expr::Coeff Coeff;
1.105 +
1.106 + static const Coeff INF;
1.107 + static const Coeff NaN;
1.108 + // static const Coeff INF=0;
1.109 + // static const Coeff NaN=1;
1.110 +
1.111 + Expr expr;
1.112 + Coeff lb,ub;
1.113 +
1.114 + Constr() : expr(), lb(NaN), ub(NaN) {}
1.115 + Constr(Coeff _lb,const Expr &e,Coeff _ub) :
1.116 + expr(e), lb(_lb), ub(_ub) {}
1.117 + Constr(const Expr &e,Coeff _ub) :
1.118 + expr(e), lb(NaN), ub(_ub) {}
1.119 + Constr(Coeff _lb,const Expr &e) :
1.120 + expr(e), lb(_lb), ub(NaN) {}
1.121 + Constr(const Expr &e) :
1.122 + expr(e), lb(NaN), ub(NaN) {}
1.123 + };
1.124 +
1.125
1.126 protected:
1.127 _FixId rows;
1.128 @@ -290,6 +388,21 @@
1.129 }
1.130 return s;
1.131 }
1.132 + template<class T>
1.133 + typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
1.134 + int>::type
1.135 + addColSet(T &t,dummy<2> = 2) {
1.136 + ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
1.137 + int s=0;
1.138 + for(typename T::ValueSet::iterator i=t.valueSet().begin();
1.139 + i!=t.valueSet().end();
1.140 + ++i)
1.141 + {
1.142 + *i=addCol();
1.143 + s++;
1.144 + }
1.145 + return s;
1.146 + }
1.147 #endif
1.148
1.149 ///Add a new empty row (i.e a new constaint) to the LP
1.150 @@ -326,8 +439,6 @@
1.151
1.152 ///\param r is the row to be modified
1.153 ///\param c is a linear expression (see \ref Constr)
1.154 - ///\bug This is a temportary function. The interface will change to
1.155 - ///a better one.
1.156 void setRow(Row r, const Constr &c) {
1.157 Value lb= c.lb==NaN?-INF:lb;
1.158 Value ub= c.ub==NaN?INF:lb;
1.159 @@ -352,8 +463,6 @@
1.160
1.161 ///\param c is a linear expression (see \ref Constr)
1.162 ///\return The created row.
1.163 - ///\bug This is a temportary function. The interface will change to
1.164 - ///a better one.
1.165 Row addRow(const Constr &c) {
1.166 Row r=addRow();
1.167 setRow(r,c);
1.168 @@ -427,6 +536,186 @@
1.169
1.170 };
1.171
1.172 + ///\e
1.173 +
1.174 + ///\relates LpSolverBase::Expr
1.175 + ///
1.176 + inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1.177 + const LpSolverBase::Expr &b)
1.178 + {
1.179 + LpSolverBase::Expr tmp(a);
1.180 + tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
1.181 + return tmp;
1.182 + }
1.183 + ///\e
1.184 +
1.185 + ///\relates LpSolverBase::Expr
1.186 + ///
1.187 + inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1.188 + const LpSolverBase::Expr &b)
1.189 + {
1.190 + LpSolverBase::Expr tmp(a);
1.191 + tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
1.192 + return tmp;
1.193 + }
1.194 + ///\e
1.195 +
1.196 + ///\relates LpSolverBase::Expr
1.197 + ///
1.198 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1.199 + const LpSolverBase::Expr::Coeff &b)
1.200 + {
1.201 + LpSolverBase::Expr tmp(a);
1.202 + tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
1.203 + return tmp;
1.204 + }
1.205 +
1.206 + ///\e
1.207 +
1.208 + ///\relates LpSolverBase::Expr
1.209 + ///
1.210 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr::Coeff &a,
1.211 + const LpSolverBase::Expr &b)
1.212 + {
1.213 + LpSolverBase::Expr tmp(b);
1.214 + tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
1.215 + return tmp;
1.216 + }
1.217 + ///\e
1.218 +
1.219 + ///\relates LpSolverBase::Expr
1.220 + ///
1.221 + inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1.222 + const LpSolverBase::Expr::Coeff &b)
1.223 + {
1.224 + LpSolverBase::Expr tmp(a);
1.225 + tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
1.226 + return tmp;
1.227 + }
1.228 +
1.229 + ///\e
1.230 +
1.231 + ///\relates LpSolverBase::Constr
1.232 + ///
1.233 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1.234 + const LpSolverBase::Expr &f)
1.235 + {
1.236 + return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1.237 + }
1.238 +
1.239 + ///\e
1.240 +
1.241 + ///\relates LpSolverBase::Constr
1.242 + ///
1.243 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr::Coeff &e,
1.244 + const LpSolverBase::Expr &f)
1.245 + {
1.246 + return LpSolverBase::Constr(e,f);
1.247 + }
1.248 +
1.249 + ///\e
1.250 +
1.251 + ///\relates LpSolverBase::Constr
1.252 + ///
1.253 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1.254 + const LpSolverBase::Expr::Coeff &f)
1.255 + {
1.256 + return LpSolverBase::Constr(e,f);
1.257 + }
1.258 +
1.259 + ///\e
1.260 +
1.261 + ///\relates LpSolverBase::Constr
1.262 + ///
1.263 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1.264 + const LpSolverBase::Expr &f)
1.265 + {
1.266 + return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1.267 + }
1.268 +
1.269 +
1.270 + ///\e
1.271 +
1.272 + ///\relates LpSolverBase::Constr
1.273 + ///
1.274 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr::Coeff &e,
1.275 + const LpSolverBase::Expr &f)
1.276 + {
1.277 + return LpSolverBase::Constr(f,e);
1.278 + }
1.279 +
1.280 +
1.281 + ///\e
1.282 +
1.283 + ///\relates LpSolverBase::Constr
1.284 + ///
1.285 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1.286 + const LpSolverBase::Expr::Coeff &f)
1.287 + {
1.288 + return LpSolverBase::Constr(f,e);
1.289 + }
1.290 +
1.291 + ///\e
1.292 +
1.293 + ///\relates LpSolverBase::Constr
1.294 + ///
1.295 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1.296 + const LpSolverBase::Expr &f)
1.297 + {
1.298 + return LpSolverBase::Constr(0,e-f,0);
1.299 + }
1.300 +
1.301 + ///\e
1.302 +
1.303 + ///\relates LpSolverBase::Constr
1.304 + ///
1.305 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr::Coeff &n,
1.306 + const LpSolverBase::Constr&c)
1.307 + {
1.308 + LpSolverBase::Constr tmp(c);
1.309 + if(tmp.lb!=tmp.NaN) throw LogicError();
1.310 + else tmp.lb=n;
1.311 + return tmp;
1.312 + }
1.313 + ///\e
1.314 +
1.315 + ///\relates LpSolverBase::Constr
1.316 + ///
1.317 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1.318 + const LpSolverBase::Constr::Coeff &n)
1.319 + {
1.320 + LpSolverBase::Constr tmp(c);
1.321 + if(tmp.ub!=tmp.NaN) throw LogicError();
1.322 + else tmp.ub=n;
1.323 + return tmp;
1.324 + }
1.325 +
1.326 + ///\e
1.327 +
1.328 + ///\relates LpSolverBase::Constr
1.329 + ///
1.330 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr::Coeff &n,
1.331 + const LpSolverBase::Constr&c)
1.332 + {
1.333 + LpSolverBase::Constr tmp(c);
1.334 + if(tmp.ub!=tmp.NaN) throw LogicError();
1.335 + else tmp.ub=n;
1.336 + return tmp;
1.337 + }
1.338 + ///\e
1.339 +
1.340 + ///\relates LpSolverBase::Constr
1.341 + ///
1.342 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1.343 + const LpSolverBase::Constr::Coeff &n)
1.344 + {
1.345 + LpSolverBase::Constr tmp(c);
1.346 + if(tmp.lb!=tmp.NaN) throw LogicError();
1.347 + else tmp.lb=n;
1.348 + return tmp;
1.349 + }
1.350 +
1.351 +
1.352 } //namespace lemon
1.353
1.354 #endif //LEMON_LP_BASE_H