Changeset 1445:4635352e5524 in lemon0.x
 Timestamp:
 06/04/05 14:50:15 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1925
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/lp_base.h
r1439 r1445 411 411 }; 412 412 413 ///Linear expression of rows 414 415 ///This data structure represents a column of the matrix, 416 ///thas is it strores a linear expression of the dual variables 417 ///(\ref Row "Row"s). 418 /// 419 ///There are several ways to access and modify the contents of this 420 ///container. 421 /// Its it fully compatible with \c std::map<Row,double>, so for expamle 422 ///if \c e is an DualExpr and \c v 423 ///and \c w are of type \ref Row, then you can 424 ///read and modify the coefficients like 425 ///these. 426 ///\code 427 ///e[v]=5; 428 ///e[v]+=12; 429 ///e.erase(v); 430 ///\endcode 431 ///or you can also iterate through its elements. 432 ///\code 433 ///double s=0; 434 ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i) 435 /// s+=i>second; 436 ///\endcode 437 ///(This code computes the sum of all coefficients). 438 /// Numbers (<tt>double</tt>'s) 439 ///and variables (\ref Row "Row"s) directly convert to an 440 ///\ref DualExpr and the usual linear operations are defined so 441 ///\code 442 ///v+w 443 ///2*v3.12*(vw/2) 444 ///v*2.1+(3*v+(v*12+w)*3)/2 445 ///\endcode 446 ///are valid \ref DualExpr "DualExpr"essions. 447 ///The usual assignment operations are also defined. 448 ///\code 449 ///e=v+w; 450 ///e+=2*v3.12*(vw/2); 451 ///e*=3.4; 452 ///e/=5; 453 ///\endcode 454 /// 455 ///\sa Expr 456 /// 457 class DualExpr : public std::map<Row,Value> 458 { 459 public: 460 typedef LpSolverBase::Row Key; 461 typedef LpSolverBase::Value Value; 462 463 protected: 464 typedef std::map<Row,Value> Base; 465 466 public: 467 typedef True IsLinExpression; 468 ///\e 469 DualExpr() : Base() { } 470 ///\e 471 DualExpr(const Key &v) { 472 Base::insert(std::make_pair(v, 1)); 473 } 474 ///\e 475 DualExpr(const Value &v) {} 476 ///\e 477 void set(const Key &v,const Value &c) { 478 Base::insert(std::make_pair(v, c)); 479 } 480 481 ///Removes the components with zero coefficient. 482 void simplify() { 483 for (Base::iterator i=Base::begin(); i!=Base::end();) { 484 Base::iterator j=i; 485 ++j; 486 if ((*i).second==0) Base::erase(i); 487 j=i; 488 } 489 } 490 491 ///Sets all coefficients to 0. 492 void clear() { 493 Base::clear(); 494 } 495 496 ///\e 497 DualExpr &operator+=(const DualExpr &e) { 498 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j) 499 (*this)[j>first]+=j>second; 500 ///\todo it might be speeded up using "hints" 501 return *this; 502 } 503 ///\e 504 DualExpr &operator=(const DualExpr &e) { 505 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j) 506 (*this)[j>first]=j>second; 507 return *this; 508 } 509 ///\e 510 DualExpr &operator*=(const Value &c) { 511 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) 512 j>second*=c; 513 return *this; 514 } 515 ///\e 516 DualExpr &operator/=(const Value &c) { 517 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j) 518 j>second/=c; 519 return *this; 520 } 521 }; 522 413 523 414 524 protected: … … 548 658 #endif 549 659 550 ///Add a new empty row (i.e a new constaint) to the LP 551 552 ///This function adds a new empty row (i.e a new constaint) to the LP. 660 ///Set a column (i.e a dual constraint) of the LP 661 662 ///\param c is the column to be modified 663 ///\param e is a dual linear expression (see \ref DualExpr) 664 ///\bug This is a temportary function. The interface will change to 665 ///a better one. 666 void setCol(Col c,const DualExpr &e) { 667 std::vector<int> indices; 668 std::vector<Value> values; 669 indices.push_back(0); 670 values.push_back(0); 671 for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i) 672 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!! 673 indices.push_back(cols.floatingId((*i).first.id)); 674 values.push_back((*i).second); 675 } 676 _setColCoeffs(cols.floatingId(c.id),indices.size()1, 677 &indices[0],&values[0]); 678 } 679 680 ///Add a new column to the LP 681 682 ///\param e is a dual linear expression (see \ref DualExpr) 683 ///\param obj is the corresponding component of the objective 684 ///function. It is 0 by default. 685 ///\return The created column. 686 ///\bug This is a temportary function. The interface will change to 687 ///a better one. 688 Col addCol(Value l,const DualExpr &e, Value obj=0) { 689 Col c=addCol(); 690 setCol(c,e); 691 objCoeff(c,0); 692 return c; 693 } 694 695 ///Add a new empty row (i.e a new constraint) to the LP 696 697 ///This function adds a new empty row (i.e a new constraint) to the LP. 553 698 ///\return The created row 554 699 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;} 555 700 556 ///Set a row (i.e a constaint) of the LP 701 ///\brief Adds several new row 702 ///(i.e a variables) at once 703 /// 704 ///This magic function takes a container as its argument 705 ///and fills its elements 706 ///with new row (i.e. variables) 707 ///\param t can be 708 /// a standard STL compatible iterable container with 709 ///\ref Row as its \c values_type 710 ///like 711 ///\code 712 ///std::vector<LpSolverBase::Row> 713 ///std::list<LpSolverBase::Row> 714 ///\endcode 715 /// a standard STL compatible iterable container with 716 ///\ref Row as its \c mapped_type 717 ///like 718 ///\code 719 ///std::map<AnyType,LpSolverBase::Row> 720 ///\endcode 721 /// an iterable lemon \ref concept::WriteMap "write map" like 722 ///\code 723 ///ListGraph::NodeMap<LpSolverBase::Row> 724 ///ListGraph::EdgeMap<LpSolverBase::Row> 725 ///\endcode 726 ///\return The number of rows created. 727 #ifdef DOXYGEN 728 template<class T> 729 int addRowSet(T &t) { return 0;} 730 #else 731 template<class T> 732 typename enable_if<typename T::value_type::LpSolverRow,int>::type 733 addRowSet(T &t,dummy<0> = 0) { 734 int s=0; 735 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;} 736 return s; 737 } 738 template<class T> 739 typename enable_if<typename T::value_type::second_type::LpSolverRow, 740 int>::type 741 addRowSet(T &t,dummy<1> = 1) { 742 int s=0; 743 for(typename T::iterator i=t.begin();i!=t.end();++i) { 744 i>second=addRow(); 745 s++; 746 } 747 return s; 748 } 749 template<class T> 750 typename enable_if<typename T::ValueSet::value_type::LpSolverRow, 751 int>::type 752 addRowSet(T &t,dummy<2> = 2) { 753 ///\bug <tt>return addRowSet(t.valueSet());</tt> should also work. 754 int s=0; 755 for(typename T::ValueSet::iterator i=t.valueSet().begin(); 756 i!=t.valueSet().end(); 757 ++i) 758 { 759 *i=addRow(); 760 s++; 761 } 762 return s; 763 } 764 #endif 765 766 ///Set a row (i.e a constraint) of the LP 557 767 558 768 ///\param r is the row to be modified … … 581 791 } 582 792 583 ///Set a row (i.e a const aint) of the LP793 ///Set a row (i.e a constraint) of the LP 584 794 585 795 ///\param r is the row to be modified … … 592 802 } 593 803 594 ///Add a new row (i.e a new const aint) to the LP804 ///Add a new row (i.e a new constraint) to the LP 595 805 596 806 ///\param l is the lower bound (\ref INF means no bound) … … 606 816 } 607 817 608 ///Add a new row (i.e a new const aint) to the LP818 ///Add a new row (i.e a new constraint) to the LP 609 819 610 820 ///\param c is a linear expression (see \ref Constr) … … 918 1128 } 919 1129 1130 ///\e 1131 1132 ///\relates LpSolverBase::DualExpr 1133 /// 1134 inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a, 1135 const LpSolverBase::DualExpr &b) 1136 { 1137 LpSolverBase::DualExpr tmp(a); 1138 tmp+=b; ///\todo Doesn't STL have some special 'merge' algorithm? 1139 return tmp; 1140 } 1141 ///\e 1142 1143 ///\relates LpSolverBase::DualExpr 1144 /// 1145 inline LpSolverBase::DualExpr operator(const LpSolverBase::DualExpr &a, 1146 const LpSolverBase::DualExpr &b) 1147 { 1148 LpSolverBase::DualExpr tmp(a); 1149 tmp=b; ///\todo Doesn't STL have some special 'merge' algorithm? 1150 return tmp; 1151 } 1152 ///\e 1153 1154 ///\relates LpSolverBase::DualExpr 1155 /// 1156 inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a, 1157 const LpSolverBase::Value &b) 1158 { 1159 LpSolverBase::DualExpr tmp(a); 1160 tmp*=b; ///\todo Doesn't STL have some special 'merge' algorithm? 1161 return tmp; 1162 } 1163 1164 ///\e 1165 1166 ///\relates LpSolverBase::DualExpr 1167 /// 1168 inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a, 1169 const LpSolverBase::DualExpr &b) 1170 { 1171 LpSolverBase::DualExpr tmp(b); 1172 tmp*=a; ///\todo Doesn't STL have some special 'merge' algorithm? 1173 return tmp; 1174 } 1175 ///\e 1176 1177 ///\relates LpSolverBase::DualExpr 1178 /// 1179 inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a, 1180 const LpSolverBase::Value &b) 1181 { 1182 LpSolverBase::DualExpr tmp(a); 1183 tmp/=b; ///\todo Doesn't STL have some special 'merge' algorithm? 1184 return tmp; 1185 } 1186 920 1187 921 1188 } //namespace lemon 
test/lp_test.cc
r1437 r1445 35 35 lp.addColSet(z); 36 36 37 { 38 LP::Expr e,f,g; 39 LP::Col p1,p2,p3,p4,p5; 40 LP::Constr c; 41 42 e[p1]=2; 43 e.constComp()=12; 44 e[p1]+=2; 45 e.constComp()+=12; 46 e[p1]=2; 47 e.constComp()=12; 48 49 e=2; 50 e=2.2; 51 e=p1; 52 e=f; 53 54 e+=2; 55 e+=2.2; 56 e+=p1; 57 e+=f; 58 59 e=2; 60 e=2.2; 61 e=p1; 62 e=f; 63 64 e*=2; 65 e*=2.2; 66 e/=2; 67 e/=2.2; 68 69 e=((p1+p2)+(p1p2)+(p1+12)+(12+p1)+(p112)+(12p1)+ 70 (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+ 71 (f12)+(12f)+(p1f)+(fp1)+(fg)+ 72 2.2*f+f*2.2+f/2.2+ 73 2*f+f*2+f/2+ 74 2.2*p1+p1*2.2+p1/2.2+ 75 2*p1+p1*2+p1/2 76 ); 37 77 38 LP::Expr e,f,g; 39 LP::Col p1,p2,p3,p4,p5; 40 LP::Constr c; 78 79 c = (e <= f ); 80 c = (e <= 2.2); 81 c = (e <= 2 ); 82 c = (e <= p1 ); 83 c = (2.2<= f ); 84 c = (2 <= f ); 85 c = (p1 <= f ); 86 c = (p1 <= p2 ); 87 c = (p1 <= 2.2); 88 c = (p1 <= 2 ); 89 c = (2.2<= p2 ); 90 c = (2 <= p2 ); 91 92 c = (e >= f ); 93 c = (e >= 2.2); 94 c = (e >= 2 ); 95 c = (e >= p1 ); 96 c = (2.2>= f ); 97 c = (2 >= f ); 98 c = (p1 >= f ); 99 c = (p1 >= p2 ); 100 c = (p1 >= 2.2); 101 c = (p1 >= 2 ); 102 c = (2.2>= p2 ); 103 c = (2 >= p2 ); 104 105 c = (e == f ); 106 c = (e == 2.2); 107 c = (e == 2 ); 108 c = (e == p1 ); 109 c = (2.2== f ); 110 c = (2 == f ); 111 c = (p1 == f ); 112 //c = (p1 == p2 ); 113 c = (p1 == 2.2); 114 c = (p1 == 2 ); 115 c = (2.2== p2 ); 116 c = (2 == p2 ); 117 118 c = (2 <= e <= 3); 119 c = (2 <= p1<= 3); 120 121 c = (2 >= e >= 3); 122 c = (2 >= p1>= 3); 123 124 e[x[3]]=2; 125 e[x[3]]=4; 126 e[x[3]]=1; 127 e.constComp()=12; 128 129 lp.addRow(LP::INF,e,23); 130 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)x[3],23); 131 lp.addRow(LP::INF,3.0*(x[1]+x[2]*25*x[3]+12x[4]/3)+2*x[4]4,23); 132 133 lp.addRow(x[1]+x[3]<=x[5]3); 134 lp.addRow(7<=x[1]+x[3]12<=3); 135 lp.addRow(x[1]<=x[5]); 136 } 41 137 42 e[p1]=2; 43 e.constComp()=12; 44 e[p1]+=2; 45 e.constComp()+=12; 46 e[p1]=2; 47 e.constComp()=12; 48 49 e=2; 50 e=2.2; 51 e=p1; 52 e=f; 53 54 e+=2; 55 e+=2.2; 56 e+=p1; 57 e+=f; 58 59 e=2; 60 e=2.2; 61 e=p1; 62 e=f; 63 64 e*=2; 65 e*=2.2; 66 e/=2; 67 e/=2.2; 68 69 e=((p1+p2)+(p1p2)+(p1+12)+(12+p1)+(p112)+(12p1)+ 70 (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+ 71 (f12)+(12f)+(p1f)+(fp1)+(fg)+ 72 2.2*f+f*2.2+f/2.2+ 73 2*f+f*2+f/2+ 74 2.2*p1+p1*2.2+p1/2.2+ 75 2*p1+p1*2+p1/2 76 ); 138 { 139 LP::DualExpr e,f,g; 140 LP::Row p1,p2,p3,p4,p5; 141 142 e[p1]=2; 143 e[p1]+=2; 144 e[p1]=2; 145 146 e=p1; 147 e=f; 148 149 e+=p1; 150 e+=f; 151 152 e=p1; 153 e=f; 154 155 e*=2; 156 e*=2.2; 157 e/=2; 158 e/=2.2; 159 160 e=((p1+p2)+(p1p2)+(p1+12)+(12+p1)+(p112)+(12p1)+ 161 (p1+f)+(f+p1)+(f+g)+ 162 (p1f)+(fp1)+(fg)+ 163 2.2*f+f*2.2+f/2.2+ 164 2*f+f*2+f/2+ 165 2.2*p1+p1*2.2+p1/2.2+ 166 2*p1+p1*2+p1/2 167 ); 168 } 77 169 78 170 79 c = (e <= f );80 c = (e <= 2.2);81 c = (e <= 2 );82 c = (e <= p1 );83 c = (2.2<= f );84 c = (2 <= f );85 c = (p1 <= f );86 c = (p1 <= p2 );87 c = (p1 <= 2.2);88 c = (p1 <= 2 );89 c = (2.2<= p2 );90 c = (2 <= p2 );91 92 c = (e >= f );93 c = (e >= 2.2);94 c = (e >= 2 );95 c = (e >= p1 );96 c = (2.2>= f );97 c = (2 >= f );98 c = (p1 >= f );99 c = (p1 >= p2 );100 c = (p1 >= 2.2);101 c = (p1 >= 2 );102 c = (2.2>= p2 );103 c = (2 >= p2 );104 105 c = (e == f );106 c = (e == 2.2);107 c = (e == 2 );108 c = (e == p1 );109 c = (2.2== f );110 c = (2 == f );111 c = (p1 == f );112 //c = (p1 == p2 );113 c = (p1 == 2.2);114 c = (p1 == 2 );115 c = (2.2== p2 );116 c = (2 == p2 );117 118 c = (2 <= e <= 3);119 c = (2 <= p1<= 3);120 121 c = (2 >= e >= 3);122 c = (2 >= p1>= 3);123 124 e[x[3]]=2;125 e[x[3]]=4;126 e[x[3]]=1;127 e.constComp()=12;128 129 lp.addRow(LP::INF,e,23);130 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)x[3],23);131 lp.addRow(LP::INF,3.0*(x[1]+x[2]*25*x[3]+12x[4]/3)+2*x[4]4,23);132 133 lp.addRow(x[1]+x[3]<=x[5]3);134 lp.addRow(7<=x[1]+x[3]12<=3);135 lp.addRow(x[1]<=x[5]);136 137 138 139 171 } 140 172
Note: See TracChangeset
for help on using the changeset viewer.