Changeset 1111:88ade201ffc6 in lemon0.x
 Timestamp:
 02/01/05 13:53:30 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1510
 Location:
 src/work/marci/lp
 Files:

 1 deleted
 1 edited
 1 moved
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/lp_solver_base.h
r1110 r1111 25 25 #include <utility> 26 26 27 //#include <sage_graph.h>28 27 //#include <lemon/list_graph.h> 29 //#include <lemon/graph_wrapper.h>30 28 #include <lemon/invalid.h> 31 29 #include <expression.h> … … 174 172 175 173 /*! \e 176 177 \todo A[x,y]t cserel. Jobboldal, baloldal csere. 178 \todo LEKERDEZESEK!!! 179 \todo DOKSI!!!! Doxygen group!!! 180 181 */ 174 \todo A[x,y]t cserel. Jobboldal, baloldal csere. 175 \todo LEKERDEZESEK!!! 176 \todo DOKSI!!!! Doxygen group!!! 177 The aim of this class is to give a general surface to different 178 solvers, i.e. it makes possible to write algorithms using LP's, 179 in which the solver can be changed to an other one easily. 180 */ 182 181 template <typename _Value> 183 182 class LPSolverBase { … … 220 219 protected: 221 220 /// \e 221 virtual int _addCol() = 0; 222 /// \e 222 223 virtual int _addRow() = 0; 223 224 /// \e 224 virtual int _addCol() = 0; 225 virtual void _eraseCol(int i) = 0; 226 /// \e 227 virtual void _eraseRow(int i) = 0; 225 228 /// \e 226 229 virtual void _setRowCoeffs(int i, … … 229 232 virtual void _setColCoeffs(int i, 230 233 const std::vector<std::pair<int, _Value> >& coeffs) = 0; 231 /// \e232 virtual void _eraseCol(int i) = 0;233 /// \e234 virtual void _eraseRow(int i) = 0;235 234 public: 236 235 /// \e … … 243 242 virtual void _setColLowerBound(int i, _Value value) = 0; 244 243 /// \e 244 /// The lower bound of a variable (column) is an 245 /// extended number of type _Value, i.e. a finite number of type 246 /// _Value or INF. 247 virtual _Value _getColLowerBound(int i) = 0; 248 /// \e 245 249 /// The upper bound of a variable (column) have to be given by an 246 250 /// extended number of type _Value, i.e. a finite number of type … … 248 252 virtual void _setColUpperBound(int i, _Value value) = 0; 249 253 /// \e 250 /// The lower bound of a variable (column) is an251 /// extended number of type _Value, i.e. a finite number of type252 /// _Value or INF.253 virtual _Value _getColLowerBound(int i) = 0;254 /// \e255 254 /// The upper bound of a variable (column) is an 256 255 /// extended number of type _Value, i.e. a finite number of type … … 258 257 virtual _Value _getColUpperBound(int i) = 0; 259 258 /// \e 260 virtual void _setColBounds(int i, Bound bound, 261 _Value lo, _Value up) = 0; 262 /// \e 263 virtual void _setRowBounds(int i, Bound bound, 264 _Value lo, _Value up) = 0; 259 /// The lower bound of a linear expression (row) have to be given by an 260 /// extended number of type _Value, i.e. a finite number of type 261 /// _Value or INF. 262 virtual void _setRowLowerBound(int i, _Value value) = 0; 263 /// \e 264 /// The lower bound of a linear expression (row) is an 265 /// extended number of type _Value, i.e. a finite number of type 266 /// _Value or INF. 267 virtual _Value _getRowLowerBound(int i) = 0; 268 /// \e 269 /// The upper bound of a linear expression (row) have to be given by an 270 /// extended number of type _Value, i.e. a finite number of type 271 /// _Value or INF. 272 virtual void _setRowUpperBound(int i, _Value value) = 0; 273 /// \e 274 /// The upper bound of a linear expression (row) is an 275 /// extended number of type _Value, i.e. a finite number of type 276 /// _Value or INF. 277 virtual _Value _getRowUpperBound(int i) = 0; 265 278 /// \e 266 279 virtual void _setObjCoef(int i, _Value obj_coef) = 0; … … 271 284 272 285 protected: 286 /// \e 273 287 virtual _Value _getPrimal(int i) = 0; 274 288 … … 276 290 277 291 public: 292 /// \e 293 ColIt addCol() { 294 int i=_addCol(); 295 ColIt col_it; 296 col_iter_map.first(col_it, INVALID_CLASS); 297 if (col_iter_map.valid(col_it)) { //van hasznalhato hely 298 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS); 299 col_iter_map[col_it]=i; 300 } else { //a cucc vegere kell inzertalni mert nincs szabad hely 301 col_it=col_iter_map.push_back(i, VALID_CLASS); 302 } 303 return col_it; 304 } 278 305 /// \e 279 306 RowIt addRow() { … … 288 315 } 289 316 return row_it; 290 }291 /// \e292 ColIt addCol() {293 int i=_addCol();294 ColIt col_it;295 col_iter_map.first(col_it, INVALID_CLASS);296 if (col_iter_map.valid(col_it)) { //van hasznalhato hely297 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);298 col_iter_map[col_it]=i;299 } else { //a cucc vegere kell inzertalni mert nincs szabad hely300 col_it=col_iter_map.push_back(i, VALID_CLASS);301 }302 return col_it;303 }304 /// \e305 template <typename Begin, typename End>306 void setRowCoeffs(RowIt row_it, Begin begin, End end) {307 std::vector<std::pair<int, double> > coeffs;308 for ( ; begin!=end; ++begin) {309 coeffs.push_back(std::310 make_pair(col_iter_map[begin>first], begin>second));311 }312 _setRowCoeffs(row_iter_map[row_it], coeffs);313 }314 /// \e315 template <typename Begin, typename End>316 void setColCoeffs(ColIt col_it, Begin begin, End end) {317 std::vector<std::pair<int, double> > coeffs;318 for ( ; begin!=end; ++begin) {319 coeffs.push_back(std::320 make_pair(row_iter_map[begin>first], begin>second));321 }322 _setColCoeffs(col_iter_map[col_it], coeffs);323 317 } 324 318 /// \e … … 349 343 } 350 344 /// \e 345 template <typename Begin, typename End> 346 void setRowCoeffs(RowIt row_it, Begin begin, End end) { 347 std::vector<std::pair<int, double> > coeffs; 348 for ( ; begin!=end; ++begin) { 349 coeffs.push_back(std:: 350 make_pair(col_iter_map[begin>first], begin>second)); 351 } 352 _setRowCoeffs(row_iter_map[row_it], coeffs); 353 } 354 /// \e 355 template <typename Begin, typename End> 356 void setColCoeffs(ColIt col_it, Begin begin, End end) { 357 std::vector<std::pair<int, double> > coeffs; 358 for ( ; begin!=end; ++begin) { 359 coeffs.push_back(std:: 360 make_pair(row_iter_map[begin>first], begin>second)); 361 } 362 _setColCoeffs(col_iter_map[col_it], coeffs); 363 } 364 /// \e 351 365 void setColLowerBound(ColIt col_it, _Value lo) { 352 366 _setColLowerBound(col_iter_map[col_it], lo); 353 367 } 354 368 /// \e 369 _Value getColLowerBound(ColIt col_it) { 370 return _getColLowerBound(col_iter_map[col_it]); 371 } 372 /// \e 355 373 void setColUpperBound(ColIt col_it, _Value up) { 356 374 _setColUpperBound(col_iter_map[col_it], up); 357 375 } 358 376 /// \e 359 _Value getColLowerBound(ColIt col_it) {360 return _getColLowerBound(col_iter_map[col_it]);361 }362 /// \e363 377 _Value getColUpperBound(ColIt col_it) { 364 378 return _getColUpperBound(col_iter_map[col_it]); 365 379 } 366 380 /// \e 367 void setColBounds(const ColIt& col_it, Bound bound, 368 _Value lo, _Value up) { 369 _setColBounds(col_iter_map[col_it], bound, lo, up); 370 } 371 /// \e 372 void setRowBounds(const RowIt& row_it, Bound bound, 373 _Value lo, _Value up) { 374 _setRowBounds(row_iter_map[row_it], bound, lo, up); 381 void setRowLowerBound(RowIt row_it, _Value lo) { 382 _setRowLowerBound(row_iter_map[row_it], lo); 383 } 384 /// \e 385 _Value getRowLowerBound(RowIt row_it) { 386 return _getRowLowerBound(row_iter_map[row_it]); 387 } 388 /// \e 389 void setRowUpperBound(RowIt row_it, _Value up) { 390 _setRowUpperBound(row_iter_map[row_it], up); 391 } 392 /// \e 393 _Value getRowUpperBound(RowIt row_it) { 394 return _getRowUpperBound(row_iter_map[row_it]); 375 395 } 376 396 /// \e … … 416 436 } 417 437 } 438 418 439 //SOLVER FUNCTIONS 419 440 … … 429 450 430 451 public: 452 453 /// \e 431 454 _Value getPrimal(const ColIt& col_it) { 432 455 return _getPrimal(col_iter_map[col_it]); … … 467 490 468 491 469 /// \brief Wrapper s for LP solvers492 /// \brief Wrapper for GLPK solver 470 493 /// 471 /// This class implements a lemon wrapper for glpk. 472 /// Later other LPsolvers will be wrapped into lemon. 473 /// The aim of this class is to give a general surface to different 474 /// solvers, i.e. it makes possible to write algorithms using LP's, 475 /// in which the solver can be changed to an other one easily. 494 /// This class implements a lemon wrapper for GLPK. 476 495 class LPGLPK : public LPSolverBase<double> { 477 496 public: … … 595 614 break; 596 615 case LPX_UP: 597 case LPX_DB:598 case LPX_FX:599 if (lo==up)600 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);601 else602 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);603 break;604 default: ;605 //FIXME error606 }607 }608 }609 virtual void _setColUpperBound(int i, double up) {610 if (up==INF) {611 //FIXME error612 }613 int b=lpx_get_col_type(lp, i);614 double lo=lpx_get_col_lb(lp, i);615 if (up==INF) {616 switch (b) {617 case LPX_FR:618 case LPX_LO:619 break;620 case LPX_UP:621 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);622 break;623 case LPX_DB:624 case LPX_FX:625 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);626 break;627 default: ;628 //FIXME error629 }630 } else {631 switch (b) {632 case LPX_FR:633 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);634 case LPX_LO:635 if (lo==up)636 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);637 else638 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);639 break;640 case LPX_UP:641 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);642 break;643 616 case LPX_DB: 644 617 case LPX_FX: … … 670 643 } 671 644 } 645 virtual void _setColUpperBound(int i, double up) { 646 if (up==INF) { 647 //FIXME error 648 } 649 int b=lpx_get_col_type(lp, i); 650 double lo=lpx_get_col_lb(lp, i); 651 if (up==INF) { 652 switch (b) { 653 case LPX_FR: 654 case LPX_LO: 655 break; 656 case LPX_UP: 657 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); 658 break; 659 case LPX_DB: 660 case LPX_FX: 661 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); 662 break; 663 default: ; 664 //FIXME error 665 } 666 } else { 667 switch (b) { 668 case LPX_FR: 669 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); 670 case LPX_LO: 671 if (lo==up) 672 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); 673 else 674 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); 675 break; 676 case LPX_UP: 677 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); 678 break; 679 case LPX_DB: 680 case LPX_FX: 681 if (lo==up) 682 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); 683 else 684 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); 685 break; 686 default: ; 687 //FIXME error 688 } 689 } 690 } 672 691 virtual double _getColUpperBound(int i) { 673 692 int b=lpx_get_col_type(lp, i); … … 685 704 } 686 705 } 687 virtual void _setColBounds(int i, Bound bound, 688 double lo, double up) { 689 switch (bound) { 690 case FREE: 691 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); 692 break; 693 case LOWER: 694 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); 695 break; 696 case UPPER: 697 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); 698 break; 699 case DOUBLE: 700 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); 701 break; 702 case FIXED: 703 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); 704 break; 705 } 706 } 707 virtual void _setRowBounds(int i, Bound bound, 708 double lo, double up) { 709 switch (bound) { 710 case FREE: 711 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); 712 break; 713 case LOWER: 714 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); 715 break; 716 case UPPER: 717 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); 718 break; 719 case DOUBLE: 720 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); 721 break; 722 case FIXED: 723 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); 724 break; 725 } 726 } 727 protected: 706 virtual void _setRowLowerBound(int i, double lo) { 707 if (lo==INF) { 708 //FIXME error 709 } 710 int b=lpx_get_row_type(lp, i); 711 double up=lpx_get_row_ub(lp, i); 712 if (lo==INF) { 713 switch (b) { 714 case LPX_FR: 715 case LPX_LO: 716 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); 717 break; 718 case LPX_UP: 719 break; 720 case LPX_DB: 721 case LPX_FX: 722 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); 723 break; 724 default: ; 725 //FIXME error 726 } 727 } else { 728 switch (b) { 729 case LPX_FR: 730 case LPX_LO: 731 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); 732 break; 733 case LPX_UP: 734 case LPX_DB: 735 case LPX_FX: 736 if (lo==up) 737 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); 738 else 739 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); 740 break; 741 default: ; 742 //FIXME error 743 } 744 } 745 } 746 virtual double _getRowLowerBound(int i) { 747 int b=lpx_get_row_type(lp, i); 748 switch (b) { 749 case LPX_FR: 750 return INF; 751 case LPX_LO: 752 return lpx_get_row_lb(lp, i); 753 case LPX_UP: 754 return INF; 755 case LPX_DB: 756 case LPX_FX: 757 return lpx_get_row_lb(lp, i); 758 default: ; 759 //FIXME error 760 return 0.0; 761 } 762 } 763 virtual void _setRowUpperBound(int i, double up) { 764 if (up==INF) { 765 //FIXME error 766 } 767 int b=lpx_get_row_type(lp, i); 768 double lo=lpx_get_row_lb(lp, i); 769 if (up==INF) { 770 switch (b) { 771 case LPX_FR: 772 case LPX_LO: 773 break; 774 case LPX_UP: 775 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); 776 break; 777 case LPX_DB: 778 case LPX_FX: 779 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); 780 break; 781 default: ; 782 //FIXME error 783 } 784 } else { 785 switch (b) { 786 case LPX_FR: 787 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); 788 case LPX_LO: 789 if (lo==up) 790 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); 791 else 792 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); 793 break; 794 case LPX_UP: 795 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); 796 break; 797 case LPX_DB: 798 case LPX_FX: 799 if (lo==up) 800 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); 801 else 802 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); 803 break; 804 default: ; 805 //FIXME error 806 } 807 } 808 } 809 virtual double _getRowUpperBound(int i) { 810 int b=lpx_get_row_type(lp, i); 811 switch (b) { 812 case LPX_FR: 813 case LPX_LO: 814 return INF; 815 case LPX_UP: 816 case LPX_DB: 817 case LPX_FX: 818 return lpx_get_row_ub(lp, i); 819 default: ; 820 //FIXME error 821 return 0.0; 822 } 823 } 728 824 /// \e 729 825 virtual double _getObjCoef(int i) { 
src/work/marci/lp/max_flow_expression.cc
r1110 r1111 7 7 #include <lemon/dimacs.h> 8 8 #include <lemon/time_measure.h> 9 #include <lp_solver_ wrapper_3.h>9 #include <lp_solver_base.h> 10 10 11 11 using std::cout; … … 52 52 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); 53 53 54 // capacity function54 // nonnegativity of flow and capacity function 55 55 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 56 56 ColIt col_it=lp.addCol(); … … 59 59 // if you change the order of the following two lines, the 60 60 // two runs of GLPK are extremely different 61 lp.setColLowerBound(col_it, 0); 61 62 lp.setColUpperBound(col_it, cap[e]); 62 lp.setColLowerBound(col_it, 0);63 63 } 64 64 … … 73 73 lp.setObjCoeffs(expr); 74 74 } 75 // flow conservation 75 // flow conservation constraints 76 76 if ((n!=s) && (n!=t)) { 77 77 RowIt row_it=lp.addRow(); 78 78 lp.setRowCoeffs(row_it, expr); 79 lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0); 79 lp.setRowLowerBound(row_it, 0.0); 80 lp.setRowUpperBound(row_it, 0.0); 80 81 } 81 82 }
Note: See TracChangeset
for help on using the changeset viewer.