lemon-0.x: src/work/athos/lp/lp_solver

     1 // -*- c++ -*-

     2 #ifndef LEMON_LP_SOLVER_GLPK_H

     3 #define LEMON_LP_SOLVER_GLPK_H

     5 ///\ingroup misc

     6 ///\file

     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 }

    19 /* #include <iostream> */

    20 /* #include <vector> */

    21 /* #include <string> */

    22 /* #include <list> */

    23 /* #include <memory> */

    24 /* #include <utility> */

    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>

    34 using std::cout;

    35 using std::cin;

    36 using std::endl;

    38 namespace lemon {

    41   template <typename Value>

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

    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;

    52   public:

    53     /// \e

    54     LPX* lp;

    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     }

    69     //MATRIX INDEPEDENT MANIPULATING FUNCTIONS

    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     }

    80     //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS

    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 Of course this is not efficient at all, but GLPK knows not more.

   168       int change_this;

   169       bool get_set_row;

   170       //The only thing we can do is optimize on whether working with a row

   171       //or a coloumn

   172       int row_num = rowNum();

   173       int col_num = colNum();

   174       if (col_num<row_num){

   175 	//There are more rows than coloumns

   176 	get_set_row=true;

   177 	int mem_length=1+row_num;

   178 	int* indices = new int[mem_length];

   179 	double* doubles = new double[mem_length];

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

   181       }else{

   182 	get_set_row=false;

   183 	int mem_length=1+col_num;

   184 	int* indices = new int[mem_length];

   185 	double* doubles = new double[mem_length];

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

   187       }

   188       //Itten

   189 int* indices = new int[mem_length];

   190       double* doubles = new double[mem_length];

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

   193       delete [] indices;

   194       delete [] doubles;

   196     }

   197     double _getCoeff(int col, int row) {

   198       /// FIXME not yet implemented

   199       return 0.0;

   200     }

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

   202       if (lo==INF) {

   203 	//FIXME error

   204       }

   205       int b=lpx_get_col_type(lp, i);

   206       double up=lpx_get_col_ub(lp, i);

   207       if (lo==-INF) {

   208 	switch (b) {

   209 	case LPX_FR:

   210 	case LPX_LO:

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

   212 	  break;

   213 	case LPX_UP:

   214 	  break;

   215 	case LPX_DB:

   216 	case LPX_FX:

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

   218 	  break;

   219 	default: ;

   220 	  //FIXME error

   221 	}

   222       } else {

   223 	switch (b) {

   224 	case LPX_FR:

   225 	case LPX_LO:

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

   227 	  break;

   228 	case LPX_UP:

   229 	case LPX_DB:

   230 	case LPX_FX:

   231 	  if (lo==up)

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

   233 	  else

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

   235 	  break;

   236 	default: ;

   237 	  //FIXME error

   238 	}

   239       }

   240     }

   241     virtual double _getColLowerBound(int i) {

   242       int b=lpx_get_col_type(lp, i);

   243       switch (b) {

   244       case LPX_FR:

   245 	return -INF;

   246       case LPX_LO:

   247 	return lpx_get_col_lb(lp, i);

   248       case LPX_UP:

   249 	return -INF;

   250       case LPX_DB:

   251       case LPX_FX:

   252 	return lpx_get_col_lb(lp, i);

   253       default: ;

   254 	//FIXME error

   255 	return 0.0;

   256       }

   257     }

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

   259       if (up==-INF) {

   260 	//FIXME error

   261       }

   262       int b=lpx_get_col_type(lp, i);

   263       double lo=lpx_get_col_lb(lp, i);

   264       if (up==INF) {

   265 	switch (b) {

   266 	case LPX_FR:

   267 	case LPX_LO:

   268 	  break;

   269 	case LPX_UP:

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

   271 	  break;

   272 	case LPX_DB:

   273 	case LPX_FX:

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

   275 	  break;

   276 	default: ;

   277 	  //FIXME error

   278 	}

   279       } else {

   280 	switch (b) {

   281 	case LPX_FR:

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

   283 	case LPX_LO:

   284 	  if (lo==up)

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

   286 	  else

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

   288 	  break;

   289 	case LPX_UP:

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

   291 	  break;

   292 	case LPX_DB:

   293 	case LPX_FX:

   294 	  if (lo==up)

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

   296 	  else

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

   298 	  break;

   299 	default: ;

   300 	  //FIXME error

   301 	}

   302       }

   303     }

   304     virtual double _getColUpperBound(int i) {

   305       int b=lpx_get_col_type(lp, i);

   306       switch (b) {

   307       case LPX_FR:

   308       case LPX_LO:

   309 	return INF;

   310       case LPX_UP:

   311       case LPX_DB:

   312       case LPX_FX:

   313 	return lpx_get_col_ub(lp, i);

   314       default: ;

   315 	//FIXME error

   316 	return 0.0;

   317       }

   318     }

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

   320       if (lo==INF) {

   321 	//FIXME error

   322       }

   323       int b=lpx_get_row_type(lp, i);

   324       double up=lpx_get_row_ub(lp, i);

   325       if (lo==-INF) {

   326 	switch (b) {

   327 	case LPX_FR:

   328 	case LPX_LO:

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

   330 	  break;

   331 	case LPX_UP:

   332 	  break;

   333 	case LPX_DB:

   334 	case LPX_FX:

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

   336 	  break;

   337 	default: ;

   338 	  //FIXME error

   339 	}

   340       } else {

   341 	switch (b) {

   342 	case LPX_FR:

   343 	case LPX_LO:

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

   345 	  break;

   346 	case LPX_UP:

   347 	case LPX_DB:

   348 	case LPX_FX:

   349 	  if (lo==up)

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

   351 	  else

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

   353 	  break;

   354 	default: ;

   355 	  //FIXME error

   356 	}

   357       }

   358     }

   359     virtual double _getRowLowerBound(int i) {

   360       int b=lpx_get_row_type(lp, i);

   361       switch (b) {

   362       case LPX_FR:

   363 	return -INF;

   364       case LPX_LO:

   365 	return lpx_get_row_lb(lp, i);

   366       case LPX_UP:

   367 	return -INF;

   368       case LPX_DB:

   369       case LPX_FX:

   370 	return lpx_get_row_lb(lp, i);

   371       default: ;

   372 	//FIXME error

   373 	return 0.0;

   374       }

   375     }

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

   377       if (up==-INF) {

   378 	//FIXME error

   379       }

   380       int b=lpx_get_row_type(lp, i);

   381       double lo=lpx_get_row_lb(lp, i);

   382       if (up==INF) {

   383 	switch (b) {

   384 	case LPX_FR:

   385 	case LPX_LO:

   386 	  break;

   387 	case LPX_UP:

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

   389 	  break;

   390 	case LPX_DB:

   391 	case LPX_FX:

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

   393 	  break;

   394 	default: ;

   395 	  //FIXME error

   396 	}

   397       } else {

   398 	switch (b) {

   399 	case LPX_FR:

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

   401 	case LPX_LO:

   402 	  if (lo==up)

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

   404 	  else

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

   406 	  break;

   407 	case LPX_UP:

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

   409 	  break;

   410 	case LPX_DB:

   411 	case LPX_FX:

   412 	  if (lo==up)

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

   414 	  else

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

   416 	  break;

   417 	default: ;

   418 	  //FIXME error

   419 	}

   420       }

   421     }

   422     virtual double _getRowUpperBound(int i) {

   423       int b=lpx_get_row_type(lp, i);

   424       switch (b) {

   425       case LPX_FR:

   426       case LPX_LO:

   427 	return INF;

   428       case LPX_UP:

   429       case LPX_DB:

   430       case LPX_FX:

   431 	return lpx_get_row_ub(lp, i);

   432       default: ;

   433 	//FIXME error

   434 	return 0.0;

   435       }

   436     }

   437     /// \e

   438     virtual double _getObjCoeff(int i) {

   439       return lpx_get_obj_coef(lp, i);

   440     }

   441     /// \e

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

   443       lpx_set_obj_coef(lp, i, obj_coef);

   444     }

   445   public:

   446     /// \e

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

   448     /// \e

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

   450     /// \e

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

   452   protected:

   453     virtual double _getPrimal(int i) {

   454       return lpx_get_col_prim(lp, i);

   455     }

   456   public:

   457     /// \e

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

   459     /// \e

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

   461     /// \e

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

   463     /// \e

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

   465     /// \e

   466     void printWarmUpStatus(int i) {

   467       switch (i) {

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

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

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

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

   472       }

   473     }

   474     /// \e

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

   476     /// \e

   477     void printPrimalStatus(int i) {

   478       switch (i) {

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

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

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

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

   483       }

   484     }

   485     /// \e

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

   487     /// \e

   488     void printDualStatus(int i) {

   489       switch (i) {

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

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

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

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

   494       }

   495     }

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

   497     int getRowStat(const Row& row) {

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

   499     }

   500     /// \e

   501     void printRowStatus(int i) {

   502       switch (i) {

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

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

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

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

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

   508       }

   509     }

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

   511     int getColStat(const Col& col) {

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

   513     }

   514     /// \e

   515     void printColStatus(int i) {

   516       switch (i) {

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

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

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

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

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

   522       }

   523     }

   525     // MIP

   526     /// \e

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

   528     /// \e

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

   530     /// \e

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

   532   protected:

   533     /// \e

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

   535     /// \e

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

   537     /// \e

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

   539   };

   541   /// @}

   543 } //namespace lemon

   545 #endif //LEMON_LP_SOLVER_GLPK_H

author	athos
	Tue, 22 Mar 2005 16:49:30 +0000
changeset 1243	41caee260bd4
parent 1241	dadc9987c537
permissions	-rw-r--r--