1.1 --- a/src/work/marci/lp/lp_solver_wrapper_3.h Fri Jan 14 08:02:10 2005 +0000
1.2 +++ b/src/work/marci/lp/lp_solver_wrapper_3.h Fri Jan 14 13:17:16 2005 +0000
1.3 @@ -36,7 +36,6 @@
1.4 using std::endl;
1.5
1.6 namespace lemon {
1.7 -
1.8
1.9 /// \addtogroup misc
1.10 /// @{
1.11 @@ -184,15 +183,54 @@
1.12 VALID_CLASS(0), INVALID_CLASS(1) { }
1.13 /// \e
1.14 virtual ~LPSolverBase() { }
1.15 +
1.16 + //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
1.17 +
1.18 + public:
1.19 /// \e
1.20 virtual void setMinimize() = 0;
1.21 /// \e
1.22 virtual void setMaximize() = 0;
1.23 +
1.24 + //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.25 +
1.26 protected:
1.27 /// \e
1.28 virtual int _addRow() = 0;
1.29 /// \e
1.30 virtual int _addCol() = 0;
1.31 + /// \e
1.32 + virtual void _setRowCoeffs(int i,
1.33 + std::vector<std::pair<int, double> > coeffs) = 0;
1.34 + /// \e
1.35 + virtual void _setColCoeffs(int i,
1.36 + std::vector<std::pair<int, double> > coeffs) = 0;
1.37 + /// \e
1.38 + virtual void _eraseCol(int i) = 0;
1.39 + /// \e
1.40 + virtual void _eraseRow(int i) = 0;
1.41 + public:
1.42 + /// \e
1.43 + enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
1.44 + protected:
1.45 + /// \e
1.46 + virtual void _setColBounds(int i, Bound bound,
1.47 + _Value lo, _Value up) = 0;
1.48 + /// \e
1.49 + virtual void _setRowBounds(int i, Bound bound,
1.50 + _Value lo, _Value up) = 0;
1.51 + /// \e
1.52 + virtual void _setObjCoef(int i, _Value obj_coef) = 0;
1.53 + /// \e
1.54 + virtual _Value _getObjCoef(int i) = 0;
1.55 +
1.56 + //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
1.57 +
1.58 + protected:
1.59 + virtual _Value _getPrimal(int i) = 0;
1.60 +
1.61 + //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
1.62 +
1.63 public:
1.64 /// \e
1.65 RowIt addRow() {
1.66 @@ -221,12 +259,6 @@
1.67 return col_it;
1.68 }
1.69 /// \e
1.70 - virtual void setRowCoeffs(int i,
1.71 - std::vector<std::pair<int, double> > coeffs) = 0;
1.72 - /// \e
1.73 - virtual void setColCoeffs(int i,
1.74 - std::vector<std::pair<int, double> > coeffs) = 0;
1.75 - /// \e
1.76 template <typename Begin, typename End>
1.77 void setRowCoeffs(RowIt row_it, Begin begin, End end) {
1.78 std::vector<std::pair<int, double> > coeffs;
1.79 @@ -234,7 +266,7 @@
1.80 coeffs.push_back(std::
1.81 make_pair(col_iter_map[begin->first], begin->second));
1.82 }
1.83 - setRowCoeffs(row_iter_map[row_it], coeffs);
1.84 + _setRowCoeffs(row_iter_map[row_it], coeffs);
1.85 }
1.86 /// \e
1.87 template <typename Begin, typename End>
1.88 @@ -244,57 +276,8 @@
1.89 coeffs.push_back(std::
1.90 make_pair(row_iter_map[begin->first], begin->second));
1.91 }
1.92 - setColCoeffs(col_iter_map[col_it], coeffs);
1.93 + _setColCoeffs(col_iter_map[col_it], coeffs);
1.94 }
1.95 - /// temporally, glpk style indexing
1.96 - //virtual void setRowCoeffs(RowIt row_it, int num,
1.97 - // int* indices, _Value* doubles) = 0;
1.98 - //pair<RowIt, _Value>-bol kell megadni egy std range-et
1.99 - /// \e
1.100 - // virtual void seColCoeffs(int i,
1.101 - // std::vector<std::pair<int, double> > coeffs) = 0;
1.102 - /// \e
1.103 -// template <typename Begin, typename End>
1.104 -// void setRowCoeffs(RowIt row_it, Begin begin, End end) {
1.105 -// int mem_length=1+colNum();
1.106 -// int* indices = new int[mem_length];
1.107 -// _Value* doubles = new _Value[mem_length];
1.108 -// int length=0;
1.109 -// for ( ; begin!=end; ++begin) {
1.110 -// ++length;
1.111 -// indices[length]=col_iter_map[begin->first];
1.112 -// doubles[length]=begin->second;
1.113 -// }
1.114 -// setRowCoeffs(row_it, length, indices, doubles);
1.115 -// delete [] indices;
1.116 -// delete [] doubles;
1.117 -// }
1.118 - /// temporally, glpk style indexing
1.119 - //virtual void setColCoeffs(ColIt col_it, int num,
1.120 - // int* indices, _Value* doubles) = 0;
1.121 - //pair<ColIt, _Value>-bol kell megadni egy std range-et
1.122 - /// \e
1.123 -// template <typename Begin, typename End>
1.124 -// void setColCoeffs(ColIt col_it, Begin begin, End end) {
1.125 -// int mem_length=1+rowNum();
1.126 -// int* indices = new int[mem_length];
1.127 -// _Value* doubles = new _Value[mem_length];
1.128 -// int length=0;
1.129 -// for ( ; begin!=end; ++begin) {
1.130 -// ++length;
1.131 -// indices[length]=row_iter_map[begin->first];
1.132 -// doubles[length]=begin->second;
1.133 -// }
1.134 -// setColCoeffs(col_it, length, indices, doubles);
1.135 -// delete [] indices;
1.136 -// delete [] doubles;
1.137 -// }
1.138 - protected:
1.139 - /// \e
1.140 - virtual void _eraseCol(int i) = 0;
1.141 - /// \e
1.142 - virtual void _eraseRow(int i) = 0;
1.143 - public:
1.144 /// \e
1.145 void eraseCol(const ColIt& col_it) {
1.146 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
1.147 @@ -322,15 +305,26 @@
1.148 }
1.149 }
1.150 /// \e
1.151 - virtual void setColBounds(const ColIt& col_it, int bound_type,
1.152 - _Value lo, _Value up) =0;
1.153 + void setColBounds(const ColIt& col_it, Bound bound,
1.154 + _Value lo, _Value up) {
1.155 + _setColBounds(col_iter_map[col_it], bound, lo, up);
1.156 + }
1.157 /// \e
1.158 - virtual _Value getObjCoef(const ColIt& col_it) = 0;
1.159 + void setRowBounds(const RowIt& row_it, Bound bound,
1.160 + _Value lo, _Value up) {
1.161 + _setRowBounds(row_iter_map[row_it], bound, lo, up);
1.162 + }
1.163 /// \e
1.164 - virtual void setRowBounds(const RowIt& row_it, int bound_type,
1.165 - _Value lo, _Value up) = 0;
1.166 + void setObjCoef(const ColIt& col_it, _Value obj_coef) {
1.167 + _setObjCoef(col_iter_map[col_it], obj_coef);
1.168 + }
1.169 /// \e
1.170 - virtual void setObjCoef(const ColIt& col_it, _Value obj_coef) = 0;
1.171 + _Value getObjCoef(const ColIt& col_it) {
1.172 + return _getObjCoef(col_iter_map[col_it]);
1.173 + }
1.174 +
1.175 + //SOLVER FUNCTIONS
1.176 +
1.177 /// \e
1.178 virtual void solveSimplex() = 0;
1.179 /// \e
1.180 @@ -338,9 +332,18 @@
1.181 /// \e
1.182 virtual void solveDualSimplex() = 0;
1.183 /// \e
1.184 - virtual _Value getPrimal(const ColIt& col_it) = 0;
1.185 +
1.186 + //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
1.187 +
1.188 + public:
1.189 + _Value getPrimal(const ColIt& col_it) {
1.190 + return _getPrimal(col_iter_map[col_it]);
1.191 + }
1.192 /// \e
1.193 virtual _Value getObjVal() = 0;
1.194 +
1.195 + //OTHER FUNCTIONS
1.196 +
1.197 /// \e
1.198 virtual int rowNum() const = 0;
1.199 /// \e
1.200 @@ -375,7 +378,7 @@
1.201 /// The aim of this class is to give a general surface to different
1.202 /// solvers, i.e. it makes possible to write algorithms using LP's,
1.203 /// in which the solver can be changed to an other one easily.
1.204 - class LPSolverWrapper : public LPSolverBase<double> {
1.205 + class LPGLPK : public LPSolverBase<double> {
1.206 public:
1.207 typedef LPSolverBase<double> Parent;
1.208
1.209 @@ -385,14 +388,17 @@
1.210
1.211 public:
1.212 /// \e
1.213 - LPSolverWrapper() : Parent(),
1.214 + LPGLPK() : Parent(),
1.215 lp(lpx_create_prob()) {
1.216 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
1.217 }
1.218 /// \e
1.219 - ~LPSolverWrapper() {
1.220 + ~LPGLPK() {
1.221 lpx_delete_prob(lp);
1.222 }
1.223 +
1.224 + //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
1.225 +
1.226 /// \e
1.227 void setMinimize() {
1.228 lpx_set_obj_dir(lp, LPX_MIN);
1.229 @@ -401,6 +407,9 @@
1.230 void setMaximize() {
1.231 lpx_set_obj_dir(lp, LPX_MAX);
1.232 }
1.233 +
1.234 + //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.235 +
1.236 protected:
1.237 /// \e
1.238 int _addCol() {
1.239 @@ -410,11 +419,9 @@
1.240 int _addRow() {
1.241 return lpx_add_rows(lp, 1);
1.242 }
1.243 - public:
1.244 - using Parent::setRowCoeffs;
1.245 /// \e
1.246 - virtual void setRowCoeffs(int i,
1.247 - std::vector<std::pair<int, double> > coeffs) {
1.248 + virtual void _setRowCoeffs(int i,
1.249 + std::vector<std::pair<int, double> > coeffs) {
1.250 int mem_length=1+colNum();
1.251 int* indices = new int[mem_length];
1.252 double* doubles = new double[mem_length];
1.253 @@ -424,17 +431,17 @@
1.254 ++length;
1.255 indices[length]=it->first;
1.256 doubles[length]=it->second;
1.257 - std::cout << " " << indices[length] << " "
1.258 - << doubles[length] << std::endl;
1.259 +// std::cout << " " << indices[length] << " "
1.260 +// << doubles[length] << std::endl;
1.261 }
1.262 - std::cout << i << " " << length << std::endl;
1.263 +// std::cout << i << " " << length << std::endl;
1.264 lpx_set_mat_row(lp, i, length, indices, doubles);
1.265 delete [] indices;
1.266 delete [] doubles;
1.267 }
1.268 /// \e
1.269 - virtual void setColCoeffs(int i,
1.270 - std::vector<std::pair<int, double> > coeffs) {
1.271 + virtual void _setColCoeffs(int i,
1.272 + std::vector<std::pair<int, double> > coeffs) {
1.273 int mem_length=1+rowNum();
1.274 int* indices = new int[mem_length];
1.275 double* doubles = new double[mem_length];
1.276 @@ -449,74 +456,7 @@
1.277 delete [] indices;
1.278 delete [] doubles;
1.279 }
1.280 -// /// \e
1.281 -// /// temporally, glpk style indexing
1.282 -// virtual void setRowCoeffs(RowIt row_it, int num,
1.283 -// int* indices, _Value* doubles) = 0;
1.284 -// //pair<RowIt, _Value>-bol kell megadni egy std range-et
1.285 -// /// \e
1.286 -// template <typename Begin, typename End>
1.287 -// void setRowCoeffs(RowIt row_it, Begin begin, End end) {
1.288 -// int mem_length=1+colNum();
1.289 -// int* indices = new int[mem_length];
1.290 -// _Value* doubles = new _Value[mem_length];
1.291 -// int length=0;
1.292 -// for ( ; begin!=end; ++begin) {
1.293 -// ++length;
1.294 -// indices[length]=col_iter_map[begin->first];
1.295 -// doubles[length]=begin->second;
1.296 -// }
1.297 -// setRowCoeffs(row_it, length, indices, doubles);
1.298 -// delete [] indices;
1.299 -// delete [] doubles;
1.300 -// }
1.301 -// void setRowCoeffs(RowIt row_it, int length,
1.302 -// int* indices, double* doubles) {
1.303 -// lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
1.304 -// }
1.305 -// using Parent::setColCoeffs;
1.306 -// void setColCoeffs(ColIt col_it, int length,
1.307 -// int* indices, double* doubles) {
1.308 -// lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
1.309 -// }
1.310 - // //pair<RowIt, double>-bol kell megadni egy std range-et
1.311 - // /// \e
1.312 - // template <typename Begin, typename End>
1.313 - // void setColCoeffs(const ColIt& col_it,
1.314 - // Begin begin, End end) {
1.315 - // int mem_length=1+lpx_get_num_rows(lp);
1.316 - // int* indices = new int[mem_length];
1.317 - // double* doubles = new double[mem_length];
1.318 - // int length=0;
1.319 - // for ( ; begin!=end; ++begin) {
1.320 - // ++length;
1.321 - // indices[length]=row_iter_map[begin->first];
1.322 - // doubles[length]=begin->second;
1.323 - // }
1.324 - // lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
1.325 - // delete [] indices;
1.326 - // delete [] doubles;
1.327 - // }
1.328 - // //pair<ColIt, double>-bol kell megadni egy std range-et
1.329 - // /// \e
1.330 - // template <typename Begin, typename End>
1.331 - // void setRowCoeffs(const RowIt& row_it,
1.332 - // Begin begin, End end) {
1.333 - // int mem_length=1+lpx_get_num_cols(lp);
1.334 - // int* indices = new int[mem_length];
1.335 - // double* doubles = new double[mem_length];
1.336 - // int length=0;
1.337 - // for ( ; begin!=end; ++begin) {
1.338 - // ++length;
1.339 - // indices[length]=col_iter_map[begin->first];
1.340 - // doubles[length]=begin->second;
1.341 - // }
1.342 - // lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
1.343 - // delete [] indices;
1.344 - // delete [] doubles;
1.345 - // }
1.346 /// \e
1.347 - protected:
1.348 virtual void _eraseCol(int i) {
1.349 int cols[2];
1.350 cols[1]=i;
1.351 @@ -527,25 +467,56 @@
1.352 rows[1]=i;
1.353 lpx_del_rows(lp, 1, rows);
1.354 }
1.355 - public:
1.356 + virtual void _setColBounds(int i, Bound bound,
1.357 + double lo, double up) {
1.358 + switch (bound) {
1.359 + case FREE:
1.360 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.361 + break;
1.362 + case LOWER:
1.363 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.364 + break;
1.365 + case UPPER:
1.366 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.367 + break;
1.368 + case DOUBLE:
1.369 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.370 + break;
1.371 + case FIXED:
1.372 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.373 + break;
1.374 + }
1.375 + }
1.376 + virtual void _setRowBounds(int i, Bound bound,
1.377 + double lo, double up) {
1.378 + switch (bound) {
1.379 + case FREE:
1.380 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.381 + break;
1.382 + case LOWER:
1.383 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.384 + break;
1.385 + case UPPER:
1.386 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.387 + break;
1.388 + case DOUBLE:
1.389 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.390 + break;
1.391 + case FIXED:
1.392 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.393 + break;
1.394 + }
1.395 + }
1.396 + protected:
1.397 /// \e
1.398 - void setColBounds(const ColIt& col_it, int bound_type,
1.399 - double lo, double up) {
1.400 - lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
1.401 + virtual double _getObjCoef(int i) {
1.402 + return lpx_get_obj_coef(lp, i);
1.403 }
1.404 /// \e
1.405 - double getObjCoef(const ColIt& col_it) {
1.406 - return lpx_get_obj_coef(lp, col_iter_map[col_it]);
1.407 + virtual void _setObjCoef(int i, double obj_coef) {
1.408 + lpx_set_obj_coef(lp, i, obj_coef);
1.409 }
1.410 - /// \e
1.411 - void setRowBounds(const RowIt& row_it, int bound_type,
1.412 - double lo, double up) {
1.413 - lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
1.414 - }
1.415 - /// \e
1.416 - void setObjCoef(const ColIt& col_it, double obj_coef) {
1.417 - lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
1.418 - }
1.419 + public:
1.420 /// \e
1.421 void solveSimplex() { lpx_simplex(lp); }
1.422 /// \e
1.423 @@ -553,9 +524,11 @@
1.424 /// \e
1.425 void solveDualSimplex() { lpx_simplex(lp); }
1.426 /// \e
1.427 - double getPrimal(const ColIt& col_it) {
1.428 - return lpx_get_col_prim(lp, col_iter_map[col_it]);
1.429 + protected:
1.430 + virtual double _getPrimal(int i) {
1.431 + return lpx_get_col_prim(lp, i);
1.432 }
1.433 + public:
1.434 /// \e
1.435 double getObjVal() { return lpx_get_obj_val(lp); }
1.436 /// \e
2.1 --- a/src/work/marci/lp/min_cost_gen_flow.h Fri Jan 14 08:02:10 2005 +0000
2.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h Fri Jan 14 13:17:16 2005 +0000
2.3 @@ -21,10 +21,10 @@
2.4 template<typename Edge, typename EdgeIndexMap>
2.5 class PrimalMap {
2.6 protected:
2.7 - LPSolverWrapper* lp;
2.8 + LPGLPK* lp;
2.9 EdgeIndexMap* edge_index_map;
2.10 public:
2.11 - PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :
2.12 + PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) :
2.13 lp(&_lp), edge_index_map(&_edge_index_map) { }
2.14 double operator[](Edge e) const {
2.15 return lp->getPrimal((*edge_index_map)[e]);
2.16 @@ -211,7 +211,7 @@
2.17 return (min_cost_flow.flowValue()>=expected);
2.18 }
2.19 void runByLP() {
2.20 - typedef LPSolverWrapper LPSolver;
2.21 + typedef LPGLPK LPSolver;
2.22 LPSolver lp;
2.23 lp.setMinimize();
2.24 typedef LPSolver::ColIt ColIt;
2.25 @@ -223,16 +223,16 @@
2.26 ColIt col_it=lp.addCol();
2.27 edge_index_map.set(e, col_it);
2.28 if (lcapacity[e]==capacity[e])
2.29 - lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);
2.30 + lp.setColBounds(col_it, LPSolver::FIXED, lcapacity[e], capacity[e]);
2.31 else
2.32 - lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);
2.33 + lp.setColBounds(col_it, LPSolver::DOUBLE, lcapacity[e], capacity[e]);
2.34 lp.setObjCoef(col_it, cost[e]);
2.35 }
2.36 LPSolver::ColIt col_it;
2.37 for (lp.col_iter_map.first(col_it, lp.VALID_CLASS);
2.38 lp.col_iter_map.valid(col_it);
2.39 lp.col_iter_map.next(col_it)) {
2.40 - std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
2.41 +// std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
2.42 }
2.43 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
2.44 typename Graph::template EdgeMap<Num> coeffs(g, 0);
2.45 @@ -250,9 +250,9 @@
2.46 }
2.47 }
2.48 //std::cout << std::endl;
2.49 - std::cout << " " << g.id(n) << " " << row.size() << std::endl;
2.50 + //std::cout << " " << g.id(n) << " " << row.size() << std::endl;
2.51 lp.setRowCoeffs(row_it, row.begin(), row.end());
2.52 - lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);
2.53 + lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
2.54 }
2.55 lp.solveSimplex();
2.56 //std::cout << lp.colNum() << std::endl;