Changeset 2312:07e46cbb7d85 in lemon-0.x for lemon
- Timestamp:
- 11/29/06 16:01:13 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3088
- Location:
- lemon
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/lp.h
r2221 r2312 29 29 #include <lemon/lp_cplex.h> 30 30 #include <lemon/mip_cplex.h> 31 #elif HAVE_SOPLEX 32 #include <lemon/lp_soplex.h> 31 33 #endif 32 34 … … 77 79 typedef MipCplex Mip; 78 80 const char default_solver_name[]="CPLEX"; 81 #elif HAVE_SOPLEX 82 #define DEFAULT_LP SOPLEX 83 typedef LpSoplex Lp; 84 const char default_solver_name[]="SOPLEX"; 79 85 #endif 80 86 #endif -
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); -
lemon/lp_cplex.cc
r2218 r2312 110 110 111 111 ///\warning Data at index 0 is ignored in the arrays. 112 void LpCplex::_setRowCoeffs(int i, 113 int length, 114 int const * indices, 115 Value const * values ) 116 { 117 int rowlist[length+1]; 118 int* p=rowlist; 119 for (int k=1;k<=length;++k){ 120 rowlist[k]=i; 121 } 122 status = CPXchgcoeflist(env, lp, 123 length, 124 p+1, 125 const_cast<int * >(indices+1), 126 const_cast<Value * >(values+1)); 127 } 128 129 void LpCplex::_setColCoeffs(int i, 130 int length, 131 int const * indices, 132 Value const * values) 133 { 134 int collist[length+1]; 135 int* p=collist; 136 for (int k=1;k<=length;++k){ 137 collist[k]=i; 138 } 139 status = CPXchgcoeflist(env, lp, 140 length, 141 const_cast<int * >(indices+1), 142 p+1, 143 const_cast<Value * >(values+1)); 112 void LpCplex::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) 113 { 114 std::vector<int> indices; 115 std::vector<int> rowlist; 116 std::vector<Value> values; 117 118 for(LpRowIterator it=b; it!=e; ++it) { 119 indices.push_back(it->first); 120 values.push_back(it->second); 121 rowlist.push_back(i); 122 } 123 124 status = CPXchgcoeflist(env, lp, values.size(), 125 &rowlist[0], &indices[0], &values[0]); 126 } 127 128 void LpCplex::_setColCoeffs(int i, LpColIterator b, LpColIterator e) 129 { 130 std::vector<int> indices; 131 std::vector<int> collist; 132 std::vector<Value> values; 133 134 for(LpColIterator it=b; it!=e; ++it) { 135 indices.push_back(it->first); 136 values.push_back(it->second); 137 collist.push_back(i); 138 } 139 140 status = CPXchgcoeflist(env, lp, values.size(), 141 &indices[0], &collist[0], &values[0]); 144 142 } 145 143 -
lemon/lp_cplex.h
r2218 r2312 62 62 virtual void _getColName(int col, std::string & name); 63 63 virtual void _setColName(int col, const std::string & name); 64 virtual void _setRowCoeffs(int i, 65 int length, 66 const int * indices, 67 const Value * values ); 68 virtual void _setColCoeffs(int i, 69 int length, 70 const int * indices, 71 const Value * values); 64 virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e); 65 virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e); 72 66 virtual void _setCoeff(int row, int col, Value value); 73 67 virtual void _setColLowerBound(int i, Value value); -
lemon/lp_glpk.cc
r2253 r2312 117 117 } 118 118 119 void LpGlpk::_setRowCoeffs(int i, 120 int length, 121 const int * indices, 122 const Value * values ) 123 { 124 lpx_set_mat_row(lp, i, length, 125 const_cast<int * >(indices) , 126 const_cast<Value * >(values)); 127 } 128 129 void LpGlpk::_setColCoeffs(int i, 130 int length, 131 const int * indices, 132 const Value * values) 133 { 134 lpx_set_mat_col(lp, i, length, 135 const_cast<int * >(indices), 136 const_cast<Value * >(values)); 119 void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) 120 { 121 std::vector<int> indices; 122 std::vector<Value> values; 123 124 indices.push_back(0); 125 values.push_back(0); 126 127 for(LpRowIterator it=b; it!=e; ++it) { 128 indices.push_back(it->first); 129 values.push_back(it->second); 130 } 131 132 lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]); 133 } 134 135 void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) { 136 137 std::vector<int> indices; 138 std::vector<Value> values; 139 140 indices.push_back(0); 141 values.push_back(0); 142 143 for(LpColIterator it=b; it!=e; ++it) { 144 indices.push_back(it->first); 145 values.push_back(it->second); 146 } 147 148 lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]); 137 149 } 138 150 … … 140 152 void LpGlpk::_setCoeff(int row, int col, Value value) 141 153 { 142 ///FIXME Of course this is not efficient at all, but GLPK knows not more. 143 // First approach: get one row, apply changes and set it again 144 //(one idea to improve this: maybe it is better to do this with 1 coloumn) 154 155 if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) { 156 157 int length=lpx_get_mat_row(lp, row, 0, 0); 158 159 std::vector<int> indices(length + 2); 160 std::vector<Value> values(length + 2); 161 162 lpx_get_mat_row(lp, row, &indices[0], &values[0]); 163 164 //The following code does not suppose that the elements of the 165 //array indices are sorted 166 bool found=false; 167 for (int i = 1; i <= length; ++i) { 168 if (indices[i]==col){ 169 found=true; 170 values[i]=value; 171 break; 172 } 173 } 174 if (!found){ 175 ++length; 176 indices[length]=col; 177 values[length]=value; 178 } 145 179 146 int mem_length=2+lpx_get_num_cols(lp); 147 int* indices = new int[mem_length]; 148 Value* values = new Value[mem_length]; 180 lpx_set_mat_row(lp, row, length, &indices[0], &values[0]); 181 182 } else { 183 184 int length=lpx_get_mat_col(lp, col, 0, 0); 185 186 std::vector<int> indices(length + 2); 187 std::vector<Value> values(length + 2); 188 189 lpx_get_mat_col(lp, col, &indices[0], &values[0]); 190 191 //The following code does not suppose that the elements of the 192 //array indices are sorted 193 bool found=false; 194 for (int i = 1; i <= length; ++i) { 195 if (indices[i]==col){ 196 found=true; 197 values[i]=value; 198 break; 199 } 200 } 201 if (!found){ 202 ++length; 203 indices[length]=row; 204 values[length]=value; 205 } 149 206 150 151 int length=lpx_get_mat_row(lp, row, indices, values); 152 153 //The following code does not suppose that the elements of the array indices are sorted 154 int i=1; 155 bool found=false; 156 while (i <= length && !found){ 157 if (indices[i]==col){ 158 found = true; 159 values[i]=value; 160 } 161 ++i; 162 } 163 if (!found){ 164 ++length; 165 indices[length]=col; 166 values[length]=value; 167 } 168 169 lpx_set_mat_row(lp, row, length, indices, values); 170 delete [] indices; 171 delete [] values; 172 207 lpx_set_mat_col(lp, col, length, &indices[0], &values[0]); 208 } 173 209 } 174 210 -
lemon/lp_glpk.h
r2144 r2312 57 57 virtual void _getColName(int col, std::string & name); 58 58 virtual void _setColName(int col, const std::string & name); 59 virtual void _setRowCoeffs(int i, 60 int length, 61 const int * indices, 62 const Value * values ); 63 virtual void _setColCoeffs(int i, 64 int length, 65 const int * indices, 66 const Value * values); 59 virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e); 60 virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e); 67 61 virtual void _setCoeff(int row, int col, Value value); 68 62 virtual void _setColLowerBound(int i, Value value); -
lemon/lp_skeleton.cc
r1956 r2312 59 59 60 60 61 void LpSkeleton::_setRowCoeffs(int, 62 int, 63 int const *, 64 Value const *) 65 { 61 void LpSkeleton::_setRowCoeffs(int, LpRowIterator, LpRowIterator) { 66 62 } 67 63 68 void LpSkeleton::_setColCoeffs(int, 69 int, 70 int const *, 71 Value const *) 72 { 64 void LpSkeleton::_setColCoeffs(int, LpColIterator, LpColIterator) { 73 65 } 74 66 -
lemon/lp_skeleton.h
r1956 r2312 44 44 virtual void _eraseRow(int i); 45 45 /// \e 46 virtual void _getColName(int col, 46 virtual void _getColName(int col, std::string & name); 47 47 /// \e 48 48 virtual void _setColName(int col, const std::string & name); 49 49 50 50 /// \e 51 52 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored) 53 /// 54 virtual void _setRowCoeffs(int i, 55 int length, 56 int const * indices, 57 Value const * values ); 51 virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e); 58 52 /// \e 59 60 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored) 61 /// 62 virtual void _setColCoeffs(int i, 63 int length, 64 int const * indices, 65 Value const * values ); 53 virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e); 66 54 67 55 /// Set one element of the coefficient matrix
Note: See TracChangeset
for help on using the changeset viewer.