Changeset 1144:1cfabf245433 in lemon0.x for src
 Timestamp:
 02/10/05 19:53:30 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1545
 Location:
 src/work/marci/lp
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/expression.h
r1099 r1144 5 5 #include <iostream> 6 6 #include <map> 7 #include <limits> 7 8 8 9 namespace lemon { … … 120 121 return os; 121 122 } 123 124 template <typename _Col, typename _Value> 125 class LConstr { 126 // protected: 127 public: 128 Expr<_Col, _Value> expr; 129 _Value lo; 130 public: 131 LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) : 132 expr(_expr), lo(_lo) { } 133 }; 134 135 template <typename _Col, typename _Value> 136 LConstr<_Col, _Value> 137 operator<=(_Value lo, const Expr<_Col, _Value>& expr) { 138 return LConstr<_Col, _Value>(expr, lo); 139 } 140 141 template <typename _Col, typename _Value> 142 class UConstr { 143 // protected: 144 public: 145 Expr<_Col, _Value> expr; 146 _Value up; 147 public: 148 UConstr(const Expr<_Col, _Value>& _expr, _Value _up) : 149 expr(_expr), up(_up) { } 150 }; 151 152 template <typename _Col, typename _Value> 153 UConstr<_Col, _Value> 154 operator<=(const Expr<_Col, _Value>& expr, _Value up) { 155 return UConstr<_Col, _Value>(expr, up); 156 } 157 158 template <typename _Col, typename _Value> 159 class Constr { 160 // protected: 161 public: 162 Expr<_Col, _Value> expr; 163 _Value lo, up; 164 public: 165 Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) : 166 expr(_expr), lo(_lo), up(_up) { } 167 Constr(const LConstr<_Col, _Value>& _lconstr) : 168 expr(_lconstr.expr), 169 lo(_lconstr.lo), 170 up(std::numeric_limits<_Value>::infinity()) { } 171 Constr(const UConstr<_Col, _Value>& _uconstr) : 172 expr(_uconstr.expr), 173 lo(std::numeric_limits<_Value>::infinity()), 174 up(_uconstr.up) { } 175 }; 176 177 template <typename _Col, typename _Value> 178 Constr<_Col, _Value> 179 operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) { 180 return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up); 181 } 182 183 template <typename _Col, typename _Value> 184 Constr<_Col, _Value> 185 operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) { 186 return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up); 187 } 188 189 template <typename _Col, typename _Value> 190 Constr<_Col, _Value> 191 operator==(const Expr<_Col, _Value>& expr, _Value value) { 192 return Constr<_Col, _Value>(expr, value, value); 193 } 122 194 123 195 } //namespace lemon 
src/work/marci/lp/lp_solver_base.h
r1143 r1144 194 194 typedef _Value Value; 195 195 /// \e 196 typedef IterablePartition<int>::ClassIt Row It;197 /// \e 198 typedef IterablePartition<int>::ClassIt Col It;196 typedef IterablePartition<int>::ClassIt Row; 197 /// \e 198 typedef IterablePartition<int>::ClassIt Col; 199 199 public: 200 200 /// \e … … 203 203 IterablePartition<int> col_iter_map; 204 204 /// \e 205 std::vector<Row It> int_row_map;206 /// \e 207 std::vector<Col It> int_col_map;205 std::vector<Row> int_row_map; 206 /// \e 207 std::vector<Col> int_col_map; 208 208 /// \e 209 209 const int VALID_CLASS; … … 272 272 /// \e 273 273 virtual void printDualStatus(int i) = 0; 274 /// Returns the status of the slack variable assigned to row \c row _it.275 virtual int getRowStat(const Row It& row_it) = 0;274 /// Returns the status of the slack variable assigned to row \c row. 275 virtual int getRowStat(const Row& row) = 0; 276 276 /// \e 277 277 virtual void printRowStatus(int i) = 0; 278 /// Returns the status of the variable assigned to column \c col _it.279 virtual int getColStat(const Col It& col_it) = 0;278 /// Returns the status of the variable assigned to column \c col. 279 virtual int getColStat(const Col& col) = 0; 280 280 /// \e 281 281 virtual void printColStatus(int i) = 0; … … 376 376 377 377 /// \e 378 Col ItaddCol() {378 Col addCol() { 379 379 int i=_addCol(); 380 Col It col_it;381 col_iter_map.first(col _it, INVALID_CLASS);382 if (col_iter_map.valid(col _it)) { //van hasznalhato hely383 col_iter_map.set(col _it, INVALID_CLASS, VALID_CLASS);384 col_iter_map[col _it]=i;380 Col col; 381 col_iter_map.first(col, INVALID_CLASS); 382 if (col_iter_map.valid(col)) { //van hasznalhato hely 383 col_iter_map.set(col, INVALID_CLASS, VALID_CLASS); 384 col_iter_map[col]=i; 385 385 } else { //a cucc vegere kell inzertalni mert nincs szabad hely 386 col _it=col_iter_map.push_back(i, VALID_CLASS);387 } 388 int_col_map.push_back(col _it);389 return col _it;390 } 391 /// \e 392 Row ItaddRow() {386 col=col_iter_map.push_back(i, VALID_CLASS); 387 } 388 int_col_map.push_back(col); 389 return col; 390 } 391 /// \e 392 Row addRow() { 393 393 int i=_addRow(); 394 Row It row_it;395 row_iter_map.first(row _it, INVALID_CLASS);396 if (row_iter_map.valid(row _it)) { //van hasznalhato hely397 row_iter_map.set(row _it, INVALID_CLASS, VALID_CLASS);398 row_iter_map[row _it]=i;394 Row row; 395 row_iter_map.first(row, INVALID_CLASS); 396 if (row_iter_map.valid(row)) { //van hasznalhato hely 397 row_iter_map.set(row, INVALID_CLASS, VALID_CLASS); 398 row_iter_map[row]=i; 399 399 } else { //a cucc vegere kell inzertalni mert nincs szabad hely 400 row _it=row_iter_map.push_back(i, VALID_CLASS);401 } 402 int_row_map.push_back(row _it);403 return row _it;404 } 405 /// \e 406 void eraseCol(const Col It& col_it) {407 col_iter_map.set(col _it, VALID_CLASS, INVALID_CLASS);400 row=row_iter_map.push_back(i, VALID_CLASS); 401 } 402 int_row_map.push_back(row); 403 return row; 404 } 405 /// \e 406 void eraseCol(const Col& col) { 407 col_iter_map.set(col, VALID_CLASS, INVALID_CLASS); 408 408 int cols[2]; 409 cols[1]=col_iter_map[col _it];409 cols[1]=col_iter_map[col]; 410 410 _eraseCol(cols[1]); 411 col_iter_map[col _it]=0; //glpk specifikus, de kell ez??412 Col Itit;411 col_iter_map[col]=0; //glpk specifikus, de kell ez?? 412 Col it; 413 413 for (col_iter_map.first(it, VALID_CLASS); 414 414 col_iter_map.valid(it); col_iter_map.next(it)) { … … 418 418 } 419 419 /// \e 420 void eraseRow(const Row It& row_it) {421 row_iter_map.set(row _it, VALID_CLASS, INVALID_CLASS);420 void eraseRow(const Row& row) { 421 row_iter_map.set(row, VALID_CLASS, INVALID_CLASS); 422 422 int rows[2]; 423 rows[1]=row_iter_map[row _it];423 rows[1]=row_iter_map[row]; 424 424 _eraseRow(rows[1]); 425 row_iter_map[row _it]=0; //glpk specifikus, de kell ez??426 Row Itit;425 row_iter_map[row]=0; //glpk specifikus, de kell ez?? 426 Row it; 427 427 for (row_iter_map.first(it, VALID_CLASS); 428 428 row_iter_map.valid(it); row_iter_map.next(it)) { … … 432 432 } 433 433 /// \e 434 template <typename Begin, typename End> 435 void setRowCoeffs(RowIt row_it, Begin begin, End end) { 436 std::vector<std::pair<int, double> > coeffs; 437 for ( ; begin!=end; ++begin) { 438 coeffs.push_back(std:: 439 make_pair(col_iter_map[begin>first], begin>second)); 440 } 441 _setRowCoeffs(row_iter_map[row_it], coeffs); 442 } 443 /// \e 444 template <typename Begin, typename End> 445 void setColCoeffs(ColIt col_it, Begin begin, End end) { 446 std::vector<std::pair<int, double> > coeffs; 447 for ( ; begin!=end; ++begin) { 448 coeffs.push_back(std:: 449 make_pair(row_iter_map[begin>first], begin>second)); 450 } 451 _setColCoeffs(col_iter_map[col_it], coeffs); 452 } 453 /// \e 454 void setColLowerBound(ColIt col_it, _Value lo) { 455 _setColLowerBound(col_iter_map[col_it], lo); 456 } 457 /// \e 458 _Value getColLowerBound(ColIt col_it) { 459 return _getColLowerBound(col_iter_map[col_it]); 460 } 461 /// \e 462 void setColUpperBound(ColIt col_it, _Value up) { 463 _setColUpperBound(col_iter_map[col_it], up); 464 } 465 /// \e 466 _Value getColUpperBound(ColIt col_it) { 467 return _getColUpperBound(col_iter_map[col_it]); 468 } 469 /// \e 470 void setRowLowerBound(RowIt row_it, _Value lo) { 471 _setRowLowerBound(row_iter_map[row_it], lo); 472 } 473 /// \e 474 _Value getRowLowerBound(RowIt row_it) { 475 return _getRowLowerBound(row_iter_map[row_it]); 476 } 477 /// \e 478 void setRowUpperBound(RowIt row_it, _Value up) { 479 _setRowUpperBound(row_iter_map[row_it], up); 480 } 481 /// \e 482 _Value getRowUpperBound(RowIt row_it) { 483 return _getRowUpperBound(row_iter_map[row_it]); 484 } 485 /// \e 486 void setObjCoef(const ColIt& col_it, _Value obj_coef) { 487 _setObjCoef(col_iter_map[col_it], obj_coef); 488 } 489 /// \e 490 _Value getObjCoef(const ColIt& col_it) { 491 return _getObjCoef(col_iter_map[col_it]); 434 void setColLowerBound(Col col, _Value lo) { 435 _setColLowerBound(col_iter_map[col], lo); 436 } 437 /// \e 438 _Value getColLowerBound(Col col) { 439 return _getColLowerBound(col_iter_map[col]); 440 } 441 /// \e 442 void setColUpperBound(Col col, _Value up) { 443 _setColUpperBound(col_iter_map[col], up); 444 } 445 /// \e 446 _Value getColUpperBound(Col col) { 447 return _getColUpperBound(col_iter_map[col]); 448 } 449 /// \e 450 void setRowLowerBound(Row row, _Value lo) { 451 _setRowLowerBound(row_iter_map[row], lo); 452 } 453 /// \e 454 _Value getRowLowerBound(Row row) { 455 return _getRowLowerBound(row_iter_map[row]); 456 } 457 /// \e 458 void setRowUpperBound(Row row, _Value up) { 459 _setRowUpperBound(row_iter_map[row], up); 460 } 461 /// \e 462 _Value getRowUpperBound(Row row) { 463 return _getRowUpperBound(row_iter_map[row]); 464 } 465 /// \e 466 void setObjCoef(const Col& col, _Value obj_coef) { 467 _setObjCoef(col_iter_map[col], obj_coef); 468 } 469 /// \e 470 _Value getObjCoef(const Col& col) { 471 return _getObjCoef(col_iter_map[col]); 492 472 } 493 473 … … 495 475 496 476 /// \e 497 _Value getPrimal(const Col It& col_it) {498 return _getPrimal(col_iter_map[col _it]);477 _Value getPrimal(const Col& col) { 478 return _getPrimal(col_iter_map[col]); 499 479 } 500 480 … … 509 489 510 490 /// \e 511 typedef Expr<ColIt, _Value> Expression; 512 /// \e 513 typedef Expr<RowIt, _Value> DualExpression; 491 typedef Expr<Col, _Value> Expression; 492 /// \e 493 typedef Expr<Row, _Value> DualExpression; 494 /// \e 495 typedef Constr<Col, _Value> Constraint; 514 496 515 497 //MATRIX MANIPULATING FUNCTIONS 516 498 517 499 /// \e 518 void setRowCoeffs(Row It row_it, const Expression& expr) {500 void setRowCoeffs(Row row, const Expression& expr) { 519 501 std::vector<std::pair<int, _Value> > row_coeffs; 520 502 for(typename Expression::Data::const_iterator i=expr.data.begin(); … … 523 505 (col_iter_map[(*i).first], (*i).second)); 524 506 } 525 _setRowCoeffs(row_iter_map[row_it], row_coeffs); 507 _setRowCoeffs(row_iter_map[row], row_coeffs); 508 } 509 /// \e 510 void setRow(Row row, const Constraint& constr) { 511 setRowCoeffs(row, constr.expr); 512 setRowLowerBound(row, constr.lo); 513 setRowUpperBound(row, constr.up); 514 } 515 /// \e 516 Row addRow(const Constraint& constr) { 517 Row row=addRow(); 518 setRowCoeffs(row, constr.expr); 519 setRowLowerBound(row, constr.lo); 520 setRowUpperBound(row, constr.up); 521 return row; 526 522 } 527 523 /// \e 528 524 /// This routine modifies \c expr by only adding to it. 529 void getRowCoeffs(Row It row_it, Expression& expr) {525 void getRowCoeffs(Row row, Expression& expr) { 530 526 std::vector<std::pair<int, _Value> > row_coeffs; 531 _getRowCoeffs(row_iter_map[row _it], row_coeffs);527 _getRowCoeffs(row_iter_map[row], row_coeffs); 532 528 for(typename std::vector<std::pair<int, _Value> >::const_iterator 533 529 i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) { … … 536 532 } 537 533 /// \e 538 void setColCoeffs(Col It col_it, const DualExpression& expr) {534 void setColCoeffs(Col col, const DualExpression& expr) { 539 535 std::vector<std::pair<int, _Value> > col_coeffs; 540 536 for(typename DualExpression::Data::const_iterator i=expr.data.begin(); … … 543 539 (row_iter_map[(*i).first], (*i).second)); 544 540 } 545 _setColCoeffs(col_iter_map[col _it], col_coeffs);541 _setColCoeffs(col_iter_map[col], col_coeffs); 546 542 } 547 543 /// \e 548 544 /// This routine modifies \c expr by only adding to it. 549 void getColCoeffs(Col It col_it, DualExpression& expr) {545 void getColCoeffs(Col col, DualExpression& expr) { 550 546 std::vector<std::pair<int, _Value> > col_coeffs; 551 _getColCoeffs(col_iter_map[col _it], col_coeffs);547 _getColCoeffs(col_iter_map[col], col_coeffs); 552 548 for(typename std::vector<std::pair<int, _Value> >::const_iterator 553 549 i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) { … … 590 586 LPGLPK() : Parent(), 591 587 lp(lpx_create_prob()) { 592 int_row_map.push_back(Row It());593 int_col_map.push_back(Col It());588 int_row_map.push_back(Row()); 589 int_col_map.push_back(Col()); 594 590 lpx_set_int_parm(lp, LPX_K_DUAL, 1); 595 591 } … … 992 988 } 993 989 } 994 /// Returns the status of the slack variable assigned to row \c row _it.995 int getRowStat(const Row It& row_it) {996 return lpx_get_row_stat(lp, row_iter_map[row _it]);990 /// Returns the status of the slack variable assigned to row \c row. 991 int getRowStat(const Row& row) { 992 return lpx_get_row_stat(lp, row_iter_map[row]); 997 993 } 998 994 /// \e … … 1006 1002 } 1007 1003 } 1008 /// Returns the status of the variable assigned to column \c col _it.1009 int getColStat(const Col It& col_it) {1010 return lpx_get_col_stat(lp, col_iter_map[col _it]);1004 /// Returns the status of the variable assigned to column \c col. 1005 int getColStat(const Col& col) { 1006 return lpx_get_col_stat(lp, col_iter_map[col]); 1011 1007 } 1012 1008 /// \e 
src/work/marci/lp/max_flow_expression.cc
r1143 r1144 47 47 LPSolver lp; 48 48 lp.setMaximize(); 49 typedef LPSolver::Col It ColIt;50 typedef LPSolver::Row It RowIt;51 typedef Graph::EdgeMap<Col It> EdgeIndexMap;52 typedef Graph::NodeMap<Row It> NodeIndexMap;49 typedef LPSolver::Col Col; 50 typedef LPSolver::Row Row; 51 typedef Graph::EdgeMap<Col> EdgeIndexMap; 52 typedef Graph::NodeMap<Row> NodeIndexMap; 53 53 EdgeIndexMap edge_index_map(g); 54 54 NodeIndexMap node_index_map(g); … … 57 57 // nonnegativity of flow and capacity function 58 58 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 59 Col It col_it=lp.addCol();60 edge_index_map.set(e, col _it);59 Col col=lp.addCol(); 60 edge_index_map.set(e, col); 61 61 // interesting property in GLPK: 62 62 // if you change the order of the following two lines, the 63 63 // two runs of GLPK are extremely different 64 lp.setColLowerBound(col _it, 0);65 lp.setColUpperBound(col _it, cap[e]);64 lp.setColLowerBound(col, 0); 65 lp.setColUpperBound(col, cap[e]); 66 66 } 67 67 … … 78 78 // flow conservation constraints 79 79 if ((n!=s) && (n!=t)) { 80 RowIt row_it=lp.addRow(); 81 node_index_map.set(n, row_it); 82 lp.setRowCoeffs(row_it, expr); 83 lp.setRowLowerBound(row_it, 0.0); 84 lp.setRowUpperBound(row_it, 0.0); 85 // cout << expr << endl; 86 // { 87 // LPSolver::Expression expr; 88 // lp.getRowCoeffs(node_index_map[n], expr); 89 // cout << expr << endl; 90 // } 80 node_index_map.set(n, lp.addRow(expr == 0.0)); 91 81 } 92 82 } 93 83 lp.solveSimplex(); 94 // cout << "num of nodes: " << countNodes(g) << endl;95 // cout << "num of edges: " << countEdges(g) << endl;96 // cout << "num of rows: " << lp.rowNum() << endl;97 // cout << "num of rows: " << lp.int_row_map.size() << endl;98 // for (int i=0; i<lp.int_row_map.size(); ++i) {99 // cout << lp.int_row_map[i] << " " << endl;100 // }101 // cout << "num of columns: " << lp.colNum() << endl;102 // cout << "num of columns: " << lp.int_col_map.size() << endl;103 // for (int i=0; i<lp.int_col_map.size(); ++i) {104 // cout << lp.int_col_map[i] << " " << endl;105 // }106 84 cout << "elapsed time: " << ts << endl; 107 // Graph::NodeIt n(g);108 // ++n;109 // for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {110 // cout << edge_index_map[e] << endl;111 // }112 // for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {113 // cout << edge_index_map[e] << endl;114 // }115 // LPSolver::DualExpression expr;116 // lp.getRowCoeffs(node_index_map[n], expr);117 // cout << expr << endl;118 85 }
Note: See TracChangeset
for help on using the changeset viewer.