1.1 --- a/src/work/marci/lp/lp_solver_base.h Wed Feb 16 16:17:30 2005 +0000
1.2 +++ b/src/work/marci/lp/lp_solver_base.h Wed Feb 16 21:40:16 2005 +0000
1.3 @@ -1,10 +1,9 @@
1.4 // -*- c++ -*-
1.5 -#ifndef LEMON_LP_SOLVER_WRAPPER_H
1.6 -#define LEMON_LP_SOLVER_WRAPPER_H
1.7 +#ifndef LEMON_LP_SOLVER_BASE_H
1.8 +#define LEMON_LP_SOLVER_BASE_H
1.9
1.10 ///\ingroup misc
1.11 ///\file
1.12 -///\brief Dijkstra algorithm.
1.13
1.14 // #include <stdio.h>
1.15 #include <stdlib.h>
1.16 @@ -24,10 +23,8 @@
1.17 #include <memory>
1.18 #include <utility>
1.19
1.20 -//#include <lemon/list_graph.h>
1.21 #include <lemon/invalid.h>
1.22 #include <expression.h>
1.23 -//#include <bfs_dfs.h>
1.24 //#include <stp.h>
1.25 //#include <lemon/max_flow.h>
1.26 //#include <augmenting_flow.h>
1.27 @@ -67,7 +64,7 @@
1.28 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
1.29 int classNum() const { return tips.size(); }
1.30 /// This lemon style iterator iterates through a class.
1.31 - class ClassIt;
1.32 + class Class;
1.33 /// Constructor. The number of classes is to be given which is fixed
1.34 /// over the life of the container.
1.35 /// The partition classes are indexed from 0 to class_num-1.
1.36 @@ -79,7 +76,7 @@
1.37 }
1.38 }
1.39 protected:
1.40 - void befuz(ClassIt it, int class_id) {
1.41 + void befuz(Class it, int class_id) {
1.42 if (tips[class_id].first==-1) {
1.43 if (tips[class_id].last==-1) {
1.44 nodes[it.i].prev=nodes[it.i].next=-1;
1.45 @@ -92,7 +89,7 @@
1.46 tips[class_id].last=it.i;
1.47 }
1.48 }
1.49 - void kifuz(ClassIt it, int class_id) {
1.50 + void kifuz(Class it, int class_id) {
1.51 if (tips[class_id].first==it.i) {
1.52 if (tips[class_id].last==it.i) {
1.53 tips[class_id].first=tips[class_id].last=-1;
1.54 @@ -113,7 +110,7 @@
1.55 public:
1.56 /// A new element with data \c t is pushed into the vector and into class
1.57 /// \c class_id.
1.58 - ClassIt push_back(const T& t, int class_id) {
1.59 + Class push_back(const T& t, int class_id) {
1.60 Node n;
1.61 n.data=t;
1.62 nodes.push_back(n);
1.63 @@ -122,51 +119,72 @@
1.64 return i;
1.65 }
1.66 /// A member is moved to an other class.
1.67 - void set(ClassIt it, int old_class_id, int new_class_id) {
1.68 + void set(Class it, int old_class_id, int new_class_id) {
1.69 kifuz(it.i, old_class_id);
1.70 befuz(it.i, new_class_id);
1.71 }
1.72 /// Returns the data pointed by \c it.
1.73 - T& operator[](ClassIt it) { return nodes[it.i].data; }
1.74 + T& operator[](Class it) { return nodes[it.i].data; }
1.75 /// Returns the data pointed by \c it.
1.76 - const T& operator[](ClassIt it) const { return nodes[it.i].data; }
1.77 + const T& operator[](Class it) const { return nodes[it.i].data; }
1.78 ///.
1.79 - class ClassIt {
1.80 + class Class {
1.81 friend class IterablePartition;
1.82 protected:
1.83 int i;
1.84 public:
1.85 /// Default constructor.
1.86 - ClassIt() { }
1.87 + Class() { }
1.88 /// This constructor constructs an iterator which points
1.89 /// to the member of th container indexed by the integer _i.
1.90 - ClassIt(const int& _i) : i(_i) { }
1.91 + Class(const int& _i) : i(_i) { }
1.92 /// Invalid constructor.
1.93 - ClassIt(const Invalid&) : i(-1) { }
1.94 - friend bool operator<(const ClassIt& x, const ClassIt& y);
1.95 + Class(const Invalid&) : i(-1) { }
1.96 + friend bool operator<(const Class& x, const Class& y);
1.97 friend std::ostream& operator<<(std::ostream& os,
1.98 - const ClassIt& it);
1.99 + const Class& it);
1.100 + bool operator==(const Class& node) const {return i == node.i;}
1.101 + bool operator!=(const Class& node) const {return i != node.i;}
1.102 };
1.103 - friend bool operator<(const ClassIt& x, const ClassIt& y) {
1.104 + friend bool operator<(const Class& x, const Class& y) {
1.105 return (x.i < y.i);
1.106 }
1.107 friend std::ostream& operator<<(std::ostream& os,
1.108 - const ClassIt& it) {
1.109 + const Class& it) {
1.110 os << it.i;
1.111 return os;
1.112 }
1.113 /// First member of class \c class_id.
1.114 - ClassIt& first(ClassIt& it, int class_id) const {
1.115 + Class& first(Class& it, int class_id) const {
1.116 it.i=tips[class_id].first;
1.117 return it;
1.118 }
1.119 /// Next member.
1.120 - ClassIt& next(ClassIt& it) const {
1.121 + Class& next(Class& it) const {
1.122 it.i=nodes[it.i].next;
1.123 return it;
1.124 }
1.125 /// True iff the iterator is valid.
1.126 - bool valid(const ClassIt& it) const { return it.i!=-1; }
1.127 + bool valid(const Class& it) const { return it.i!=-1; }
1.128 +
1.129 + class ClassIt : public Class {
1.130 + const IterablePartition* iterable_partition;
1.131 + public:
1.132 + ClassIt() { }
1.133 + ClassIt(Invalid i) : Class(i) { }
1.134 + ClassIt(const IterablePartition& _iterable_partition,
1.135 + const int& i) : iterable_partition(&_iterable_partition) {
1.136 + _iterable_partition.first(*this, i);
1.137 + }
1.138 + ClassIt(const IterablePartition& _iterable_partition,
1.139 + const Class& _class) :
1.140 + Class(_class), iterable_partition(&_iterable_partition) { }
1.141 + ClassIt& operator++() {
1.142 + iterable_partition->next(*this);
1.143 + return *this;
1.144 + }
1.145 + };
1.146 +
1.147 };
1.148
1.149
1.150 @@ -191,11 +209,15 @@
1.151 //UNCATEGORIZED
1.152
1.153 /// \e
1.154 + typedef IterablePartition<int> Rows;
1.155 + /// \e
1.156 + typedef IterablePartition<int> Cols;
1.157 + /// \e
1.158 typedef _Value Value;
1.159 /// \e
1.160 - typedef IterablePartition<int>::ClassIt Row;
1.161 + typedef Rows::Class Row;
1.162 /// \e
1.163 - typedef IterablePartition<int>::ClassIt Col;
1.164 + typedef Cols::Class Col;
1.165 public:
1.166 /// \e
1.167 IterablePartition<int> row_iter_map;
1.168 @@ -246,7 +268,6 @@
1.169 virtual void solvePrimalSimplex() = 0;
1.170 /// \e
1.171 virtual void solveDualSimplex() = 0;
1.172 - /// \e
1.173
1.174 //SOLUTION RETRIEVING
1.175
1.176 @@ -305,15 +326,20 @@
1.177 /// This routine modifies \c coeffs only by the \c push_back method.
1.178 virtual void _getRowCoeffs(int i,
1.179 std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.180 + /// \e
1.181 virtual void _setColCoeffs(int i,
1.182 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.183 /// \e
1.184 /// This routine modifies \c coeffs only by the \c push_back method.
1.185 virtual void _getColCoeffs(int i,
1.186 std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.187 - public:
1.188 /// \e
1.189 - enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
1.190 + virtual void _setCoeff(int col, int row, _Value value) = 0;
1.191 + /// \e
1.192 + virtual _Value _getCoeff(int col, int row) = 0;
1.193 + // public:
1.194 + // /// \e
1.195 + // enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
1.196 protected:
1.197 /// \e
1.198 /// The lower bound of a variable (column) have to be given by an
1.199 @@ -356,9 +382,9 @@
1.200 /// _Value or INF.
1.201 virtual _Value _getRowUpperBound(int i) = 0;
1.202 /// \e
1.203 - virtual void _setObjCoef(int i, _Value obj_coef) = 0;
1.204 + virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
1.205 /// \e
1.206 - virtual _Value _getObjCoef(int i) = 0;
1.207 + virtual _Value _getObjCoeff(int i) = 0;
1.208
1.209 //SOLUTION RETRIEVING
1.210
1.211 @@ -431,6 +457,14 @@
1.212 int_row_map.erase(int_row_map.begin()+rows[1]);
1.213 }
1.214 /// \e
1.215 + void setCoeff(Col col, Row row, _Value value) {
1.216 + _setCoeff(col_iter_map[col], row_iter_map[row], value);
1.217 + }
1.218 + /// \e
1.219 + _Value getCoeff(Col col, Row row) {
1.220 + return _getCoeff(col_iter_map[col], row_iter_map[row], value);
1.221 + }
1.222 + /// \e
1.223 void setColLowerBound(Col col, _Value lo) {
1.224 _setColLowerBound(col_iter_map[col], lo);
1.225 }
1.226 @@ -463,12 +497,12 @@
1.227 return _getRowUpperBound(row_iter_map[row]);
1.228 }
1.229 /// \e
1.230 - void setObjCoef(const Col& col, _Value obj_coef) {
1.231 - _setObjCoef(col_iter_map[col], obj_coef);
1.232 + void setObjCoeff(const Col& col, _Value obj_coef) {
1.233 + _setObjCoeff(col_iter_map[col], obj_coef);
1.234 }
1.235 /// \e
1.236 - _Value getObjCoef(const Col& col) {
1.237 - return _getObjCoef(col_iter_map[col]);
1.238 + _Value getObjCoeff(const Col& col) {
1.239 + return _getObjCoeff(col_iter_map[col]);
1.240 }
1.241
1.242 //SOLUTION RETRIEVING FUNCTIONS
1.243 @@ -551,17 +585,48 @@
1.244 }
1.245 }
1.246 /// \e
1.247 - /// \bug ez igy nem jo
1.248 void setObjCoeffs(const Expression& expr) {
1.249 + // writing zero everywhere
1.250 + for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
1.251 + setObjCoeff(it, 0.0);
1.252 + // writing the data needed
1.253 for(typename Expression::Data::const_iterator i=expr.data.begin();
1.254 i!=expr.data.end(); ++i) {
1.255 - setObjCoef((*i).first, (*i).second);
1.256 + setObjCoeff((*i).first, (*i).second);
1.257 }
1.258 }
1.259 /// \e
1.260 /// This routine modifies \c expr by only adding to it.
1.261 void getObjCoeffs(Expression& expr) {
1.262 - /// FIXME not yet implemented
1.263 + for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
1.264 + expr+=getObjCoeff(it)*it;
1.265 + }
1.266 + //@}
1.267 +
1.268 +
1.269 + /*! @name MIP functions and types (public members)
1.270 + */
1.271 + //@{
1.272 + public:
1.273 + /// \e
1.274 + virtual void solveBandB() = 0;
1.275 + /// \e
1.276 + virtual void setLP() = 0;
1.277 + /// \e
1.278 + virtual void setMIP() = 0;
1.279 + protected:
1.280 + /// \e
1.281 + virtual void _setColCont(int i) = 0;
1.282 + /// \e
1.283 + virtual void _setColInt(int i) = 0;
1.284 + public:
1.285 + /// \e
1.286 + void setColCont(Col col) {
1.287 + _setColCont(col_iter_map[col]);
1.288 + }
1.289 + /// \e
1.290 + void setColInt(Col col) {
1.291 + _setColInt(col_iter_map[col]);
1.292 }
1.293 //@}
1.294 };
1.295 @@ -691,6 +756,13 @@
1.296 rows[1]=i;
1.297 lpx_del_rows(lp, 1, rows);
1.298 }
1.299 + void _setCoeff(int col, int row, double value) {
1.300 + /// FIXME not yet implemented
1.301 + }
1.302 + double _getCoeff(int col, int row) {
1.303 + /// FIXME not yet implemented
1.304 + return 0.0;
1.305 + }
1.306 virtual void _setColLowerBound(int i, double lo) {
1.307 if (lo==INF) {
1.308 //FIXME error
1.309 @@ -928,11 +1000,11 @@
1.310 }
1.311 }
1.312 /// \e
1.313 - virtual double _getObjCoef(int i) {
1.314 + virtual double _getObjCoeff(int i) {
1.315 return lpx_get_obj_coef(lp, i);
1.316 }
1.317 /// \e
1.318 - virtual void _setObjCoef(int i, double obj_coef) {
1.319 + virtual void _setObjCoeff(int i, double obj_coef) {
1.320 lpx_set_obj_coef(lp, i, obj_coef);
1.321 }
1.322 public:
1.323 @@ -942,7 +1014,6 @@
1.324 void solvePrimalSimplex() { lpx_simplex(lp); }
1.325 /// \e
1.326 void solveDualSimplex() { lpx_simplex(lp); }
1.327 - /// \e
1.328 protected:
1.329 virtual double _getPrimal(int i) {
1.330 return lpx_get_col_prim(lp, i);
1.331 @@ -1015,10 +1086,23 @@
1.332 case LPX_NS: cout << "LPX_NS" << endl; break;
1.333 }
1.334 }
1.335 +
1.336 + // MIP
1.337 + /// \e
1.338 + void solveBandB() { lpx_integer(lp); }
1.339 + /// \e
1.340 + void setLP() { lpx_set_class(lp, LPX_LP); }
1.341 + /// \e
1.342 + void setMIP() { lpx_set_class(lp, LPX_MIP); }
1.343 + protected:
1.344 + /// \e
1.345 + void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
1.346 + /// \e
1.347 + void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
1.348 };
1.349
1.350 /// @}
1.351
1.352 } //namespace lemon
1.353
1.354 -#endif //LEMON_LP_SOLVER_WRAPPER_H
1.355 +#endif //LEMON_LP_SOLVER_BASE_H
2.1 --- a/src/work/marci/lp/max_flow_expression.cc Wed Feb 16 16:17:30 2005 +0000
2.2 +++ b/src/work/marci/lp/max_flow_expression.cc Wed Feb 16 21:40:16 2005 +0000
2.3 @@ -82,4 +82,28 @@
2.4 }
2.5 lp.solveSimplex();
2.6 cout << "elapsed time: " << ts << endl;
2.7 +// cout << "rows:" << endl;
2.8 +// for (
2.9 +// LPSolver::Rows::ClassIt i(lp.row_iter_map, 0);
2.10 +// i!=INVALID;
2.11 +// ++i) {
2.12 +// cout << i << " ";
2.13 +// }
2.14 +// cout << endl;
2.15 +// cout << "cols:" << endl;
2.16 +// for (
2.17 +// LPSolver::Cols::ClassIt i(lp.col_iter_map, 0);
2.18 +// i!=INVALID;
2.19 +// ++i) {
2.20 +// cout << i << " ";
2.21 +// }
2.22 +// cout << endl;
2.23 + lp.setMIP();
2.24 + cout << "elapsed time: " << ts << endl;
2.25 + for (LPSolver::Cols::ClassIt it(lp.col_iter_map ,1); it!=INVALID; ++it) {
2.26 + lp.setColInt(it);
2.27 + }
2.28 + cout << "elapsed time: " << ts << endl;
2.29 + lp.solveBandB();
2.30 + cout << "elapsed time: " << ts << endl;
2.31 }