Changeset 2312:07e46cbb7d85 in lemon-0.x for lemon/lp_base.h
- Timestamp:
- 11/29/06 16:01:13 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3088
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/lp_base.h
r2309 r2312 33 33 ///\ingroup gen_opt_group 34 34 namespace lemon { 35 35 36 36 37 ///Internal data structure to convert floating id's to fix one's 37 38 … … 110 111 int firstIndex() {return _first_index;} 111 112 }; 112 113 113 114 ///Common base class for LP solvers 114 115 … … 129 130 ///has been proved. 130 131 SOLVED = 0, 131 ///Any other case (including the case when some user specified limit has been exceeded) 132 ///Any other case (including the case when some user specified 133 ///limit has been exceeded) 132 134 UNSOLVED = 1 133 135 }; … … 222 224 } 223 225 }; 226 227 static int id(const Col& col) { return col.id; } 228 224 229 225 230 ///Refer to a row of the LP. … … 246 251 bool operator==(Row c) const {return id==c.id;} 247 252 bool operator!=(Row c) const {return id!=c.id;} 248 }; 253 }; 254 255 static int id(const Row& row) { return row.id; } 256 257 protected: 258 259 int _lpId(const Col& col) const { 260 return cols.floatingId(id(col)); 261 } 262 263 int _lpId(const Row& row) const { 264 return rows.floatingId(id(row)); 265 } 266 267 268 public: 249 269 250 270 ///Linear expression of variables and a constant component … … 337 357 } 338 358 359 void simplify() const { 360 const_cast<Expr*>(this)->simplify(); 361 } 362 339 363 ///Removes the coefficients closer to zero than \c tolerance. 340 364 void simplify(double &tolerance) { … … 416 440 typedef Expr::Value Value; 417 441 418 // static const Value INF;419 // static const Value NaN;420 421 442 protected: 422 443 Expr _expr; … … 554 575 } 555 576 577 void simplify() const { 578 const_cast<DualExpr*>(this)->simplify(); 579 } 580 556 581 ///Removes the coefficients closer to zero than \c tolerance. 557 582 void simplify(double &tolerance) { … … 564 589 } 565 590 566 567 591 ///Sets all coefficients to 0. 568 592 void clear() { … … 597 621 598 622 623 private: 624 625 template <typename _Base> 626 class MappedIterator { 627 public: 628 629 typedef _Base Base; 630 631 typedef typename Base::iterator_category iterator_category; 632 typedef typename Base::difference_type difference_type; 633 typedef const std::pair<int, Value> value_type; 634 typedef value_type reference; 635 class pointer { 636 public: 637 pointer(value_type& _value) : value(_value) {} 638 value_type* operator->() { return &value; } 639 private: 640 value_type value; 641 }; 642 643 MappedIterator(const Base& _base, const LpSolverBase& _lp) 644 : base(_base), lp(_lp) {} 645 646 reference operator*() { 647 return std::make_pair(lp._lpId(base->first), base->second); 648 } 649 650 pointer operator->() { 651 return pointer(operator*()); 652 } 653 654 MappedIterator& operator++() { 655 ++base; 656 return *this; 657 } 658 659 MappedIterator& operator++(int) { 660 MappedIterator tmp(*this); 661 ++base; 662 return tmp; 663 } 664 665 bool operator==(const MappedIterator& it) const { 666 return base == it.base; 667 } 668 669 bool operator!=(const MappedIterator& it) const { 670 return base != it.base; 671 } 672 673 private: 674 Base base; 675 const LpSolverBase& lp; 676 }; 677 599 678 protected: 679 680 /// STL compatible iterator for lp col 681 typedef MappedIterator<Expr::const_iterator> LpRowIterator; 682 /// STL compatible iterator for lp row 683 typedef MappedIterator<DualExpr::const_iterator> LpColIterator; 600 684 601 685 //Abstract virtual functions 602 686 virtual LpSolverBase &_newLp() = 0; 603 687 virtual LpSolverBase &_copyLp(){ 604 ///\todo This should be implemented here, too, when we have problem retrieving routines. It can be overriden. 688 ///\todo This should be implemented here, too, when we have 689 ///problem retrieving routines. It can be overriden. 605 690 606 691 //Starting: … … 614 699 virtual void _eraseCol(int col) = 0; 615 700 virtual void _eraseRow(int row) = 0; 616 virtual void _getColName(int col, 701 virtual void _getColName(int col, std::string & name) = 0; 617 702 virtual void _setColName(int col, const std::string & name) = 0; 618 virtual void _setRowCoeffs(int i, 619 int length, 620 int const * indices, 621 Value const * values ) = 0; 622 virtual void _setColCoeffs(int i, 623 int length, 624 int const * indices, 625 Value const * values ) = 0; 703 virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0; 704 virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0; 626 705 virtual void _setCoeff(int row, int col, Value value) = 0; 627 706 virtual void _setColLowerBound(int i, Value value) = 0; … … 632 711 virtual void _setObjCoeff(int i, Value obj_coef) = 0; 633 712 virtual void _clearObj()=0; 634 // virtual void _setObj(int length, 635 // int const * indices, 636 // Value const * values ) = 0; 713 637 714 virtual SolveExitStatus _solve() = 0; 638 715 virtual Value _getPrimal(int i) = 0; … … 653 730 //Constant component of the objective function 654 731 Value obj_const_comp; 655 656 657 658 732 659 733 public: 660 734 … … 745 819 ///a better one. 746 820 void col(Col c,const DualExpr &e) { 747 std::vector<int> indices; 748 std::vector<Value> values; 749 indices.push_back(0); 750 values.push_back(0); 751 for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i) 752 if((*i).second!=0) { 753 indices.push_back(rows.floatingId((*i).first.id)); 754 values.push_back((*i).second); 755 } 756 _setColCoeffs(cols.floatingId(c.id),indices.size()-1, 757 &indices[0],&values[0]); 821 e.simplify(); 822 _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this), 823 LpColIterator(e.end(), *this)); 758 824 } 759 825 … … 850 916 ///added or not. 851 917 void row(Row r, Value l,const Expr &e, Value u) { 852 std::vector<int> indices; 853 std::vector<Value> values; 854 indices.push_back(0); 855 values.push_back(0); 856 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i) 857 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!! 858 indices.push_back(cols.floatingId((*i).first.id)); 859 values.push_back((*i).second); 860 } 861 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1, 862 &indices[0],&values[0]); 863 // _setRowLowerBound(rows.floatingId(r.id),l-e.constComp()); 864 // _setRowUpperBound(rows.floatingId(r.id),u-e.constComp()); 865 _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp()); 918 e.simplify(); 919 _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this), 920 LpRowIterator(e.end(), *this)); 921 // _setRowLowerBound(_lpId(r),l-e.constComp()); 922 // _setRowUpperBound(_lpId(r),u-e.constComp()); 923 _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp()); 866 924 } 867 925 … … 871 929 ///\param c is a linear expression (see \ref Constr) 872 930 void row(Row r, const Constr &c) { 873 row(r, 874 c.lowerBounded()?c.lowerBound():-INF, 875 c.expr(), 876 c.upperBounded()?c.upperBound():INF); 931 row(r, c.lowerBounded()?c.lowerBound():-INF, 932 c.expr(), c.upperBounded()?c.upperBound():INF); 877 933 } 878 934 … … 905 961 ///\todo Please check this 906 962 void eraseCol(Col c) { 907 _eraseCol( cols.floatingId(c.id));963 _eraseCol(_lpId(c)); 908 964 cols.erase(c.id); 909 965 } … … 913 969 ///\todo Please check this 914 970 void eraseRow(Row r) { 915 _eraseRow( rows.floatingId(r.id));971 _eraseRow(_lpId(r)); 916 972 rows.erase(r.id); 917 973 } … … 923 979 std::string colName(Col c){ 924 980 std::string name; 925 _getColName( cols.floatingId(c.id), name);981 _getColName(_lpId(c), name); 926 982 return name; 927 983 } … … 931 987 ///\param c is the coresponding coloumn 932 988 ///\param name The name to be given 933 void colName(Col c, const std::string 934 _setColName( cols.floatingId(c.id), name);989 void colName(Col c, const std::string& name){ 990 _setColName(_lpId(c), name); 935 991 } 936 992 … … 942 998 943 999 void coeff(Row r, Col c, Value val){ 944 _setCoeff( rows.floatingId(r.id),cols.floatingId(c.id), val);1000 _setCoeff(_lpId(r),_lpId(c), val); 945 1001 } 946 1002 … … 951 1007 /// Value or -\ref INF. 952 1008 void colLowerBound(Col c, Value value) { 953 _setColLowerBound( cols.floatingId(c.id),value);1009 _setColLowerBound(_lpId(c),value); 954 1010 } 955 1011 … … 997 1053 /// Value or \ref INF. 998 1054 void colUpperBound(Col c, Value value) { 999 _setColUpperBound( cols.floatingId(c.id),value);1055 _setColUpperBound(_lpId(c),value); 1000 1056 }; 1001 1057 … … 1044 1100 /// Value, -\ref INF or \ref INF. 1045 1101 void colBounds(Col c, Value lower, Value upper) { 1046 _setColLowerBound( cols.floatingId(c.id),lower);1047 _setColUpperBound( cols.floatingId(c.id),upper);1102 _setColLowerBound(_lpId(c),lower); 1103 _setColUpperBound(_lpId(c),upper); 1048 1104 } 1049 1105 … … 1092 1148 // /// Value or -\ref INF. 1093 1149 // void rowLowerBound(Row r, Value value) { 1094 // _setRowLowerBound( rows.floatingId(r.id),value);1150 // _setRowLowerBound(_lpId(r),value); 1095 1151 // }; 1096 1152 // /// Set the upper bound of a row (i.e a constraint) … … 1100 1156 // /// Value or \ref INF. 1101 1157 // void rowUpperBound(Row r, Value value) { 1102 // _setRowUpperBound( rows.floatingId(r.id),value);1158 // _setRowUpperBound(_lpId(r),value); 1103 1159 // }; 1104 1160 … … 1110 1166 /// Value, -\ref INF or \ref INF. 1111 1167 void rowBounds(Row c, Value lower, Value upper) { 1112 _setRowBounds( rows.floatingId(c.id),lower, upper);1113 // _setRowUpperBound( rows.floatingId(c.id),upper);1168 _setRowBounds(_lpId(c),lower, upper); 1169 // _setRowUpperBound(_lpId(c),upper); 1114 1170 } 1115 1171 1116 1172 ///Set an element of the objective function 1117 void objCoeff(Col c, Value v) {_setObjCoeff( cols.floatingId(c.id),v); };1173 void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); }; 1118 1174 ///Set the objective function 1119 1175 … … 1171 1227 1172 1228 ///\e 1173 Value primal(Col c) { return _getPrimal( cols.floatingId(c.id)); }1229 Value primal(Col c) { return _getPrimal(_lpId(c)); } 1174 1230 1175 1231 ///\e 1176 Value dual(Row r) { return _getDual( rows.floatingId(r.id)); }1232 Value dual(Row r) { return _getDual(_lpId(r)); } 1177 1233 1178 1234 ///\e 1179 bool isBasicCol(Col c) { return _isBasicCol( cols.floatingId(c.id)); }1235 bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); } 1180 1236 1181 1237 ///\e … … 1214 1270 ///Sets the type of the given coloumn to the given type. 1215 1271 void colType(Col c, ColTypes col_type) { 1216 _colType( cols.floatingId(c.id),col_type);1272 _colType(_lpId(c),col_type); 1217 1273 } 1218 1274 … … 1221 1277 ///Gives back the type of the column. 1222 1278 ColTypes colType(Col c){ 1223 return _colType( cols.floatingId(c.id));1279 return _colType(_lpId(c)); 1224 1280 } 1225 1281 … … 1441 1497 /// 1442 1498 inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a, 1443 1499 const LpSolverBase::DualExpr &b) 1444 1500 { 1445 1501 LpSolverBase::DualExpr tmp(a); … … 1452 1508 /// 1453 1509 inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a, 1454 1510 const LpSolverBase::DualExpr &b) 1455 1511 { 1456 1512 LpSolverBase::DualExpr tmp(a); … … 1463 1519 /// 1464 1520 inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a, 1465 1521 const LpSolverBase::Value &b) 1466 1522 { 1467 1523 LpSolverBase::DualExpr tmp(a); … … 1475 1531 /// 1476 1532 inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a, 1477 1533 const LpSolverBase::DualExpr &b) 1478 1534 { 1479 1535 LpSolverBase::DualExpr tmp(b); … … 1486 1542 /// 1487 1543 inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a, 1488 1544 const LpSolverBase::Value &b) 1489 1545 { 1490 1546 LpSolverBase::DualExpr tmp(a);
Note: See TracChangeset
for help on using the changeset viewer.