1.1 --- a/src/work/marci/lp/expression.h Tue Feb 08 17:47:19 2005 +0000
1.2 +++ b/src/work/marci/lp/expression.h Thu Feb 10 18:53:30 2005 +0000
1.3 @@ -4,6 +4,7 @@
1.4
1.5 #include <iostream>
1.6 #include <map>
1.7 +#include <limits>
1.8
1.9 namespace lemon {
1.10
1.11 @@ -119,6 +120,77 @@
1.12 }
1.13 return os;
1.14 }
1.15 +
1.16 + template <typename _Col, typename _Value>
1.17 + class LConstr {
1.18 + // protected:
1.19 + public:
1.20 + Expr<_Col, _Value> expr;
1.21 + _Value lo;
1.22 + public:
1.23 + LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) :
1.24 + expr(_expr), lo(_lo) { }
1.25 + };
1.26 +
1.27 + template <typename _Col, typename _Value>
1.28 + LConstr<_Col, _Value>
1.29 + operator<=(_Value lo, const Expr<_Col, _Value>& expr) {
1.30 + return LConstr<_Col, _Value>(expr, lo);
1.31 + }
1.32 +
1.33 + template <typename _Col, typename _Value>
1.34 + class UConstr {
1.35 + // protected:
1.36 + public:
1.37 + Expr<_Col, _Value> expr;
1.38 + _Value up;
1.39 + public:
1.40 + UConstr(const Expr<_Col, _Value>& _expr, _Value _up) :
1.41 + expr(_expr), up(_up) { }
1.42 + };
1.43 +
1.44 + template <typename _Col, typename _Value>
1.45 + UConstr<_Col, _Value>
1.46 + operator<=(const Expr<_Col, _Value>& expr, _Value up) {
1.47 + return UConstr<_Col, _Value>(expr, up);
1.48 + }
1.49 +
1.50 + template <typename _Col, typename _Value>
1.51 + class Constr {
1.52 + // protected:
1.53 + public:
1.54 + Expr<_Col, _Value> expr;
1.55 + _Value lo, up;
1.56 + public:
1.57 + Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) :
1.58 + expr(_expr), lo(_lo), up(_up) { }
1.59 + Constr(const LConstr<_Col, _Value>& _lconstr) :
1.60 + expr(_lconstr.expr),
1.61 + lo(_lconstr.lo),
1.62 + up(std::numeric_limits<_Value>::infinity()) { }
1.63 + Constr(const UConstr<_Col, _Value>& _uconstr) :
1.64 + expr(_uconstr.expr),
1.65 + lo(-std::numeric_limits<_Value>::infinity()),
1.66 + up(_uconstr.up) { }
1.67 + };
1.68 +
1.69 + template <typename _Col, typename _Value>
1.70 + Constr<_Col, _Value>
1.71 + operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {
1.72 + return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);
1.73 + }
1.74 +
1.75 + template <typename _Col, typename _Value>
1.76 + Constr<_Col, _Value>
1.77 + operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {
1.78 + return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);
1.79 + }
1.80 +
1.81 + template <typename _Col, typename _Value>
1.82 + Constr<_Col, _Value>
1.83 + operator==(const Expr<_Col, _Value>& expr, _Value value) {
1.84 + return Constr<_Col, _Value>(expr, value, value);
1.85 + }
1.86
1.87 } //namespace lemon
1.88
2.1 --- a/src/work/marci/lp/lp_solver_base.h Tue Feb 08 17:47:19 2005 +0000
2.2 +++ b/src/work/marci/lp/lp_solver_base.h Thu Feb 10 18:53:30 2005 +0000
2.3 @@ -193,18 +193,18 @@
2.4 /// \e
2.5 typedef _Value Value;
2.6 /// \e
2.7 - typedef IterablePartition<int>::ClassIt RowIt;
2.8 + typedef IterablePartition<int>::ClassIt Row;
2.9 /// \e
2.10 - typedef IterablePartition<int>::ClassIt ColIt;
2.11 + typedef IterablePartition<int>::ClassIt Col;
2.12 public:
2.13 /// \e
2.14 IterablePartition<int> row_iter_map;
2.15 /// \e
2.16 IterablePartition<int> col_iter_map;
2.17 /// \e
2.18 - std::vector<RowIt> int_row_map;
2.19 + std::vector<Row> int_row_map;
2.20 /// \e
2.21 - std::vector<ColIt> int_col_map;
2.22 + std::vector<Col> int_col_map;
2.23 /// \e
2.24 const int VALID_CLASS;
2.25 /// \e
2.26 @@ -271,12 +271,12 @@
2.27 virtual int getDualStatus() = 0;
2.28 /// \e
2.29 virtual void printDualStatus(int i) = 0;
2.30 - /// Returns the status of the slack variable assigned to row \c row_it.
2.31 - virtual int getRowStat(const RowIt& row_it) = 0;
2.32 + /// Returns the status of the slack variable assigned to row \c row.
2.33 + virtual int getRowStat(const Row& row) = 0;
2.34 /// \e
2.35 virtual void printRowStatus(int i) = 0;
2.36 - /// Returns the status of the variable assigned to column \c col_it.
2.37 - virtual int getColStat(const ColIt& col_it) = 0;
2.38 + /// Returns the status of the variable assigned to column \c col.
2.39 + virtual int getColStat(const Col& col) = 0;
2.40 /// \e
2.41 virtual void printColStatus(int i) = 0;
2.42
2.43 @@ -375,41 +375,41 @@
2.44 //MATRIX MANIPULATING FUNCTIONS
2.45
2.46 /// \e
2.47 - ColIt addCol() {
2.48 + Col addCol() {
2.49 int i=_addCol();
2.50 - ColIt col_it;
2.51 - col_iter_map.first(col_it, INVALID_CLASS);
2.52 - if (col_iter_map.valid(col_it)) { //van hasznalhato hely
2.53 - col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
2.54 - col_iter_map[col_it]=i;
2.55 + Col col;
2.56 + col_iter_map.first(col, INVALID_CLASS);
2.57 + if (col_iter_map.valid(col)) { //van hasznalhato hely
2.58 + col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
2.59 + col_iter_map[col]=i;
2.60 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
2.61 - col_it=col_iter_map.push_back(i, VALID_CLASS);
2.62 + col=col_iter_map.push_back(i, VALID_CLASS);
2.63 }
2.64 - int_col_map.push_back(col_it);
2.65 - return col_it;
2.66 + int_col_map.push_back(col);
2.67 + return col;
2.68 }
2.69 /// \e
2.70 - RowIt addRow() {
2.71 + Row addRow() {
2.72 int i=_addRow();
2.73 - RowIt row_it;
2.74 - row_iter_map.first(row_it, INVALID_CLASS);
2.75 - if (row_iter_map.valid(row_it)) { //van hasznalhato hely
2.76 - row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
2.77 - row_iter_map[row_it]=i;
2.78 + Row row;
2.79 + row_iter_map.first(row, INVALID_CLASS);
2.80 + if (row_iter_map.valid(row)) { //van hasznalhato hely
2.81 + row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
2.82 + row_iter_map[row]=i;
2.83 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
2.84 - row_it=row_iter_map.push_back(i, VALID_CLASS);
2.85 + row=row_iter_map.push_back(i, VALID_CLASS);
2.86 }
2.87 - int_row_map.push_back(row_it);
2.88 - return row_it;
2.89 + int_row_map.push_back(row);
2.90 + return row;
2.91 }
2.92 /// \e
2.93 - void eraseCol(const ColIt& col_it) {
2.94 - col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
2.95 + void eraseCol(const Col& col) {
2.96 + col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
2.97 int cols[2];
2.98 - cols[1]=col_iter_map[col_it];
2.99 + cols[1]=col_iter_map[col];
2.100 _eraseCol(cols[1]);
2.101 - col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
2.102 - ColIt it;
2.103 + col_iter_map[col]=0; //glpk specifikus, de kell ez??
2.104 + Col it;
2.105 for (col_iter_map.first(it, VALID_CLASS);
2.106 col_iter_map.valid(it); col_iter_map.next(it)) {
2.107 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
2.108 @@ -417,13 +417,13 @@
2.109 int_col_map.erase(int_col_map.begin()+cols[1]);
2.110 }
2.111 /// \e
2.112 - void eraseRow(const RowIt& row_it) {
2.113 - row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
2.114 + void eraseRow(const Row& row) {
2.115 + row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
2.116 int rows[2];
2.117 - rows[1]=row_iter_map[row_it];
2.118 + rows[1]=row_iter_map[row];
2.119 _eraseRow(rows[1]);
2.120 - row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
2.121 - RowIt it;
2.122 + row_iter_map[row]=0; //glpk specifikus, de kell ez??
2.123 + Row it;
2.124 for (row_iter_map.first(it, VALID_CLASS);
2.125 row_iter_map.valid(it); row_iter_map.next(it)) {
2.126 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
2.127 @@ -431,71 +431,51 @@
2.128 int_row_map.erase(int_row_map.begin()+rows[1]);
2.129 }
2.130 /// \e
2.131 - template <typename Begin, typename End>
2.132 - void setRowCoeffs(RowIt row_it, Begin begin, End end) {
2.133 - std::vector<std::pair<int, double> > coeffs;
2.134 - for ( ; begin!=end; ++begin) {
2.135 - coeffs.push_back(std::
2.136 - make_pair(col_iter_map[begin->first], begin->second));
2.137 - }
2.138 - _setRowCoeffs(row_iter_map[row_it], coeffs);
2.139 + void setColLowerBound(Col col, _Value lo) {
2.140 + _setColLowerBound(col_iter_map[col], lo);
2.141 }
2.142 /// \e
2.143 - template <typename Begin, typename End>
2.144 - void setColCoeffs(ColIt col_it, Begin begin, End end) {
2.145 - std::vector<std::pair<int, double> > coeffs;
2.146 - for ( ; begin!=end; ++begin) {
2.147 - coeffs.push_back(std::
2.148 - make_pair(row_iter_map[begin->first], begin->second));
2.149 - }
2.150 - _setColCoeffs(col_iter_map[col_it], coeffs);
2.151 + _Value getColLowerBound(Col col) {
2.152 + return _getColLowerBound(col_iter_map[col]);
2.153 }
2.154 /// \e
2.155 - void setColLowerBound(ColIt col_it, _Value lo) {
2.156 - _setColLowerBound(col_iter_map[col_it], lo);
2.157 + void setColUpperBound(Col col, _Value up) {
2.158 + _setColUpperBound(col_iter_map[col], up);
2.159 }
2.160 /// \e
2.161 - _Value getColLowerBound(ColIt col_it) {
2.162 - return _getColLowerBound(col_iter_map[col_it]);
2.163 + _Value getColUpperBound(Col col) {
2.164 + return _getColUpperBound(col_iter_map[col]);
2.165 }
2.166 /// \e
2.167 - void setColUpperBound(ColIt col_it, _Value up) {
2.168 - _setColUpperBound(col_iter_map[col_it], up);
2.169 + void setRowLowerBound(Row row, _Value lo) {
2.170 + _setRowLowerBound(row_iter_map[row], lo);
2.171 }
2.172 /// \e
2.173 - _Value getColUpperBound(ColIt col_it) {
2.174 - return _getColUpperBound(col_iter_map[col_it]);
2.175 + _Value getRowLowerBound(Row row) {
2.176 + return _getRowLowerBound(row_iter_map[row]);
2.177 }
2.178 /// \e
2.179 - void setRowLowerBound(RowIt row_it, _Value lo) {
2.180 - _setRowLowerBound(row_iter_map[row_it], lo);
2.181 + void setRowUpperBound(Row row, _Value up) {
2.182 + _setRowUpperBound(row_iter_map[row], up);
2.183 }
2.184 /// \e
2.185 - _Value getRowLowerBound(RowIt row_it) {
2.186 - return _getRowLowerBound(row_iter_map[row_it]);
2.187 + _Value getRowUpperBound(Row row) {
2.188 + return _getRowUpperBound(row_iter_map[row]);
2.189 }
2.190 /// \e
2.191 - void setRowUpperBound(RowIt row_it, _Value up) {
2.192 - _setRowUpperBound(row_iter_map[row_it], up);
2.193 + void setObjCoef(const Col& col, _Value obj_coef) {
2.194 + _setObjCoef(col_iter_map[col], obj_coef);
2.195 }
2.196 /// \e
2.197 - _Value getRowUpperBound(RowIt row_it) {
2.198 - return _getRowUpperBound(row_iter_map[row_it]);
2.199 - }
2.200 - /// \e
2.201 - void setObjCoef(const ColIt& col_it, _Value obj_coef) {
2.202 - _setObjCoef(col_iter_map[col_it], obj_coef);
2.203 - }
2.204 - /// \e
2.205 - _Value getObjCoef(const ColIt& col_it) {
2.206 - return _getObjCoef(col_iter_map[col_it]);
2.207 + _Value getObjCoef(const Col& col) {
2.208 + return _getObjCoef(col_iter_map[col]);
2.209 }
2.210
2.211 //SOLUTION RETRIEVING FUNCTIONS
2.212
2.213 /// \e
2.214 - _Value getPrimal(const ColIt& col_it) {
2.215 - return _getPrimal(col_iter_map[col_it]);
2.216 + _Value getPrimal(const Col& col) {
2.217 + return _getPrimal(col_iter_map[col]);
2.218 }
2.219
2.220 //@}
2.221 @@ -508,47 +488,63 @@
2.222 //EXPRESSION TYPES
2.223
2.224 /// \e
2.225 - typedef Expr<ColIt, _Value> Expression;
2.226 + typedef Expr<Col, _Value> Expression;
2.227 /// \e
2.228 - typedef Expr<RowIt, _Value> DualExpression;
2.229 + typedef Expr<Row, _Value> DualExpression;
2.230 + /// \e
2.231 + typedef Constr<Col, _Value> Constraint;
2.232
2.233 //MATRIX MANIPULATING FUNCTIONS
2.234
2.235 /// \e
2.236 - void setRowCoeffs(RowIt row_it, const Expression& expr) {
2.237 + void setRowCoeffs(Row row, const Expression& expr) {
2.238 std::vector<std::pair<int, _Value> > row_coeffs;
2.239 for(typename Expression::Data::const_iterator i=expr.data.begin();
2.240 i!=expr.data.end(); ++i) {
2.241 row_coeffs.push_back(std::make_pair
2.242 (col_iter_map[(*i).first], (*i).second));
2.243 }
2.244 - _setRowCoeffs(row_iter_map[row_it], row_coeffs);
2.245 + _setRowCoeffs(row_iter_map[row], row_coeffs);
2.246 + }
2.247 + /// \e
2.248 + void setRow(Row row, const Constraint& constr) {
2.249 + setRowCoeffs(row, constr.expr);
2.250 + setRowLowerBound(row, constr.lo);
2.251 + setRowUpperBound(row, constr.up);
2.252 + }
2.253 + /// \e
2.254 + Row addRow(const Constraint& constr) {
2.255 + Row row=addRow();
2.256 + setRowCoeffs(row, constr.expr);
2.257 + setRowLowerBound(row, constr.lo);
2.258 + setRowUpperBound(row, constr.up);
2.259 + return row;
2.260 }
2.261 /// \e
2.262 /// This routine modifies \c expr by only adding to it.
2.263 - void getRowCoeffs(RowIt row_it, Expression& expr) {
2.264 + void getRowCoeffs(Row row, Expression& expr) {
2.265 std::vector<std::pair<int, _Value> > row_coeffs;
2.266 - _getRowCoeffs(row_iter_map[row_it], row_coeffs);
2.267 + _getRowCoeffs(row_iter_map[row], row_coeffs);
2.268 for(typename std::vector<std::pair<int, _Value> >::const_iterator
2.269 i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
2.270 expr+= (*i).second*int_col_map[(*i).first];
2.271 }
2.272 }
2.273 /// \e
2.274 - void setColCoeffs(ColIt col_it, const DualExpression& expr) {
2.275 + void setColCoeffs(Col col, const DualExpression& expr) {
2.276 std::vector<std::pair<int, _Value> > col_coeffs;
2.277 for(typename DualExpression::Data::const_iterator i=expr.data.begin();
2.278 i!=expr.data.end(); ++i) {
2.279 col_coeffs.push_back(std::make_pair
2.280 (row_iter_map[(*i).first], (*i).second));
2.281 }
2.282 - _setColCoeffs(col_iter_map[col_it], col_coeffs);
2.283 + _setColCoeffs(col_iter_map[col], col_coeffs);
2.284 }
2.285 /// \e
2.286 /// This routine modifies \c expr by only adding to it.
2.287 - void getColCoeffs(ColIt col_it, DualExpression& expr) {
2.288 + void getColCoeffs(Col col, DualExpression& expr) {
2.289 std::vector<std::pair<int, _Value> > col_coeffs;
2.290 - _getColCoeffs(col_iter_map[col_it], col_coeffs);
2.291 + _getColCoeffs(col_iter_map[col], col_coeffs);
2.292 for(typename std::vector<std::pair<int, _Value> >::const_iterator
2.293 i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
2.294 expr+= (*i).second*int_row_map[(*i).first];
2.295 @@ -589,8 +585,8 @@
2.296 /// \e
2.297 LPGLPK() : Parent(),
2.298 lp(lpx_create_prob()) {
2.299 - int_row_map.push_back(RowIt());
2.300 - int_col_map.push_back(ColIt());
2.301 + int_row_map.push_back(Row());
2.302 + int_col_map.push_back(Col());
2.303 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
2.304 }
2.305 /// \e
2.306 @@ -991,9 +987,9 @@
2.307 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
2.308 }
2.309 }
2.310 - /// Returns the status of the slack variable assigned to row \c row_it.
2.311 - int getRowStat(const RowIt& row_it) {
2.312 - return lpx_get_row_stat(lp, row_iter_map[row_it]);
2.313 + /// Returns the status of the slack variable assigned to row \c row.
2.314 + int getRowStat(const Row& row) {
2.315 + return lpx_get_row_stat(lp, row_iter_map[row]);
2.316 }
2.317 /// \e
2.318 void printRowStatus(int i) {
2.319 @@ -1005,9 +1001,9 @@
2.320 case LPX_NS: cout << "LPX_NS" << endl; break;
2.321 }
2.322 }
2.323 - /// Returns the status of the variable assigned to column \c col_it.
2.324 - int getColStat(const ColIt& col_it) {
2.325 - return lpx_get_col_stat(lp, col_iter_map[col_it]);
2.326 + /// Returns the status of the variable assigned to column \c col.
2.327 + int getColStat(const Col& col) {
2.328 + return lpx_get_col_stat(lp, col_iter_map[col]);
2.329 }
2.330 /// \e
2.331 void printColStatus(int i) {
3.1 --- a/src/work/marci/lp/max_flow_expression.cc Tue Feb 08 17:47:19 2005 +0000
3.2 +++ b/src/work/marci/lp/max_flow_expression.cc Thu Feb 10 18:53:30 2005 +0000
3.3 @@ -46,23 +46,23 @@
3.4 typedef LPGLPK LPSolver;
3.5 LPSolver lp;
3.6 lp.setMaximize();
3.7 - typedef LPSolver::ColIt ColIt;
3.8 - typedef LPSolver::RowIt RowIt;
3.9 - typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
3.10 - typedef Graph::NodeMap<RowIt> NodeIndexMap;
3.11 + typedef LPSolver::Col Col;
3.12 + typedef LPSolver::Row Row;
3.13 + typedef Graph::EdgeMap<Col> EdgeIndexMap;
3.14 + typedef Graph::NodeMap<Row> NodeIndexMap;
3.15 EdgeIndexMap edge_index_map(g);
3.16 NodeIndexMap node_index_map(g);
3.17 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
3.18
3.19 // nonnegativity of flow and capacity function
3.20 for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.21 - ColIt col_it=lp.addCol();
3.22 - edge_index_map.set(e, col_it);
3.23 + Col col=lp.addCol();
3.24 + edge_index_map.set(e, col);
3.25 // interesting property in GLPK:
3.26 // if you change the order of the following two lines, the
3.27 // two runs of GLPK are extremely different
3.28 - lp.setColLowerBound(col_it, 0);
3.29 - lp.setColUpperBound(col_it, cap[e]);
3.30 + lp.setColLowerBound(col, 0);
3.31 + lp.setColUpperBound(col, cap[e]);
3.32 }
3.33
3.34 for (Graph::NodeIt n(g); n!=INVALID; ++n) {
3.35 @@ -77,42 +77,9 @@
3.36 }
3.37 // flow conservation constraints
3.38 if ((n!=s) && (n!=t)) {
3.39 - RowIt row_it=lp.addRow();
3.40 - node_index_map.set(n, row_it);
3.41 - lp.setRowCoeffs(row_it, expr);
3.42 - lp.setRowLowerBound(row_it, 0.0);
3.43 - lp.setRowUpperBound(row_it, 0.0);
3.44 -// cout << expr << endl;
3.45 -// {
3.46 -// LPSolver::Expression expr;
3.47 -// lp.getRowCoeffs(node_index_map[n], expr);
3.48 -// cout << expr << endl;
3.49 -// }
3.50 + node_index_map.set(n, lp.addRow(expr == 0.0));
3.51 }
3.52 }
3.53 lp.solveSimplex();
3.54 -// cout << "num of nodes: " << countNodes(g) << endl;
3.55 -// cout << "num of edges: " << countEdges(g) << endl;
3.56 -// cout << "num of rows: " << lp.rowNum() << endl;
3.57 -// cout << "num of rows: " << lp.int_row_map.size() << endl;
3.58 -// for (int i=0; i<lp.int_row_map.size(); ++i) {
3.59 -// cout << lp.int_row_map[i] << " " << endl;
3.60 -// }
3.61 -// cout << "num of columns: " << lp.colNum() << endl;
3.62 -// cout << "num of columns: " << lp.int_col_map.size() << endl;
3.63 -// for (int i=0; i<lp.int_col_map.size(); ++i) {
3.64 -// cout << lp.int_col_map[i] << " " << endl;
3.65 -// }
3.66 cout << "elapsed time: " << ts << endl;
3.67 -// Graph::NodeIt n(g);
3.68 -// ++n;
3.69 -// for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
3.70 -// cout << edge_index_map[e] << endl;
3.71 -// }
3.72 -// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
3.73 -// cout << edge_index_map[e] << endl;
3.74 -// }
3.75 -// LPSolver::DualExpression expr;
3.76 -// lp.getRowCoeffs(node_index_map[n], expr);
3.77 -// cout << expr << endl;
3.78 }