Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/athos/lp/lp_solver_glpk.h
author alpar
Fri, 25 Mar 2005 18:56:07 +0000
changeset 1264 92ba3e62825d
permissions -rw-r--r--
Constraints (expressions containing <= or >=) can be passed to addRow()
and setRow() 
     1 // -*- c++ -*-

     2 #ifndef LEMON_LP_SOLVER_GLPK_H

     3 #define LEMON_LP_SOLVER_GLPK_H

     4 

     5 ///\ingroup misc

     6 ///\file

     7 

     8 extern "C" {

     9 #include "glpk.h"

    10 }

    11 #include <lp_solver_base.h>

    12 

    13 namespace lemon {

    14   

    15   

    16   template <typename Value>

    17   const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity();

    18 

    19 

    20   /// \brief Wrapper for GLPK solver

    21   /// 

    22   /// This class implements a lemon wrapper for GLPK.

    23   class LpGlpk : public LpSolverBase<double> {

    24 

    25   public:

    26 

    27     typedef LpSolverBase<double> Parent;

    28     

    29     /// \e

    30     LPX* lp;

    31 

    32     /// \e

    33     LpGlpk() : Parent(), 

    34 			lp(lpx_create_prob()) {

    35       //int_row_map.push_back(Row());

    36       //int_col_map.push_back(Col());

    37       lpx_set_int_parm(lp, LPX_K_DUAL, 1);

    38     }

    39     /// \e

    40     ~LpGlpk() {

    41       lpx_delete_prob(lp);

    42     }

    43 

    44     //MATRIX INDEPEDENT MANIPULATING FUNCTIONS

    45 

    46     /// \e

    47     void setMinimize() { 

    48       lpx_set_obj_dir(lp, LPX_MIN);

    49     }

    50     /// \e

    51     void setMaximize() { 

    52       lpx_set_obj_dir(lp, LPX_MAX);

    53     }

    54 

    55     /// \e

    56     /// Retrieve number of rows

    57     int rowNum() const { return lpx_get_num_rows(lp); }

    58     /// \e

    59     /// Retrieve number of coloumns

    60     int colNum() const { return lpx_get_num_cols(lp); }

    61 

    62   protected:

    63     /// \e

    64     int LpGlpk::_addCol() { 

    65       int i=lpx_add_cols(lp, 1);

    66       _setColLowerBound(i, -INF);

    67       _setColUpperBound(i, INF);

    68       return i;

    69     }

    70     /// \e

    71     int LpGlpk::_addRow() { 

    72       int i=lpx_add_rows(lp, 1);

    73       return i;

    74     }

    75     /// \e

    76     virtual void _setRowCoeffs(int i, 

    77 			       const std::vector<std::pair<int, double> >& coeffs) {

    78       int mem_length=1+colNum();

    79       int* indices = new int[mem_length];

    80       double* doubles = new double[mem_length];

    81       int length=0;

    82       for (std::vector<std::pair<int, double> >::

    83 	     const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {

    84 	++length;

    85 	indices[length]=it->first;

    86 	doubles[length]=it->second;

    87       }

    88       lpx_set_mat_row(lp, i, length, indices, doubles);

    89       delete [] indices;

    90       delete [] doubles;

    91     }

    92     /// \e

    93     virtual void _getRowCoeffs(int i, 

    94 			       std::vector<std::pair<int, double> >& coeffs) {

    95       int mem_length=1+colNum();

    96       int* indices = new int[mem_length];

    97       double* doubles = new double[mem_length];

    98       int length=lpx_get_mat_row(lp, i, indices, doubles);

    99       for (int i=1; i<=length; ++i) {

   100 	coeffs.push_back(std::make_pair(indices[i], doubles[i]));

   101       }

   102       delete [] indices;

   103       delete [] doubles;

   104     }

   105     /// \e

   106     virtual void _setColCoeffs(int i, 

   107 			       const std::vector<std::pair<int, double> >& coeffs) {

   108       int mem_length=1+rowNum();

   109       int* indices = new int[mem_length];

   110       double* doubles = new double[mem_length];

   111       int length=0;

   112       for (std::vector<std::pair<int, double> >::

   113 	     const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {

   114 	++length;

   115 	indices[length]=it->first;

   116 	doubles[length]=it->second;

   117       }

   118       lpx_set_mat_col(lp, i, length, indices, doubles);

   119       delete [] indices;

   120       delete [] doubles;

   121     }

   122     /// \e

   123     virtual void _getColCoeffs(int i, 

   124 			       std::vector<std::pair<int, double> >& coeffs) {

   125       int mem_length=1+rowNum();

   126       int* indices = new int[mem_length];

   127       double* doubles = new double[mem_length];

   128       int length=lpx_get_mat_col(lp, i, indices, doubles);

   129       for (int i=1; i<=length; ++i) {

   130 	coeffs.push_back(std::make_pair(indices[i], doubles[i]));

   131       }

   132       delete [] indices;

   133       delete [] doubles;

   134     }

   135     /// \e

   136     virtual void _eraseCol(int i) {

   137       int cols[2];

   138       cols[1]=i;

   139       lpx_del_cols(lp, 1, cols);

   140     }

   141     virtual void _eraseRow(int i) {

   142       int rows[2];

   143       rows[1]=i;

   144       lpx_del_rows(lp, 1, rows);

   145     }

   146 

   147     void _setCoeff(int row, int col, double value) {

   148       ///FIXME Of course this is not efficient at all, but GLPK knows not more.

   149       /// First approach: get one row, apply changes and set it again

   150 

   151       int mem_length=1+colNum();

   152       int* indices = new int[mem_length];

   153       double* doubles = new double[mem_length];

   154 

   155 

   156       int length=lpx_get_mat_row(lp, i, indices, doubles);

   157 

   158       //The following code does not suppose that the elements of the array indices are sorted

   159       int i=1;

   160       bool found=false;

   161       while (i <= length && !found){

   162 	if (indices[i]=col){

   163 	  found = true;

   164 	  doubles[i]=value;

   165 	}

   166 	++i;

   167       }

   168       if (!found){

   169 	++length;

   170 	indices[length]=col;

   171 	doubles[length]=value;

   172       }

   173 

   174 // This is a piece of code that assumes that the array 'indices' is sorted. 

   175 // Not ready, I suppose. 

   176 //       //We need another arrays to put the data back, anyway

   177 //       int* new_indices = new int[length+1];

   178 //       double* new_doubles = new double[length+1];

   179 //       int offset;

   180 

   181 //       int i=1;

   182 //       while (i <= length && indices[i]<col){

   183 // 	new_indiced[i]=indices[i];

   184 // 	new_doubles[i]=doubles[i];

   185 // 	++i;

   186 //       }

   187 //       if (i>length || indices[i]>col){

   188 // 	//Ha atugrottuk, vagy a vegen van

   189 // 	new_indices[i]=col;

   190 // 	new_doubles[i]=value;

   191 // 	offset = 1;

   192 //       }

   193 //       else{

   194 // 	//I.e.: indices[i]=col

   195 // 	new_doubles[i]=value;

   196 // 	offset = 0;

   197 // 	++i;

   198 //       }

   199 //       while (i <= length){

   200 // 	new_indices[i+offset]=indices[i];

   201 // 	new_values[i+offset]=values[i];

   202 //       }

   203 

   204       lpx_set_mat_row(lp, row, length, indices, doubles);

   205       delete [] indices;

   206       delete [] doubles;

   207 

   208 //       lpx_set_mat_row(lp, row, length+offset, new_indices, new_doubles);

   209 //       delete [] new_indices;

   210 //       delete [] new_doubles;

   211       

   212 

   213     }

   214     double _getCoeff(int col, int row) {

   215       /// FIXME not yet implemented

   216       return 0.0;

   217     }

   218     virtual void _setColLowerBound(int i, double lo) {

   219       if (lo==INF) {

   220 	//FIXME error

   221       }

   222       int b=lpx_get_col_type(lp, i);

   223       double up=lpx_get_col_ub(lp, i);	

   224       if (lo==-INF) {

   225 	switch (b) {

   226 	case LPX_FR:

   227 	case LPX_LO:

   228 	  lpx_set_col_bnds(lp, i, LPX_FR, lo, up);

   229 	  break;

   230 	case LPX_UP:

   231 	  break;

   232 	case LPX_DB:

   233 	case LPX_FX:

   234 	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   235 	  break;

   236 	default: ;

   237 	  //FIXME error

   238 	}

   239       } else {

   240 	switch (b) {

   241 	case LPX_FR:

   242 	case LPX_LO:

   243 	  lpx_set_col_bnds(lp, i, LPX_LO, lo, up);

   244 	  break;

   245 	case LPX_UP:	  

   246 	case LPX_DB:

   247 	case LPX_FX:

   248 	  if (lo==up) 

   249 	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);

   250 	  else 

   251 	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);

   252 	  break;

   253 	default: ;

   254 	  //FIXME error

   255 	}

   256       }

   257     }

   258     virtual double _getColLowerBound(int i) {

   259       int b=lpx_get_col_type(lp, i);

   260       switch (b) {

   261       case LPX_FR:

   262 	return -INF;

   263       case LPX_LO:

   264 	return lpx_get_col_lb(lp, i);

   265       case LPX_UP:

   266 	return -INF;

   267       case LPX_DB:

   268       case LPX_FX:

   269 	return lpx_get_col_lb(lp, i);

   270       default: ;

   271 	//FIXME error

   272 	return 0.0;

   273       }

   274     }

   275     virtual void _setColUpperBound(int i, double up) {

   276       if (up==-INF) {

   277 	//FIXME error

   278       }

   279       int b=lpx_get_col_type(lp, i);

   280       double lo=lpx_get_col_lb(lp, i);

   281       if (up==INF) {

   282 	switch (b) {

   283 	case LPX_FR:

   284 	case LPX_LO:

   285 	  break;

   286 	case LPX_UP:

   287 	  lpx_set_col_bnds(lp, i, LPX_FR, lo, up);

   288 	  break;

   289 	case LPX_DB:

   290 	case LPX_FX:

   291 	  lpx_set_col_bnds(lp, i, LPX_LO, lo, up);

   292 	  break;

   293 	default: ;

   294 	  //FIXME error

   295 	}

   296       } else {

   297 	switch (b) {

   298 	case LPX_FR:

   299 	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   300 	case LPX_LO:

   301 	  if (lo==up) 

   302 	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);

   303 	  else

   304 	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);

   305 	  break;

   306 	case LPX_UP:

   307 	  lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   308 	  break;

   309 	case LPX_DB:

   310 	case LPX_FX:

   311 	  if (lo==up) 

   312 	    lpx_set_col_bnds(lp, i, LPX_FX, lo, up);

   313 	  else 

   314 	    lpx_set_col_bnds(lp, i, LPX_DB, lo, up);

   315 	  break;

   316 	default: ;

   317 	  //FIXME error

   318 	}

   319       }

   320     }

   321     virtual double _getColUpperBound(int i) {

   322       int b=lpx_get_col_type(lp, i);

   323       switch (b) {

   324       case LPX_FR:

   325       case LPX_LO:

   326 	return INF;

   327       case LPX_UP:

   328       case LPX_DB:

   329       case LPX_FX:

   330 	return lpx_get_col_ub(lp, i);

   331       default: ;

   332 	//FIXME error

   333 	return 0.0;

   334       }

   335     }

   336     virtual void _setRowLowerBound(int i, double lo) {

   337       if (lo==INF) {

   338 	//FIXME error

   339       }

   340       int b=lpx_get_row_type(lp, i);

   341       double up=lpx_get_row_ub(lp, i);	

   342       if (lo==-INF) {

   343 	switch (b) {

   344 	case LPX_FR:

   345 	case LPX_LO:

   346 	  lpx_set_row_bnds(lp, i, LPX_FR, lo, up);

   347 	  break;

   348 	case LPX_UP:

   349 	  break;

   350 	case LPX_DB:

   351 	case LPX_FX:

   352 	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   353 	  break;

   354 	default: ;

   355 	  //FIXME error

   356 	}

   357       } else {

   358 	switch (b) {

   359 	case LPX_FR:

   360 	case LPX_LO:

   361 	  lpx_set_row_bnds(lp, i, LPX_LO, lo, up);

   362 	  break;

   363 	case LPX_UP:	  

   364 	case LPX_DB:

   365 	case LPX_FX:

   366 	  if (lo==up) 

   367 	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);

   368 	  else 

   369 	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);

   370 	  break;

   371 	default: ;

   372 	  //FIXME error

   373 	}

   374       }

   375     }

   376     virtual double _getRowLowerBound(int i) {

   377       int b=lpx_get_row_type(lp, i);

   378       switch (b) {

   379       case LPX_FR:

   380 	return -INF;

   381       case LPX_LO:

   382 	return lpx_get_row_lb(lp, i);

   383       case LPX_UP:

   384 	return -INF;

   385       case LPX_DB:

   386       case LPX_FX:

   387 	return lpx_get_row_lb(lp, i);

   388       default: ;

   389 	//FIXME error

   390 	return 0.0;

   391       }

   392     }

   393     virtual void _setRowUpperBound(int i, double up) {

   394       if (up==-INF) {

   395 	//FIXME error

   396       }

   397       int b=lpx_get_row_type(lp, i);

   398       double lo=lpx_get_row_lb(lp, i);

   399       if (up==INF) {

   400 	switch (b) {

   401 	case LPX_FR:

   402 	case LPX_LO:

   403 	  break;

   404 	case LPX_UP:

   405 	  lpx_set_row_bnds(lp, i, LPX_FR, lo, up);

   406 	  break;

   407 	case LPX_DB:

   408 	case LPX_FX:

   409 	  lpx_set_row_bnds(lp, i, LPX_LO, lo, up);

   410 	  break;

   411 	default: ;

   412 	  //FIXME error

   413 	}

   414       } else {

   415 	switch (b) {

   416 	case LPX_FR:

   417 	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   418 	case LPX_LO:

   419 	  if (lo==up) 

   420 	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);

   421 	  else

   422 	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);

   423 	  break;

   424 	case LPX_UP:

   425 	  lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   426 	  break;

   427 	case LPX_DB:

   428 	case LPX_FX:

   429 	  if (lo==up) 

   430 	    lpx_set_row_bnds(lp, i, LPX_FX, lo, up);

   431 	  else 

   432 	    lpx_set_row_bnds(lp, i, LPX_DB, lo, up);

   433 	  break;

   434 	default: ;

   435 	  //FIXME error

   436 	}

   437       }

   438     }

   439     virtual double _getRowUpperBound(int i) {

   440       int b=lpx_get_row_type(lp, i);

   441       switch (b) {

   442       case LPX_FR:

   443       case LPX_LO:

   444 	return INF;

   445       case LPX_UP:

   446       case LPX_DB:

   447       case LPX_FX:

   448 	return lpx_get_row_ub(lp, i);

   449       default: ;

   450 	//FIXME error

   451 	return 0.0;

   452       }

   453     }

   454     /// \e

   455     virtual double _getObjCoeff(int i) { 

   456       return lpx_get_obj_coef(lp, i);

   457     }

   458     /// \e

   459     virtual void _setObjCoeff(int i, double obj_coef) { 

   460       lpx_set_obj_coef(lp, i, obj_coef);

   461     }

   462 

   463   protected:

   464     virtual double _getPrimal(int i) {

   465       return lpx_get_col_prim(lp, i);

   466     }

   467 

   468     //MIP

   469   protected:

   470     /// \e

   471     void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }

   472     /// \e

   473     void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }

   474     /// \e

   475     double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }

   476 

   477 

   478 //   public:

   479 //     /// \e

   480 //     void solveSimplex() { lpx_simplex(lp); }

   481 //     /// \e

   482 //     void solvePrimalSimplex() { lpx_simplex(lp); }

   483 //     /// \e

   484 //     void solveDualSimplex() { lpx_simplex(lp); }

   485 //     /// \e

   486 //     double getObjVal() { return lpx_get_obj_val(lp); }

   487 //     /// \e

   488 //     int warmUp() { return lpx_warm_up(lp); }

   489 //     /// \e

   490 //     void printWarmUpStatus(int i) {

   491 //       switch (i) {

   492 //       case LPX_E_OK: cout << "LPX_E_OK" << endl; break;

   493 //       case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;	

   494 //       case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;

   495 //       case LPX_E_SING: cout << "LPX_E_SING" << endl; break;

   496 //       }

   497 //     }

   498 //     /// \e

   499 //     int getPrimalStatus() { return lpx_get_prim_stat(lp); }

   500 //     /// \e

   501 //     void printPrimalStatus(int i) {

   502 //       switch (i) {

   503 //       case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;

   504 //       case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;	

   505 //       case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;

   506 //       case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;

   507 //       }

   508 //     }

   509 //     /// \e

   510 //     int getDualStatus() { return lpx_get_dual_stat(lp); }

   511 //     /// \e

   512 //     void printDualStatus(int i) {

   513 //       switch (i) {

   514 //       case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;

   515 //       case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;	

   516 //       case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;

   517 //       case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;

   518 //       }

   519 //     }

   520 //     /// Returns the status of the slack variable assigned to row \c row.

   521 //     int getRowStat(const Row& row) { 

   522 //       return lpx_get_row_stat(lp, row_iter_map[row]); 

   523 //     }

   524 //     /// \e

   525 //     void printRowStatus(int i) {

   526 //       switch (i) {

   527 //       case LPX_BS: cout << "LPX_BS" << endl; break;

   528 //       case LPX_NL: cout << "LPX_NL" << endl; break;	

   529 //       case LPX_NU: cout << "LPX_NU" << endl; break;

   530 //       case LPX_NF: cout << "LPX_NF" << endl; break;

   531 //       case LPX_NS: cout << "LPX_NS" << endl; break;

   532 //       }

   533 //     }

   534 //     /// Returns the status of the variable assigned to column \c col.

   535 //     int getColStat(const Col& col) { 

   536 //       return lpx_get_col_stat(lp, col_iter_map[col]); 

   537 //     }

   538 //     /// \e

   539 //     void printColStatus(int i) {

   540 //       switch (i) {

   541 //       case LPX_BS: cout << "LPX_BS" << endl; break;

   542 //       case LPX_NL: cout << "LPX_NL" << endl; break;	

   543 //       case LPX_NU: cout << "LPX_NU" << endl; break;

   544 //       case LPX_NF: cout << "LPX_NF" << endl; break;

   545 //       case LPX_NS: cout << "LPX_NS" << endl; break;

   546 //       }

   547 //     }

   548 

   549 //     // MIP

   550 //     /// \e

   551 //     void solveBandB() { lpx_integer(lp); }

   552 //     /// \e

   553 //     void setLP() { lpx_set_class(lp, LPX_LP); }

   554 //     /// \e

   555 //     void setMIP() { lpx_set_class(lp, LPX_MIP); }

   556 

   557 

   558 

   559   };

   560   

   561   /// @}

   562 

   563 } //namespace lemon

   564 

   565 #endif //LEMON_LP_SOLVER_GLPK_H
lemon-0.x