Changeset 1253:609fe893df8c in lemon0.x for src/work/athos/lp/lp_base.h
 Timestamp:
 03/24/05 12:44:25 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1680
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/lp/lp_base.h
r1251 r1253 1 1 /* * C++ * 2 * src/lemon/ maps.h  Part of LEMON, a generic C++ optimization library2 * src/lemon/lp_base.h  Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 18 18 #define LEMON_LP_BASE_H 19 19 20 #include<vector> 21 22 #include<lemon/error.h> 23 24 #include"lin_expr.h" 20 25 ///\file 21 26 ///\brief The interface of the LP solver interface. 22 27 namespace lemon { 28 29 ///Internal data structure to convert floating id's to fix one's 30 31 ///\todo This might by implemented to be usable in other places. 32 class _FixId 33 { 34 std::vector<int> index; 35 std::vector<int> cross; 36 int first_free; 37 public: 38 _FixId() : first_free(1) {}; 39 ///Convert a floating id to a fix one 40 41 ///\param n is a floating id 42 ///\return the corresponding fix id 43 int fixId(int n) {return cross[n];} 44 ///Convert a fix id to a floating one 45 46 ///\param n is a fix id 47 ///\return the corresponding floating id 48 int floatingId(int n) { return index[n];} 49 ///Add a new floating id. 50 51 ///\param n is a floating id 52 ///\return the fix id of the new value 53 ///\todo Multiple additions should also be handled. 54 int insert(int n) 55 { 56 if(n>=int(cross.size())) { 57 cross.resize(n+1); 58 if(first_free==1) { 59 cross[n]=index.size(); 60 index.push_back(n); 61 } 62 else { 63 cross[n]=first_free; 64 int next=index[first_free]; 65 index[first_free]=n; 66 first_free=next; 67 } 68 } 69 else throw LogicError(); //floatingIds must form a continuous range; 70 } 71 ///Remove a fix id. 72 73 ///\param n is a fix id 74 /// 75 void erase(int n) 76 { 77 int fl=index[n]; 78 index[n]=first_free; 79 first_free=n; 80 for(int i=fl+1;i<int(cross.size());++i) { 81 cross[i1]=cross[i]; 82 index[cross[i]]; 83 } 84 cross.pop_back(); 85 } 86 ///An upper bound on the largest fix id. 87 88 ///\todo Do we need this? 89 /// 90 std::size_t maxFixId() { return cross.size()1; } 91 92 }; 93 94 ///Common base class for LP solvers 23 95 class LpSolverBase { 96 24 97 public: 25 26 //UNCATEGORIZED27 98 28 99 /// \e … … 30 101 /// \e 31 102 static const Value INF; 32 protected: 103 104 ///\e 105 class Col { protected: int id; friend class LpSolverBase; }; 106 ///\e 107 class Row { protected: int id; friend class LpSolverBase; }; 108 109 typedef SparseLinExpr<Col, Value> Expr; 110 111 protected: 112 _FixId rows; 113 _FixId cols; 33 114 34 115 //MATRIX MANIPULATING FUNCTIONS … … 39 120 virtual int _addRow() = 0; 40 121 /// \e 122 41 123 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored) 124 /// 42 125 virtual void _setRowCoeffs(int i, 43 126 int length, … … 45 128 Value const * values ) = 0; 46 129 /// \e 130 47 131 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored) 132 /// 48 133 virtual void _setColCoeffs(int i, 49 134 int length, … … 52 137 53 138 /// \e 139 54 140 /// The lower bound of a variable (column) have to be given by an 55 141 /// extended number of type Value, i.e. a finite number of type … … 57 143 virtual void _setColLowerBound(int i, Value value) = 0; 58 144 /// \e 145 59 146 /// The upper bound of a variable (column) have to be given by an 60 147 /// extended number of type Value, i.e. a finite number of type … … 62 149 virtual void _setColUpperBound(int i, Value value) = 0; 63 150 /// \e 151 64 152 /// The lower bound of a linear expression (row) have to be given by an 65 153 /// extended number of type Value, i.e. a finite number of type … … 67 155 virtual void _setRowLowerBound(int i, Value value) = 0; 68 156 /// \e 157 69 158 /// The upper bound of a linear expression (row) have to be given by an 70 159 /// extended number of type Value, i.e. a finite number of type … … 74 163 /// \e 75 164 virtual void _setObjCoeff(int i, Value obj_coef) = 0; 165 166 ///\e 167 168 ///\bug unimplemented!!!! 169 void clearObj() {} 170 public: 171 172 173 ///\e 174 virtual ~LpSolverBase() {} 175 176 ///Add a new empty column (i.e a new variable) to the LP 177 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;} 178 ///Add a new empty row (i.e a new constaint) to the LP 179 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;} 180 181 ///Add a new row (i.e a new constaint) to the LP 182 183 ///\param l lower bound (INF means no bound) 184 ///\param e a linear expression (see \ref Expr) 185 ///\param u upper bound (INF means no bound) 186 ///\bug This is a temportary function. The interface will change to 187 ///a better one. 188 Row addRow(Value l,Expr e, Value u) { 189 Row r=addRow(); 190 std::vector<int> indices; 191 std::vector<Value> values; 192 indices.push_back(0); 193 values.push_back(0); 194 for(Expr::iterator i=e.begin(); i!=e.end(); ++i) { 195 indices.push_back(cols.floatingId((*i).first.id)); 196 values.push_back((*i).second); 197 } 198 _setRowCoeffs(rows.floatingId(r.id),indices.size()1, 199 &indices[0],&values[0]); 200 _setRowLowerBound(rows.floatingId(r.id),l); 201 _setRowUpperBound(rows.floatingId(r.id),l); 202 return r; 203 } 204 205 /// Set the lower bound of a column (i.e a variable) 206 207 /// The upper bound of a variable (column) have to be given by an 208 /// extended number of type Value, i.e. a finite number of type 209 /// Value or INF. 210 virtual void setColLowerBound(Col c, Value value) { 211 _setColLowerBound(cols.floatingId(c.id),value); 212 } 213 /// Set the upper bound of a column (i.e a variable) 214 215 /// The upper bound of a variable (column) have to be given by an 216 /// extended number of type Value, i.e. a finite number of type 217 /// Value or INF. 218 virtual void setColUpperBound(Col c, Value value) { 219 _setColUpperBound(cols.floatingId(c.id),value); 220 }; 221 /// Set the lower bound of a row (i.e a constraint) 222 223 /// The lower bound of a linear expression (row) have to be given by an 224 /// extended number of type Value, i.e. a finite number of type 225 /// Value or INF. 226 virtual void setRowLowerBound(Row r, Value value) { 227 _setRowLowerBound(rows.floatingId(r.id),value); 228 }; 229 /// Set the upper bound of a row (i.e a constraint) 230 231 /// The upper bound of a linear expression (row) have to be given by an 232 /// extended number of type Value, i.e. a finite number of type 233 /// Value or INF. 234 virtual void setRowUpperBound(Row r, Value value) { 235 _setRowUpperBound(rows.floatingId(r.id),value); 236 }; 237 ///Set an element of the objective function 238 void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); }; 239 ///Set the objective function 240 241 ///\param e is a linear expression of type \ref Expr. 242 ///\todo What to do with the constant component? 243 void setObj(Expr e) { 244 clearObj(); 245 for (Expr::iterator i=e.begin(); i!=e.end(); ++i) 246 setObjCoeff((*i).first,(*i).second); 247 } 248 76 249 }; 77 250
Note: See TracChangeset
for help on using the changeset viewer.