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

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

     2 #ifndef LEMON_LP_SOLVER_WRAPPER_H

     3 #define LEMON_LP_SOLVER_WRAPPER

     5 ///\ingroup misc

     6 ///\file

     7 ///\brief Dijkstra algorithm.

     9 // #include <stdio.h>

    10 #include <stdlib.h>

    11 // #include <stdio>

    12 //#include <stdlib>

    13 extern "C" {

    14 #include "glpk.h"

    15 }

    17 #include <iostream>

    18 #include <vector>

    19 #include <string>

    20 #include <list>

    21 #include <memory>

    22 #include <utility>

    24 //#include <sage_graph.h>

    25 //#include <lemon/list_graph.h>

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

    27 #include <lemon/invalid.h>

    28 //#include <bfs_dfs.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   /// \addtogroup misc

    42   /// @{

    44   /// \brief A partitioned vector with iterable classes.

    45   ///

    46   /// This class implements a container in which the data is stored in an

    47   /// stl vector, the range is partitioned into sets and each set is

    48   /// doubly linked in a list.

    49   /// That is, each class is iterable by lemon iterators, and any member of

    50   /// the vector can bo moved to an other class.

    51   template <typename T>

    52   class IterablePartition {

    53   protected:

    54     struct Node {

    55       T data;

    56       int prev; //invalid az -1

    57       int next;

    58     };

    59     std::vector<Node> nodes;

    60     struct Tip {

    61       int first;

    62       int last;

    63     };

    64     std::vector<Tip> tips;

    65   public:

    66     /// The classes are indexed by integers from \c 0 to \c classNum()-1.

    67     int classNum() const { return tips.size(); }

    68     /// This lemon style iterator iterates through a class.

    69     class ClassIt;

    70     /// Constructor. The number of classes is to be given which is fixed

    71     /// over the life of the container.

    72     /// The partition classes are indexed from 0 to class_num-1.

    73     IterablePartition(int class_num) {

    74       for (int i=0; i<class_num; ++i) {

    75 	Tip t;

    76 	t.first=t.last=-1;

    77 	tips.push_back(t);

    78       }

    79     }

    80   protected:

    81     void befuz(ClassIt it, int class_id) {

    82       if (tips[class_id].first==-1) {

    83 	if (tips[class_id].last==-1) {

    84 	  nodes[it.i].prev=nodes[it.i].next=-1;

    85 	  tips[class_id].first=tips[class_id].last=it.i;

    86 	}

    87       } else {

    88 	nodes[it.i].prev=tips[class_id].last;

    89 	nodes[it.i].next=-1;

    90 	nodes[tips[class_id].last].next=it.i;

    91 	tips[class_id].last=it.i;

    92       }

    93     }

    94     void kifuz(ClassIt it, int class_id) {

    95       if (tips[class_id].first==it.i) {

    96 	if (tips[class_id].last==it.i) {

    97 	  tips[class_id].first=tips[class_id].last=-1;

    98 	} else {

    99 	  tips[class_id].first=nodes[it.i].next;

   100 	  nodes[nodes[it.i].next].prev=-1;

   101 	}

   102       } else {

   103 	if (tips[class_id].last==it.i) {

   104 	  tips[class_id].last=nodes[it.i].prev;

   105 	  nodes[nodes[it.i].prev].next=-1;

   106 	} else {

   107 	  nodes[nodes[it.i].next].prev=nodes[it.i].prev;

   108 	  nodes[nodes[it.i].prev].next=nodes[it.i].next;

   109 	}

   110       }

   111     }

   112   public:

   113     /// A new element with data \c t is pushed into the vector and into class

   114     /// \c class_id.

   115     ClassIt push_back(const T& t, int class_id) {

   116       Node n;

   117       n.data=t;

   118       nodes.push_back(n);

   119       int i=nodes.size()-1;

   120       befuz(i, class_id);

   121       return i;

   122     }

   123     /// A member is moved to an other class.

   124     void set(ClassIt it, int old_class_id, int new_class_id) {

   125       kifuz(it.i, old_class_id);

   126       befuz(it.i, new_class_id);

   127     }

   128     /// Returns the data pointed by \c it.

   129     T& operator[](ClassIt it) { return nodes[it.i].data; }

   130     /// Returns the data pointed by \c it.

   131     const T& operator[](ClassIt it) const { return nodes[it.i].data; }

   132     ///.

   133     class ClassIt {

   134       friend class IterablePartition;

   135     protected:

   136       int i;

   137     public:

   138       /// Default constructor.

   139       ClassIt() { }

   140       /// This constructor constructs an iterator which points

   141       /// to the member of th container indexed by the integer _i.

   142       ClassIt(const int& _i) : i(_i) { }

   143       /// Invalid constructor.

   144       ClassIt(const Invalid&) : i(-1) { }

   145     };

   146     /// First member of class \c class_id.

   147     ClassIt& first(ClassIt& it, int class_id) const {

   148       it.i=tips[class_id].first;

   149       return it;

   150     }

   151     /// Next member.

   152     ClassIt& next(ClassIt& it) const {

   153       it.i=nodes[it.i].next;

   154       return it;

   155     }

   156     /// True iff the iterator is valid.

   157     bool valid(const ClassIt& it) const { return it.i!=-1; }

   158   };

   160   /// \brief Wrappers for LP solvers

   161   ///

   162   /// This class implements a lemon wrapper for glpk.

   163   /// Later other LP-solvers will be wrapped into lemon.

   164   /// The aim of this class is to give a general surface to different

   165   /// solvers, i.e. it makes possible to write algorithms using LP's,

   166   /// in which the solver can be changed to an other one easily.

   167   class LPSolverWrapper {

   168   public:

   170 //   class Row {

   171 //   protected:

   172 //     int i;

   173 //   public:

   174 //     Row() { }

   175 //     Row(const Invalid&) : i(0) { }

   176 //     Row(const int& _i) : i(_i) { }

   177 //     operator int() const { return i; }

   178 //   };

   179 //   class RowIt : public Row {

   180 //   public:

   181 //     RowIt(const Row& row) : Row(row) { }

   182 //   };

   184 //   class Col {

   185 //   protected:

   186 //     int i;

   187 //   public:

   188 //     Col() { }

   189 //     Col(const Invalid&) : i(0) { }

   190 //     Col(const int& _i) : i(_i) { }

   191 //     operator int() const { return i; }

   192 //   };

   193 //   class ColIt : public Col {

   194 //     ColIt(const Col& col) : Col(col) { }

   195 //   };

   197   public:

   198     ///.

   199     LPX* lp;

   200     ///.

   201     typedef IterablePartition<int>::ClassIt RowIt;

   202     ///.

   203     IterablePartition<int> row_iter_map;

   204     ///.

   205     typedef IterablePartition<int>::ClassIt ColIt;

   206     ///.

   207     IterablePartition<int> col_iter_map;

   208     //std::vector<int> row_id_to_lp_row_id;

   209     //std::vector<int> col_id_to_lp_col_id;

   210     ///.

   211     const int VALID_ID;

   212     ///.

   213     const int INVALID_ID;

   215   public:

   216     ///.

   217     LPSolverWrapper() : lp(lpx_create_prob()),

   218 			row_iter_map(2),

   219 			col_iter_map(2),

   220 			//row_id_to_lp_row_id(), col_id_to_lp_col_id(),

   221 			VALID_ID(0), INVALID_ID(1) {

   222       lpx_set_int_parm(lp, LPX_K_DUAL, 1);

   223     }

   224     ///.

   225     ~LPSolverWrapper() {

   226       lpx_delete_prob(lp);

   227     }

   228     ///.

   229     void setMinimize() {

   230       lpx_set_obj_dir(lp, LPX_MIN);

   231     }

   232     ///.

   233     void setMaximize() {

   234       lpx_set_obj_dir(lp, LPX_MAX);

   235     }

   236     ///.

   237     ColIt addCol() {

   238       int i=lpx_add_cols(lp, 1);

   239       ColIt col_it;

   240       col_iter_map.first(col_it, INVALID_ID);

   241       if (col_iter_map.valid(col_it)) { //van hasznalhato hely

   242 	col_iter_map.set(col_it, INVALID_ID, VALID_ID);

   243 	col_iter_map[col_it]=i;

   244 	//col_id_to_lp_col_id[col_iter_map[col_it]]=i;

   245       } else { //a cucc vegere kell inzertalni mert nincs szabad hely

   246 	//col_id_to_lp_col_id.push_back(i);

   247 	//int j=col_id_to_lp_col_id.size()-1;

   248 	col_it=col_iter_map.push_back(i, VALID_ID);

   249       }

   250 //    edge_index_map.set(e, i);

   251 //    lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);

   252 //    lpx_set_obj_coef(lp, i, cost[e]);

   253       return col_it;

   254     }

   255     ///.

   256     RowIt addRow() {

   257       int i=lpx_add_rows(lp, 1);

   258       RowIt row_it;

   259       row_iter_map.first(row_it, INVALID_ID);

   260       if (row_iter_map.valid(row_it)) { //van hasznalhato hely

   261 	row_iter_map.set(row_it, INVALID_ID, VALID_ID);

   262 	row_iter_map[row_it]=i;

   263       } else { //a cucc vegere kell inzertalni mert nincs szabad hely

   264 	row_it=row_iter_map.push_back(i, VALID_ID);

   265       }

   266       return row_it;

   267     }

   268     //pair<RowIt, double>-bol kell megadni egy std range-et

   269     ///.

   270     template <typename Begin, typename End>

   271     void setColCoeffs(const ColIt& col_it,

   272 		      Begin begin, End end) {

   273       int mem_length=1+lpx_get_num_rows(lp);

   274       int* indices = new int[mem_length];

   275       double* doubles = new double[mem_length];

   276       int length=0;

   277       for ( ; begin!=end; ++begin) {

   278 	++length;

   279 	indices[length]=row_iter_map[begin->first];

   280 	doubles[length]=begin->second;

   281       }

   282       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);

   283       delete [] indices;

   284       delete [] doubles;

   285     }

   286     //pair<ColIt, double>-bol kell megadni egy std range-et

   287     ///.

   288     template <typename Begin, typename End>

   289     void setRowCoeffs(const RowIt& row_it,

   290 		      Begin begin, End end) {

   291       int mem_length=1+lpx_get_num_cols(lp);

   292       int* indices = new int[mem_length];

   293       double* doubles = new double[mem_length];

   294       int length=0;

   295       for ( ; begin!=end; ++begin) {

   296 	++length;

   297 	indices[length]=col_iter_map[begin->first];

   298 	doubles[length]=begin->second;

   299       }

   300       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);

   301       delete [] indices;

   302       delete [] doubles;

   303     }

   304     ///.

   305     void eraseCol(const ColIt& col_it) {

   306       col_iter_map.set(col_it, VALID_ID, INVALID_ID);

   307       int cols[2];

   308       cols[1]=col_iter_map[col_it];

   309       lpx_del_cols(lp, 1, cols);

   310       col_iter_map[col_it]=0; //glpk specifikus

   311       ColIt it;

   312       for (col_iter_map.first(it, VALID_ID);

   313 	   col_iter_map.valid(it); col_iter_map.next(it)) {

   314 	if (col_iter_map[it]>cols[1]) --col_iter_map[it];

   315       }

   316     }

   317     ///.

   318     void eraseRow(const RowIt& row_it) {

   319       row_iter_map.set(row_it, VALID_ID, INVALID_ID);

   320       int rows[2];

   321       rows[1]=row_iter_map[row_it];

   322       lpx_del_rows(lp, 1, rows);

   323       row_iter_map[row_it]=0; //glpk specifikus

   324       RowIt it;

   325       for (row_iter_map.first(it, VALID_ID);

   326 	   row_iter_map.valid(it); row_iter_map.next(it)) {

   327 	if (row_iter_map[it]>rows[1]) --row_iter_map[it];

   328       }

   329     }

   330     ///.

   331     void setColBounds(const ColIt& col_it, int bound_type,

   332 		      double lo, double up) {

   333       lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);

   334     }

   335     ///.

   336     double getObjCoef(const ColIt& col_it) {

   337       return lpx_get_obj_coef(lp, col_iter_map[col_it]);

   338     }

   339     ///.

   340     void setRowBounds(const RowIt& row_it, int bound_type,

   341 		      double lo, double up) {

   342       lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);

   343     }

   344     ///.

   345     void setObjCoef(const ColIt& col_it, double obj_coef) {

   346       lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);

   347     }

   348     ///.

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

   350     ///.

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

   352     ///.

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

   354     ///.

   355     double getPrimal(const ColIt& col_it) {

   356       return lpx_get_col_prim(lp, col_iter_map[col_it]);

   357     }

   358     ///.

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

   360     ///.

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

   362     ///.

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

   364     ///.

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

   366     ///.

   367     void printWarmUpStatus(int i) {

   368       switch (i) {

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

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

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

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

   373       }

   374     }

   375     ///.

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

   377     ///.

   378     void printPrimalStatus(int i) {

   379       switch (i) {

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

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

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

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

   384       }

   385     }

   386     ///.

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

   388     ///.

   389     void printDualStatus(int i) {

   390       switch (i) {

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

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

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

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

   395       }

   396     }

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

   398     int getRowStat(const RowIt& row_it) {

   399       return lpx_get_row_stat(lp, row_iter_map[row_it]);

   400     }

   401     ///.

   402     void printRowStatus(int i) {

   403       switch (i) {

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

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

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

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

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

   409       }

   410     }

   411     /// Returns the status of the variable assigned to column \c col_it.

   412     int getColStat(const ColIt& col_it) {

   413       return lpx_get_col_stat(lp, col_iter_map[col_it]);

   414     }

   415     ///.

   416     void printColStatus(int i) {

   417       switch (i) {

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

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

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

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

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

   423       }

   424     }

   425   };

   427   /// @}

   429 } //namespace lemon

   431 #endif //LEMON_LP_SOLVER_WRAPPER_H

author	marci
	Sat, 20 Nov 2004 14:23:27 +0000
changeset 1014	aae850a2394d
parent 921	818510fa3d99
child 1015	e3bb0e118bb4
permissions	-rw-r--r--