1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/lp/lp_solver_glpk.cc Fri Mar 25 15:23:00 2005 +0000
1.3 @@ -0,0 +1,28 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef LEMON_LP_SOLVER_GLPK_CC
1.6 +#define LEMON_LP_SOLVER_GLPK_CC
1.7 + //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.8 +extern "C" {
1.9 +#include "glpk.h"
1.10 +}
1.11 +#include "lp_solver_glpk.h"
1.12 +
1.13 +namespace lemon {
1.14 +
1.15 +
1.16 + /// \e
1.17 + int LpGlpk::_addCol() {
1.18 + int i=lpx_add_cols(lp, 1);
1.19 + _setColLowerBound(i, -INF);
1.20 + _setColUpperBound(i, INF);
1.21 + return i;
1.22 + }
1.23 + /// \e
1.24 + int LpGlpk::_addRow() {
1.25 + int i=lpx_add_rows(lp, 1);
1.26 + return i;
1.27 + }
1.28 +
1.29 +} //namespace lemon
1.30 +
1.31 +#endif //LEMON_LP_SOLVER_GLPK_CC
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/lp/lp_solver_glpk.h Fri Mar 25 15:23:00 2005 +0000
2.3 @@ -0,0 +1,565 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef LEMON_LP_SOLVER_GLPK_H
2.6 +#define LEMON_LP_SOLVER_GLPK_H
2.7 +
2.8 +///\ingroup misc
2.9 +///\file
2.10 +
2.11 +extern "C" {
2.12 +#include "glpk.h"
2.13 +}
2.14 +#include <lp_solver_base.h>
2.15 +
2.16 +namespace lemon {
2.17 +
2.18 +
2.19 + template <typename Value>
2.20 + const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity();
2.21 +
2.22 +
2.23 + /// \brief Wrapper for GLPK solver
2.24 + ///
2.25 + /// This class implements a lemon wrapper for GLPK.
2.26 + class LpGlpk : public LpSolverBase<double> {
2.27 +
2.28 + public:
2.29 +
2.30 + typedef LpSolverBase<double> Parent;
2.31 +
2.32 + /// \e
2.33 + LPX* lp;
2.34 +
2.35 + /// \e
2.36 + LpGlpk() : Parent(),
2.37 + lp(lpx_create_prob()) {
2.38 + //int_row_map.push_back(Row());
2.39 + //int_col_map.push_back(Col());
2.40 + lpx_set_int_parm(lp, LPX_K_DUAL, 1);
2.41 + }
2.42 + /// \e
2.43 + ~LpGlpk() {
2.44 + lpx_delete_prob(lp);
2.45 + }
2.46 +
2.47 + //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
2.48 +
2.49 + /// \e
2.50 + void setMinimize() {
2.51 + lpx_set_obj_dir(lp, LPX_MIN);
2.52 + }
2.53 + /// \e
2.54 + void setMaximize() {
2.55 + lpx_set_obj_dir(lp, LPX_MAX);
2.56 + }
2.57 +
2.58 + /// \e
2.59 + /// Retrieve number of rows
2.60 + int rowNum() const { return lpx_get_num_rows(lp); }
2.61 + /// \e
2.62 + /// Retrieve number of coloumns
2.63 + int colNum() const { return lpx_get_num_cols(lp); }
2.64 +
2.65 + protected:
2.66 + /// \e
2.67 + int LpGlpk::_addCol() {
2.68 + int i=lpx_add_cols(lp, 1);
2.69 + _setColLowerBound(i, -INF);
2.70 + _setColUpperBound(i, INF);
2.71 + return i;
2.72 + }
2.73 + /// \e
2.74 + int LpGlpk::_addRow() {
2.75 + int i=lpx_add_rows(lp, 1);
2.76 + return i;
2.77 + }
2.78 + /// \e
2.79 + virtual void _setRowCoeffs(int i,
2.80 + const std::vector<std::pair<int, double> >& coeffs) {
2.81 + int mem_length=1+colNum();
2.82 + int* indices = new int[mem_length];
2.83 + double* doubles = new double[mem_length];
2.84 + int length=0;
2.85 + for (std::vector<std::pair<int, double> >::
2.86 + const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
2.87 + ++length;
2.88 + indices[length]=it->first;
2.89 + doubles[length]=it->second;
2.90 + }
2.91 + lpx_set_mat_row(lp, i, length, indices, doubles);
2.92 + delete [] indices;
2.93 + delete [] doubles;
2.94 + }
2.95 + /// \e
2.96 + virtual void _getRowCoeffs(int i,
2.97 + std::vector<std::pair<int, double> >& coeffs) {
2.98 + int mem_length=1+colNum();
2.99 + int* indices = new int[mem_length];
2.100 + double* doubles = new double[mem_length];
2.101 + int length=lpx_get_mat_row(lp, i, indices, doubles);
2.102 + for (int i=1; i<=length; ++i) {
2.103 + coeffs.push_back(std::make_pair(indices[i], doubles[i]));
2.104 + }
2.105 + delete [] indices;
2.106 + delete [] doubles;
2.107 + }
2.108 + /// \e
2.109 + virtual void _setColCoeffs(int i,
2.110 + const std::vector<std::pair<int, double> >& coeffs) {
2.111 + int mem_length=1+rowNum();
2.112 + int* indices = new int[mem_length];
2.113 + double* doubles = new double[mem_length];
2.114 + int length=0;
2.115 + for (std::vector<std::pair<int, double> >::
2.116 + const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
2.117 + ++length;
2.118 + indices[length]=it->first;
2.119 + doubles[length]=it->second;
2.120 + }
2.121 + lpx_set_mat_col(lp, i, length, indices, doubles);
2.122 + delete [] indices;
2.123 + delete [] doubles;
2.124 + }
2.125 + /// \e
2.126 + virtual void _getColCoeffs(int i,
2.127 + std::vector<std::pair<int, double> >& coeffs) {
2.128 + int mem_length=1+rowNum();
2.129 + int* indices = new int[mem_length];
2.130 + double* doubles = new double[mem_length];
2.131 + int length=lpx_get_mat_col(lp, i, indices, doubles);
2.132 + for (int i=1; i<=length; ++i) {
2.133 + coeffs.push_back(std::make_pair(indices[i], doubles[i]));
2.134 + }
2.135 + delete [] indices;
2.136 + delete [] doubles;
2.137 + }
2.138 + /// \e
2.139 + virtual void _eraseCol(int i) {
2.140 + int cols[2];
2.141 + cols[1]=i;
2.142 + lpx_del_cols(lp, 1, cols);
2.143 + }
2.144 + virtual void _eraseRow(int i) {
2.145 + int rows[2];
2.146 + rows[1]=i;
2.147 + lpx_del_rows(lp, 1, rows);
2.148 + }
2.149 +
2.150 + void _setCoeff(int row, int col, double value) {
2.151 + ///FIXME Of course this is not efficient at all, but GLPK knows not more.
2.152 + /// First approach: get one row, apply changes and set it again
2.153 +
2.154 + int mem_length=1+colNum();
2.155 + int* indices = new int[mem_length];
2.156 + double* doubles = new double[mem_length];
2.157 +
2.158 +
2.159 + int length=lpx_get_mat_row(lp, i, indices, doubles);
2.160 +
2.161 + //The following code does not suppose that the elements of the array indices are sorted
2.162 + int i=1;
2.163 + bool found=false;
2.164 + while (i <= length && !found){
2.165 + if (indices[i]=col){
2.166 + found = true;
2.167 + doubles[i]=value;
2.168 + }
2.169 + ++i;
2.170 + }
2.171 + if (!found){
2.172 + ++length;
2.173 + indices[length]=col;
2.174 + doubles[length]=value;
2.175 + }
2.176 +
2.177 +// This is a piece of code that assumes that the array 'indices' is sorted.
2.178 +// Not ready, I suppose.
2.179 +// //We need another arrays to put the data back, anyway
2.180 +// int* new_indices = new int[length+1];
2.181 +// double* new_doubles = new double[length+1];
2.182 +// int offset;
2.183 +
2.184 +// int i=1;
2.185 +// while (i <= length && indices[i]<col){
2.186 +// new_indiced[i]=indices[i];
2.187 +// new_doubles[i]=doubles[i];
2.188 +// ++i;
2.189 +// }
2.190 +// if (i>length || indices[i]>col){
2.191 +// //Ha atugrottuk, vagy a vegen van
2.192 +// new_indices[i]=col;
2.193 +// new_doubles[i]=value;
2.194 +// offset = 1;
2.195 +// }
2.196 +// else{
2.197 +// //I.e.: indices[i]=col
2.198 +// new_doubles[i]=value;
2.199 +// offset = 0;
2.200 +// ++i;
2.201 +// }
2.202 +// while (i <= length){
2.203 +// new_indices[i+offset]=indices[i];
2.204 +// new_values[i+offset]=values[i];
2.205 +// }
2.206 +
2.207 + lpx_set_mat_row(lp, row, length, indices, doubles);
2.208 + delete [] indices;
2.209 + delete [] doubles;
2.210 +
2.211 +// lpx_set_mat_row(lp, row, length+offset, new_indices, new_doubles);
2.212 +// delete [] new_indices;
2.213 +// delete [] new_doubles;
2.214 +
2.215 +
2.216 + }
2.217 + double _getCoeff(int col, int row) {
2.218 + /// FIXME not yet implemented
2.219 + return 0.0;
2.220 + }
2.221 + virtual void _setColLowerBound(int i, double lo) {
2.222 + if (lo==INF) {
2.223 + //FIXME error
2.224 + }
2.225 + int b=lpx_get_col_type(lp, i);
2.226 + double up=lpx_get_col_ub(lp, i);
2.227 + if (lo==-INF) {
2.228 + switch (b) {
2.229 + case LPX_FR:
2.230 + case LPX_LO:
2.231 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
2.232 + break;
2.233 + case LPX_UP:
2.234 + break;
2.235 + case LPX_DB:
2.236 + case LPX_FX:
2.237 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
2.238 + break;
2.239 + default: ;
2.240 + //FIXME error
2.241 + }
2.242 + } else {
2.243 + switch (b) {
2.244 + case LPX_FR:
2.245 + case LPX_LO:
2.246 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
2.247 + break;
2.248 + case LPX_UP:
2.249 + case LPX_DB:
2.250 + case LPX_FX:
2.251 + if (lo==up)
2.252 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
2.253 + else
2.254 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
2.255 + break;
2.256 + default: ;
2.257 + //FIXME error
2.258 + }
2.259 + }
2.260 + }
2.261 + virtual double _getColLowerBound(int i) {
2.262 + int b=lpx_get_col_type(lp, i);
2.263 + switch (b) {
2.264 + case LPX_FR:
2.265 + return -INF;
2.266 + case LPX_LO:
2.267 + return lpx_get_col_lb(lp, i);
2.268 + case LPX_UP:
2.269 + return -INF;
2.270 + case LPX_DB:
2.271 + case LPX_FX:
2.272 + return lpx_get_col_lb(lp, i);
2.273 + default: ;
2.274 + //FIXME error
2.275 + return 0.0;
2.276 + }
2.277 + }
2.278 + virtual void _setColUpperBound(int i, double up) {
2.279 + if (up==-INF) {
2.280 + //FIXME error
2.281 + }
2.282 + int b=lpx_get_col_type(lp, i);
2.283 + double lo=lpx_get_col_lb(lp, i);
2.284 + if (up==INF) {
2.285 + switch (b) {
2.286 + case LPX_FR:
2.287 + case LPX_LO:
2.288 + break;
2.289 + case LPX_UP:
2.290 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
2.291 + break;
2.292 + case LPX_DB:
2.293 + case LPX_FX:
2.294 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
2.295 + break;
2.296 + default: ;
2.297 + //FIXME error
2.298 + }
2.299 + } else {
2.300 + switch (b) {
2.301 + case LPX_FR:
2.302 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
2.303 + case LPX_LO:
2.304 + if (lo==up)
2.305 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
2.306 + else
2.307 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
2.308 + break;
2.309 + case LPX_UP:
2.310 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
2.311 + break;
2.312 + case LPX_DB:
2.313 + case LPX_FX:
2.314 + if (lo==up)
2.315 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
2.316 + else
2.317 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
2.318 + break;
2.319 + default: ;
2.320 + //FIXME error
2.321 + }
2.322 + }
2.323 + }
2.324 + virtual double _getColUpperBound(int i) {
2.325 + int b=lpx_get_col_type(lp, i);
2.326 + switch (b) {
2.327 + case LPX_FR:
2.328 + case LPX_LO:
2.329 + return INF;
2.330 + case LPX_UP:
2.331 + case LPX_DB:
2.332 + case LPX_FX:
2.333 + return lpx_get_col_ub(lp, i);
2.334 + default: ;
2.335 + //FIXME error
2.336 + return 0.0;
2.337 + }
2.338 + }
2.339 + virtual void _setRowLowerBound(int i, double lo) {
2.340 + if (lo==INF) {
2.341 + //FIXME error
2.342 + }
2.343 + int b=lpx_get_row_type(lp, i);
2.344 + double up=lpx_get_row_ub(lp, i);
2.345 + if (lo==-INF) {
2.346 + switch (b) {
2.347 + case LPX_FR:
2.348 + case LPX_LO:
2.349 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
2.350 + break;
2.351 + case LPX_UP:
2.352 + break;
2.353 + case LPX_DB:
2.354 + case LPX_FX:
2.355 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
2.356 + break;
2.357 + default: ;
2.358 + //FIXME error
2.359 + }
2.360 + } else {
2.361 + switch (b) {
2.362 + case LPX_FR:
2.363 + case LPX_LO:
2.364 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
2.365 + break;
2.366 + case LPX_UP:
2.367 + case LPX_DB:
2.368 + case LPX_FX:
2.369 + if (lo==up)
2.370 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
2.371 + else
2.372 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
2.373 + break;
2.374 + default: ;
2.375 + //FIXME error
2.376 + }
2.377 + }
2.378 + }
2.379 + virtual double _getRowLowerBound(int i) {
2.380 + int b=lpx_get_row_type(lp, i);
2.381 + switch (b) {
2.382 + case LPX_FR:
2.383 + return -INF;
2.384 + case LPX_LO:
2.385 + return lpx_get_row_lb(lp, i);
2.386 + case LPX_UP:
2.387 + return -INF;
2.388 + case LPX_DB:
2.389 + case LPX_FX:
2.390 + return lpx_get_row_lb(lp, i);
2.391 + default: ;
2.392 + //FIXME error
2.393 + return 0.0;
2.394 + }
2.395 + }
2.396 + virtual void _setRowUpperBound(int i, double up) {
2.397 + if (up==-INF) {
2.398 + //FIXME error
2.399 + }
2.400 + int b=lpx_get_row_type(lp, i);
2.401 + double lo=lpx_get_row_lb(lp, i);
2.402 + if (up==INF) {
2.403 + switch (b) {
2.404 + case LPX_FR:
2.405 + case LPX_LO:
2.406 + break;
2.407 + case LPX_UP:
2.408 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
2.409 + break;
2.410 + case LPX_DB:
2.411 + case LPX_FX:
2.412 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
2.413 + break;
2.414 + default: ;
2.415 + //FIXME error
2.416 + }
2.417 + } else {
2.418 + switch (b) {
2.419 + case LPX_FR:
2.420 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
2.421 + case LPX_LO:
2.422 + if (lo==up)
2.423 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
2.424 + else
2.425 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
2.426 + break;
2.427 + case LPX_UP:
2.428 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
2.429 + break;
2.430 + case LPX_DB:
2.431 + case LPX_FX:
2.432 + if (lo==up)
2.433 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
2.434 + else
2.435 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
2.436 + break;
2.437 + default: ;
2.438 + //FIXME error
2.439 + }
2.440 + }
2.441 + }
2.442 + virtual double _getRowUpperBound(int i) {
2.443 + int b=lpx_get_row_type(lp, i);
2.444 + switch (b) {
2.445 + case LPX_FR:
2.446 + case LPX_LO:
2.447 + return INF;
2.448 + case LPX_UP:
2.449 + case LPX_DB:
2.450 + case LPX_FX:
2.451 + return lpx_get_row_ub(lp, i);
2.452 + default: ;
2.453 + //FIXME error
2.454 + return 0.0;
2.455 + }
2.456 + }
2.457 + /// \e
2.458 + virtual double _getObjCoeff(int i) {
2.459 + return lpx_get_obj_coef(lp, i);
2.460 + }
2.461 + /// \e
2.462 + virtual void _setObjCoeff(int i, double obj_coef) {
2.463 + lpx_set_obj_coef(lp, i, obj_coef);
2.464 + }
2.465 +
2.466 + protected:
2.467 + virtual double _getPrimal(int i) {
2.468 + return lpx_get_col_prim(lp, i);
2.469 + }
2.470 +
2.471 + //MIP
2.472 + protected:
2.473 + /// \e
2.474 + void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
2.475 + /// \e
2.476 + void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
2.477 + /// \e
2.478 + double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }
2.479 +
2.480 +
2.481 +// public:
2.482 +// /// \e
2.483 +// void solveSimplex() { lpx_simplex(lp); }
2.484 +// /// \e
2.485 +// void solvePrimalSimplex() { lpx_simplex(lp); }
2.486 +// /// \e
2.487 +// void solveDualSimplex() { lpx_simplex(lp); }
2.488 +// /// \e
2.489 +// double getObjVal() { return lpx_get_obj_val(lp); }
2.490 +// /// \e
2.491 +// int warmUp() { return lpx_warm_up(lp); }
2.492 +// /// \e
2.493 +// void printWarmUpStatus(int i) {
2.494 +// switch (i) {
2.495 +// case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
2.496 +// case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
2.497 +// case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
2.498 +// case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
2.499 +// }
2.500 +// }
2.501 +// /// \e
2.502 +// int getPrimalStatus() { return lpx_get_prim_stat(lp); }
2.503 +// /// \e
2.504 +// void printPrimalStatus(int i) {
2.505 +// switch (i) {
2.506 +// case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
2.507 +// case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
2.508 +// case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
2.509 +// case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
2.510 +// }
2.511 +// }
2.512 +// /// \e
2.513 +// int getDualStatus() { return lpx_get_dual_stat(lp); }
2.514 +// /// \e
2.515 +// void printDualStatus(int i) {
2.516 +// switch (i) {
2.517 +// case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
2.518 +// case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
2.519 +// case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
2.520 +// case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
2.521 +// }
2.522 +// }
2.523 +// /// Returns the status of the slack variable assigned to row \c row.
2.524 +// int getRowStat(const Row& row) {
2.525 +// return lpx_get_row_stat(lp, row_iter_map[row]);
2.526 +// }
2.527 +// /// \e
2.528 +// void printRowStatus(int i) {
2.529 +// switch (i) {
2.530 +// case LPX_BS: cout << "LPX_BS" << endl; break;
2.531 +// case LPX_NL: cout << "LPX_NL" << endl; break;
2.532 +// case LPX_NU: cout << "LPX_NU" << endl; break;
2.533 +// case LPX_NF: cout << "LPX_NF" << endl; break;
2.534 +// case LPX_NS: cout << "LPX_NS" << endl; break;
2.535 +// }
2.536 +// }
2.537 +// /// Returns the status of the variable assigned to column \c col.
2.538 +// int getColStat(const Col& col) {
2.539 +// return lpx_get_col_stat(lp, col_iter_map[col]);
2.540 +// }
2.541 +// /// \e
2.542 +// void printColStatus(int i) {
2.543 +// switch (i) {
2.544 +// case LPX_BS: cout << "LPX_BS" << endl; break;
2.545 +// case LPX_NL: cout << "LPX_NL" << endl; break;
2.546 +// case LPX_NU: cout << "LPX_NU" << endl; break;
2.547 +// case LPX_NF: cout << "LPX_NF" << endl; break;
2.548 +// case LPX_NS: cout << "LPX_NS" << endl; break;
2.549 +// }
2.550 +// }
2.551 +
2.552 +// // MIP
2.553 +// /// \e
2.554 +// void solveBandB() { lpx_integer(lp); }
2.555 +// /// \e
2.556 +// void setLP() { lpx_set_class(lp, LPX_LP); }
2.557 +// /// \e
2.558 +// void setMIP() { lpx_set_class(lp, LPX_MIP); }
2.559 +
2.560 +
2.561 +
2.562 + };
2.563 +
2.564 + /// @}
2.565 +
2.566 +} //namespace lemon
2.567 +
2.568 +#endif //LEMON_LP_SOLVER_GLPK_H