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 marci
Tue, 22 Mar 2005 16:00:00 +0000
changeset 1242 e48c4fe47aaf
child 1243 41caee260bd4
permissions -rw-r--r--
small improvment in documentation 
     1 // -*- c++ -*-

     2 #ifndef LEMON_LP_SOLVER_GLPK_H

     3 #define LEMON_LP_SOLVER_GLPK_H

     4 

     5 ///\ingroup misc

     6 ///\file

     7 

     8 // #include <stdio.h>

     9 /* #include <stdlib.h> */

    10 /* #include <iostream> */

    11 /* #include <map> */

    12 /* #include <limits> */

    13 // #include <stdio>

    14 //#include <stdlib>

    15 extern "C" {

    16 #include "glpk.h"

    17 }

    18 

    19 /* #include <iostream> */

    20 /* #include <vector> */

    21 /* #include <string> */

    22 /* #include <list> */

    23 /* #include <memory> */

    24 /* #include <utility> */

    25 

    26 //#include <lemon/invalid.h>

    27 //#include <expression.h>

    28 #include <lp_solver_base.h>

    29 //#include <stp.h>

    30 //#include <lemon/max_flow.h>

    31 //#include <augmenting_flow.h>

    32 //#include <iter_map.h>

    33 

    34 using std::cout;

    35 using std::cin;

    36 using std::endl;

    37 

    38 namespace lemon {

    39   

    40   

    41   template <typename Value>

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

    43 

    44 

    45   /// \brief Wrapper for GLPK solver

    46   /// 

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

    48   class LpGlpk : public LpSolverBase<double> {

    49   public:

    50     typedef LpSolverBase<double> Parent;

    51 

    52   public:

    53     /// \e

    54     LPX* lp;

    55 

    56   public:

    57     /// \e

    58     LpGlpk() : Parent(), 

    59 			lp(lpx_create_prob()) {

    60       int_row_map.push_back(Row());

    61       int_col_map.push_back(Col());

    62       lpx_set_int_parm(lp, LPX_K_DUAL, 1);

    63     }

    64     /// \e

    65     ~LpGlpk() {

    66       lpx_delete_prob(lp);

    67     }

    68 

    69     //MATRIX INDEPEDENT MANIPULATING FUNCTIONS

    70 

    71     /// \e

    72     void setMinimize() { 

    73       lpx_set_obj_dir(lp, LPX_MIN);

    74     }

    75     /// \e

    76     void setMaximize() { 

    77       lpx_set_obj_dir(lp, LPX_MAX);

    78     }

    79 

    80     //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS

    81 

    82   protected:

    83     /// \e

    84     int _addCol() { 

    85       int i=lpx_add_cols(lp, 1);

    86       _setColLowerBound(i, -INF);

    87       _setColUpperBound(i, INF);

    88       return i;

    89     }

    90     /// \e

    91     int _addRow() { 

    92       int i=lpx_add_rows(lp, 1);

    93       return i;

    94     }

    95     /// \e

    96     virtual void _setRowCoeffs(int i, 

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

    98       int mem_length=1+colNum();

    99       int* indices = new int[mem_length];

   100       double* doubles = new double[mem_length];

   101       int length=0;

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

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

   104 	++length;

   105 	indices[length]=it->first;

   106 	doubles[length]=it->second;

   107       }

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

   109       delete [] indices;

   110       delete [] doubles;

   111     }

   112     /// \e

   113     virtual void _getRowCoeffs(int i, 

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

   115       int mem_length=1+colNum();

   116       int* indices = new int[mem_length];

   117       double* doubles = new double[mem_length];

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

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

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

   121       }

   122       delete [] indices;

   123       delete [] doubles;

   124     }

   125     /// \e

   126     virtual void _setColCoeffs(int i, 

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

   128       int mem_length=1+rowNum();

   129       int* indices = new int[mem_length];

   130       double* doubles = new double[mem_length];

   131       int length=0;

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

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

   134 	++length;

   135 	indices[length]=it->first;

   136 	doubles[length]=it->second;

   137       }

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

   139       delete [] indices;

   140       delete [] doubles;

   141     }

   142     /// \e

   143     virtual void _getColCoeffs(int i, 

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

   145       int mem_length=1+rowNum();

   146       int* indices = new int[mem_length];

   147       double* doubles = new double[mem_length];

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

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

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

   151       }

   152       delete [] indices;

   153       delete [] doubles;

   154     }

   155     /// \e

   156     virtual void _eraseCol(int i) {

   157       int cols[2];

   158       cols[1]=i;

   159       lpx_del_cols(lp, 1, cols);

   160     }

   161     virtual void _eraseRow(int i) {

   162       int rows[2];

   163       rows[1]=i;

   164       lpx_del_rows(lp, 1, rows);

   165     }

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

   167       /// FIXME not yet implemented

   168     }

   169     double _getCoeff(int col, int row) {

   170       /// FIXME not yet implemented

   171       return 0.0;

   172     }

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

   174       if (lo==INF) {

   175 	//FIXME error

   176       }

   177       int b=lpx_get_col_type(lp, i);

   178       double up=lpx_get_col_ub(lp, i);	

   179       if (lo==-INF) {

   180 	switch (b) {

   181 	case LPX_FR:

   182 	case LPX_LO:

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

   184 	  break;

   185 	case LPX_UP:

   186 	  break;

   187 	case LPX_DB:

   188 	case LPX_FX:

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

   190 	  break;

   191 	default: ;

   192 	  //FIXME error

   193 	}

   194       } else {

   195 	switch (b) {

   196 	case LPX_FR:

   197 	case LPX_LO:

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

   199 	  break;

   200 	case LPX_UP:	  

   201 	case LPX_DB:

   202 	case LPX_FX:

   203 	  if (lo==up) 

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

   205 	  else 

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

   207 	  break;

   208 	default: ;

   209 	  //FIXME error

   210 	}

   211       }

   212     }

   213     virtual double _getColLowerBound(int i) {

   214       int b=lpx_get_col_type(lp, i);

   215       switch (b) {

   216       case LPX_FR:

   217 	return -INF;

   218       case LPX_LO:

   219 	return lpx_get_col_lb(lp, i);

   220       case LPX_UP:

   221 	return -INF;

   222       case LPX_DB:

   223       case LPX_FX:

   224 	return lpx_get_col_lb(lp, i);

   225       default: ;

   226 	//FIXME error

   227 	return 0.0;

   228       }

   229     }

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

   231       if (up==-INF) {

   232 	//FIXME error

   233       }

   234       int b=lpx_get_col_type(lp, i);

   235       double lo=lpx_get_col_lb(lp, i);

   236       if (up==INF) {

   237 	switch (b) {

   238 	case LPX_FR:

   239 	case LPX_LO:

   240 	  break;

   241 	case LPX_UP:

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

   243 	  break;

   244 	case LPX_DB:

   245 	case LPX_FX:

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

   247 	  break;

   248 	default: ;

   249 	  //FIXME error

   250 	}

   251       } else {

   252 	switch (b) {

   253 	case LPX_FR:

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

   255 	case LPX_LO:

   256 	  if (lo==up) 

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

   258 	  else

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

   260 	  break;

   261 	case LPX_UP:

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

   263 	  break;

   264 	case LPX_DB:

   265 	case LPX_FX:

   266 	  if (lo==up) 

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

   268 	  else 

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

   270 	  break;

   271 	default: ;

   272 	  //FIXME error

   273 	}

   274       }

   275     }

   276     virtual double _getColUpperBound(int i) {

   277       int b=lpx_get_col_type(lp, i);

   278       switch (b) {

   279       case LPX_FR:

   280       case LPX_LO:

   281 	return INF;

   282       case LPX_UP:

   283       case LPX_DB:

   284       case LPX_FX:

   285 	return lpx_get_col_ub(lp, i);

   286       default: ;

   287 	//FIXME error

   288 	return 0.0;

   289       }

   290     }

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

   292       if (lo==INF) {

   293 	//FIXME error

   294       }

   295       int b=lpx_get_row_type(lp, i);

   296       double up=lpx_get_row_ub(lp, i);	

   297       if (lo==-INF) {

   298 	switch (b) {

   299 	case LPX_FR:

   300 	case LPX_LO:

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

   302 	  break;

   303 	case LPX_UP:

   304 	  break;

   305 	case LPX_DB:

   306 	case LPX_FX:

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

   308 	  break;

   309 	default: ;

   310 	  //FIXME error

   311 	}

   312       } else {

   313 	switch (b) {

   314 	case LPX_FR:

   315 	case LPX_LO:

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

   317 	  break;

   318 	case LPX_UP:	  

   319 	case LPX_DB:

   320 	case LPX_FX:

   321 	  if (lo==up) 

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

   323 	  else 

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

   325 	  break;

   326 	default: ;

   327 	  //FIXME error

   328 	}

   329       }

   330     }

   331     virtual double _getRowLowerBound(int i) {

   332       int b=lpx_get_row_type(lp, i);

   333       switch (b) {

   334       case LPX_FR:

   335 	return -INF;

   336       case LPX_LO:

   337 	return lpx_get_row_lb(lp, i);

   338       case LPX_UP:

   339 	return -INF;

   340       case LPX_DB:

   341       case LPX_FX:

   342 	return lpx_get_row_lb(lp, i);

   343       default: ;

   344 	//FIXME error

   345 	return 0.0;

   346       }

   347     }

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

   349       if (up==-INF) {

   350 	//FIXME error

   351       }

   352       int b=lpx_get_row_type(lp, i);

   353       double lo=lpx_get_row_lb(lp, i);

   354       if (up==INF) {

   355 	switch (b) {

   356 	case LPX_FR:

   357 	case LPX_LO:

   358 	  break;

   359 	case LPX_UP:

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

   361 	  break;

   362 	case LPX_DB:

   363 	case LPX_FX:

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

   365 	  break;

   366 	default: ;

   367 	  //FIXME error

   368 	}

   369       } else {

   370 	switch (b) {

   371 	case LPX_FR:

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

   373 	case LPX_LO:

   374 	  if (lo==up) 

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

   376 	  else

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

   378 	  break;

   379 	case LPX_UP:

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

   381 	  break;

   382 	case LPX_DB:

   383 	case LPX_FX:

   384 	  if (lo==up) 

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

   386 	  else 

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

   388 	  break;

   389 	default: ;

   390 	  //FIXME error

   391 	}

   392       }

   393     }

   394     virtual double _getRowUpperBound(int i) {

   395       int b=lpx_get_row_type(lp, i);

   396       switch (b) {

   397       case LPX_FR:

   398       case LPX_LO:

   399 	return INF;

   400       case LPX_UP:

   401       case LPX_DB:

   402       case LPX_FX:

   403 	return lpx_get_row_ub(lp, i);

   404       default: ;

   405 	//FIXME error

   406 	return 0.0;

   407       }

   408     }

   409     /// \e

   410     virtual double _getObjCoeff(int i) { 

   411       return lpx_get_obj_coef(lp, i);

   412     }

   413     /// \e

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

   415       lpx_set_obj_coef(lp, i, obj_coef);

   416     }

   417   public:

   418     /// \e

   419     void solveSimplex() { lpx_simplex(lp); }

   420     /// \e

   421     void solvePrimalSimplex() { lpx_simplex(lp); }

   422     /// \e

   423     void solveDualSimplex() { lpx_simplex(lp); }

   424   protected:

   425     virtual double _getPrimal(int i) {

   426       return lpx_get_col_prim(lp, i);

   427     }

   428   public:

   429     /// \e

   430     double getObjVal() { return lpx_get_obj_val(lp); }

   431     /// \e

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

   433     /// \e

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

   435     /// \e

   436     int warmUp() { return lpx_warm_up(lp); }

   437     /// \e

   438     void printWarmUpStatus(int i) {

   439       switch (i) {

   440       case LPX_E_OK: cout << "LPX_E_OK" << endl; break;

   441       case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;	

   442       case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;

   443       case LPX_E_SING: cout << "LPX_E_SING" << endl; break;

   444       }

   445     }

   446     /// \e

   447     int getPrimalStatus() { return lpx_get_prim_stat(lp); }

   448     /// \e

   449     void printPrimalStatus(int i) {

   450       switch (i) {

   451       case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;

   452       case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;	

   453       case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;

   454       case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;

   455       }

   456     }

   457     /// \e

   458     int getDualStatus() { return lpx_get_dual_stat(lp); }

   459     /// \e

   460     void printDualStatus(int i) {

   461       switch (i) {

   462       case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;

   463       case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;	

   464       case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;

   465       case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;

   466       }

   467     }

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

   469     int getRowStat(const Row& row) { 

   470       return lpx_get_row_stat(lp, row_iter_map[row]); 

   471     }

   472     /// \e

   473     void printRowStatus(int i) {

   474       switch (i) {

   475       case LPX_BS: cout << "LPX_BS" << endl; break;

   476       case LPX_NL: cout << "LPX_NL" << endl; break;	

   477       case LPX_NU: cout << "LPX_NU" << endl; break;

   478       case LPX_NF: cout << "LPX_NF" << endl; break;

   479       case LPX_NS: cout << "LPX_NS" << endl; break;

   480       }

   481     }

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

   483     int getColStat(const Col& col) { 

   484       return lpx_get_col_stat(lp, col_iter_map[col]); 

   485     }

   486     /// \e

   487     void printColStatus(int i) {

   488       switch (i) {

   489       case LPX_BS: cout << "LPX_BS" << endl; break;

   490       case LPX_NL: cout << "LPX_NL" << endl; break;	

   491       case LPX_NU: cout << "LPX_NU" << endl; break;

   492       case LPX_NF: cout << "LPX_NF" << endl; break;

   493       case LPX_NS: cout << "LPX_NS" << endl; break;

   494       }

   495     }

   496 

   497     // MIP

   498     /// \e

   499     void solveBandB() { lpx_integer(lp); }

   500     /// \e

   501     void setLP() { lpx_set_class(lp, LPX_LP); }

   502     /// \e

   503     void setMIP() { lpx_set_class(lp, LPX_MIP); }

   504   protected:

   505     /// \e

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

   507     /// \e

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

   509     /// \e

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

   511   };

   512   

   513   /// @}

   514 

   515 } //namespace lemon

   516 

   517 #endif //LEMON_LP_SOLVER_GLPK_H
lemon-0.x