src/work/athos/lp_old/lp_solver_base.h
author alpar
Thu, 07 Apr 2005 06:31:03 +0000
changeset 1312 48f9299b390d
parent 1241 dadc9987c537
permissions -rw-r--r--
max() [_setMax()], min() [_setMin()], primalValue() [_getPrimalValue()] added
     1 // -*- c++ -*-
     2 #ifndef LEMON_LP_SOLVER_BASE_H
     3 #define LEMON_LP_SOLVER_BASE_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 
    16 #include <iostream>
    17 #include <vector>
    18 #include <string>
    19 #include <list>
    20 #include <memory>
    21 #include <utility>
    22 
    23 #include <lemon/invalid.h>
    24 #include <expression.h>
    25 //#include <stp.h>
    26 //#include <lemon/max_flow.h>
    27 //#include <augmenting_flow.h>
    28 //#include <iter_map.h>
    29 
    30 using std::cout;
    31 using std::cin;
    32 using std::endl;
    33 
    34 namespace lemon {
    35   
    36   /// \addtogroup misc
    37   /// @{
    38 
    39   /// \brief A partitioned vector with iterable classes.
    40   ///
    41   /// This class implements a container in which the data is stored in an 
    42   /// stl vector, the range is partitioned into sets and each set is 
    43   /// doubly linked in a list. 
    44   /// That is, each class is iterable by lemon iterators, and any member of 
    45   /// the vector can bo moved to an other class.
    46   template <typename T>
    47   class IterablePartition {
    48   protected:
    49     struct Node {
    50       T data;
    51       int prev; //invalid az -1
    52       int next; 
    53     };
    54     std::vector<Node> nodes;
    55     struct Tip {
    56       int first;
    57       int last;
    58     };
    59     std::vector<Tip> tips;
    60   public:
    61     /// The classes are indexed by integers from \c 0 to \c classNum()-1.
    62     int classNum() const { return tips.size(); }
    63     /// This lemon style iterator iterates through a class. 
    64     class Class;
    65     /// Constructor. The number of classes is to be given which is fixed 
    66     /// over the life of the container. 
    67     /// The partition classes are indexed from 0 to class_num-1. 
    68     IterablePartition(int class_num) { 
    69       for (int i=0; i<class_num; ++i) {
    70 	Tip t;
    71 	t.first=t.last=-1;
    72 	tips.push_back(t);
    73       }
    74     }
    75   protected:
    76     void befuz(Class it, int class_id) {
    77       if (tips[class_id].first==-1) {
    78 	if (tips[class_id].last==-1) {
    79 	  nodes[it.i].prev=nodes[it.i].next=-1;
    80 	  tips[class_id].first=tips[class_id].last=it.i;
    81 	}
    82       } else {
    83 	nodes[it.i].prev=tips[class_id].last;
    84 	nodes[it.i].next=-1;
    85 	nodes[tips[class_id].last].next=it.i;
    86 	tips[class_id].last=it.i;
    87       }
    88     }
    89     void kifuz(Class it, int class_id) {
    90       if (tips[class_id].first==it.i) {
    91 	if (tips[class_id].last==it.i) {
    92 	  tips[class_id].first=tips[class_id].last=-1;
    93 	} else {
    94 	  tips[class_id].first=nodes[it.i].next;
    95 	  nodes[nodes[it.i].next].prev=-1;
    96 	}
    97       } else {
    98 	if (tips[class_id].last==it.i) {
    99 	  tips[class_id].last=nodes[it.i].prev;
   100 	  nodes[nodes[it.i].prev].next=-1;
   101 	} else {
   102 	  nodes[nodes[it.i].next].prev=nodes[it.i].prev;
   103 	  nodes[nodes[it.i].prev].next=nodes[it.i].next;
   104 	}
   105       }
   106     }
   107   public:
   108     /// A new element with data \c t is pushed into the vector and into class 
   109     /// \c class_id.
   110     Class push_back(const T& t, int class_id) { 
   111       Node n;
   112       n.data=t;
   113       nodes.push_back(n);
   114       int i=nodes.size()-1;
   115       befuz(i, class_id);
   116       return i;
   117     }
   118     /// A member is moved to an other class.
   119     void set(Class it, int old_class_id, int new_class_id) {
   120       kifuz(it.i, old_class_id);
   121       befuz(it.i, new_class_id);
   122     }
   123     /// Returns the data pointed by \c it.
   124     T& operator[](Class it) { return nodes[it.i].data; }
   125     /// Returns the data pointed by \c it.
   126     const T& operator[](Class it) const { return nodes[it.i].data; }
   127     ///.
   128     class Class {
   129       friend class IterablePartition;
   130     protected:
   131       int i;
   132     public:
   133       /// Default constructor.
   134       Class() { }
   135       /// This constructor constructs an iterator which points
   136       /// to the member of th container indexed by the integer _i.
   137       Class(const int& _i) : i(_i) { }
   138       /// Invalid constructor.
   139       Class(const Invalid&) : i(-1) { }
   140       friend bool operator<(const Class& x, const Class& y);
   141       friend std::ostream& operator<<(std::ostream& os, 
   142 				      const Class& it);
   143       bool operator==(const Class& node) const {return i == node.i;}
   144       bool operator!=(const Class& node) const {return i != node.i;}
   145     };
   146     friend bool operator<(const Class& x, const Class& y) {
   147       return (x.i < y.i);
   148     }
   149     friend std::ostream& operator<<(std::ostream& os, 
   150 				    const Class& it) {
   151       os << it.i;
   152       return os;
   153     }
   154     /// First member of class \c class_id.
   155     Class& first(Class& it, int class_id) const {
   156       it.i=tips[class_id].first;
   157       return it;
   158     }
   159     /// Next member.
   160     Class& next(Class& it) const {
   161       it.i=nodes[it.i].next;
   162       return it;
   163     }
   164     /// True iff the iterator is valid.
   165     bool valid(const Class& it) const { return it.i!=-1; }
   166 
   167     class ClassIt : public Class {
   168       const IterablePartition* iterable_partition;
   169     public:
   170       ClassIt() { }
   171       ClassIt(Invalid i) : Class(i) { }
   172       ClassIt(const IterablePartition& _iterable_partition, 
   173 	      const int& i) : iterable_partition(&_iterable_partition) {
   174         _iterable_partition.first(*this, i);
   175       }
   176       ClassIt(const IterablePartition& _iterable_partition, 
   177 	      const Class& _class) : 
   178 	Class(_class), iterable_partition(&_iterable_partition) { }
   179       ClassIt& operator++() {
   180         iterable_partition->next(*this);
   181         return *this;
   182       }
   183     };
   184 
   185   };
   186 
   187 
   188   /*! \e
   189     \todo kellenene uj iterable structure bele, mert ez nem az igazi
   190     \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
   191     \todo LEKERDEZESEK!!!
   192     \todo DOKSI!!!! Doxygen group!!!
   193     The aim of this class is to give a general surface to different 
   194     solvers, i.e. it makes possible to write algorithms using LP's, 
   195     in which the solver can be changed to an other one easily.
   196     \nosubgrouping
   197   */
   198   template <typename _Value>
   199   class LpSolverBase {
   200     
   201     /*! @name Uncategorized functions and types (public members)
   202     */
   203     //@{
   204   public:
   205 
   206     //UNCATEGORIZED
   207 
   208     /// \e
   209     typedef IterablePartition<int> Rows;
   210     /// \e
   211     typedef IterablePartition<int> Cols;
   212     /// \e
   213     typedef _Value Value;
   214     /// \e
   215     typedef Rows::Class Row;
   216     /// \e
   217     typedef Cols::Class Col;
   218   public:
   219     /// \e
   220     IterablePartition<int> row_iter_map;
   221     /// \e
   222     IterablePartition<int> col_iter_map;
   223     /// \e
   224     std::vector<Row> int_row_map;
   225     /// \e
   226     std::vector<Col> int_col_map;
   227     /// \e
   228     const int VALID_CLASS;
   229     /// \e
   230     const int INVALID_CLASS;
   231     /// \e 
   232     static const Value INF;
   233   public:
   234     /// \e
   235     LpSolverBase() : row_iter_map(2), 
   236 		     col_iter_map(2), 
   237 		     VALID_CLASS(0), INVALID_CLASS(1) { }
   238     /// \e
   239     virtual ~LpSolverBase() { }
   240     //@}
   241 
   242     /*! @name Medium level interface (public members)
   243       These functions appear in the low level and also in the high level 
   244       interfaces thus these each of these functions have to be implemented 
   245       only once in the different interfaces.
   246       This means that these functions have to be reimplemented for all of the 
   247       different lp solvers. These are basic functions, and have the same 
   248       parameter lists in the low and high level interfaces. 
   249     */
   250     //@{
   251   public:
   252 
   253     //UNCATEGORIZED FUNCTIONS
   254 
   255     /// \e
   256     virtual void setMinimize() = 0;
   257     /// \e
   258     virtual void setMaximize() = 0;
   259 
   260     //SOLVER FUNCTIONS
   261 
   262     /// \e
   263     virtual void solveSimplex() = 0;
   264     /// \e
   265     virtual void solvePrimalSimplex() = 0;
   266     /// \e
   267     virtual void solveDualSimplex() = 0;
   268 
   269     //SOLUTION RETRIEVING
   270 
   271     /// \e
   272     virtual Value getObjVal() = 0;
   273 
   274     //OTHER FUNCTIONS
   275 
   276     /// \e
   277     virtual int rowNum() const = 0;
   278     /// \e
   279     virtual int colNum() const = 0;
   280     /// \e
   281     virtual int warmUp() = 0;
   282     /// \e
   283     virtual void printWarmUpStatus(int i) = 0;
   284     /// \e
   285     virtual int getPrimalStatus() = 0;
   286     /// \e
   287     virtual void printPrimalStatus(int i) = 0;
   288     /// \e
   289     virtual int getDualStatus() = 0;
   290     /// \e
   291     virtual void printDualStatus(int i) = 0;
   292     /// Returns the status of the slack variable assigned to row \c row.
   293     virtual int getRowStat(const Row& row) = 0;
   294     /// \e
   295     virtual void printRowStatus(int i) = 0;
   296     /// Returns the status of the variable assigned to column \c col.
   297     virtual int getColStat(const Col& col) = 0;
   298     /// \e
   299     virtual void printColStatus(int i) = 0;
   300 
   301     //@}
   302 
   303     /*! @name Low level interface (protected members)
   304       Problem manipulating functions in the low level interface
   305     */
   306     //@{
   307   protected:
   308 
   309     //MATRIX MANIPULATING FUNCTIONS
   310 
   311     /// \e
   312     virtual int _addCol() = 0;
   313     /// \e
   314     virtual int _addRow() = 0;
   315     /// \e
   316     virtual void _eraseCol(int i) = 0;
   317     /// \e
   318     virtual void _eraseRow(int i) = 0;
   319     /// \e
   320     virtual void _setRowCoeffs(int i, 
   321 			       const std::vector<std::pair<int, Value> >& coeffs) = 0;
   322     /// \e
   323     /// This routine modifies \c coeffs only by the \c push_back method.
   324     virtual void _getRowCoeffs(int i, 
   325 			       std::vector<std::pair<int, Value> >& coeffs) = 0;
   326     /// \e
   327     virtual void _setColCoeffs(int i, 
   328 			       const std::vector<std::pair<int, Value> >& coeffs) = 0;
   329     /// \e
   330     /// This routine modifies \c coeffs only by the \c push_back method.
   331     virtual void _getColCoeffs(int i, 
   332 			       std::vector<std::pair<int, Value> >& coeffs) = 0;
   333     /// \e
   334     virtual void _setCoeff(int col, int row, Value value) = 0;
   335     /// \e
   336     virtual Value _getCoeff(int col, int row) = 0;
   337     //  public:
   338     //    /// \e
   339     //    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
   340   protected:
   341     /// \e
   342     /// The lower bound of a variable (column) have to be given by an 
   343     /// extended number of type Value, i.e. a finite number of type 
   344     /// Value or -INF.
   345     virtual void _setColLowerBound(int i, Value value) = 0;
   346     /// \e
   347     /// The lower bound of a variable (column) is an 
   348     /// extended number of type Value, i.e. a finite number of type 
   349     /// Value or -INF.
   350     virtual Value _getColLowerBound(int i) = 0;
   351     /// \e
   352     /// The upper bound of a variable (column) have to be given by an 
   353     /// extended number of type Value, i.e. a finite number of type 
   354     /// Value or INF.
   355     virtual void _setColUpperBound(int i, Value value) = 0;
   356     /// \e
   357     /// The upper bound of a variable (column) is an 
   358     /// extended number of type Value, i.e. a finite number of type 
   359     /// Value or INF.
   360     virtual Value _getColUpperBound(int i) = 0;
   361     /// \e
   362     /// The lower bound of a linear expression (row) have to be given by an 
   363     /// extended number of type Value, i.e. a finite number of type 
   364     /// Value or -INF.
   365     virtual void _setRowLowerBound(int i, Value value) = 0;
   366     /// \e
   367     /// The lower bound of a linear expression (row) is an 
   368     /// extended number of type Value, i.e. a finite number of type 
   369     /// Value or -INF.
   370     virtual Value _getRowLowerBound(int i) = 0;
   371     /// \e
   372     /// The upper bound of a linear expression (row) have to be given by an 
   373     /// extended number of type Value, i.e. a finite number of type 
   374     /// Value or INF.
   375     virtual void _setRowUpperBound(int i, Value value) = 0;
   376     /// \e
   377     /// The upper bound of a linear expression (row) is an 
   378     /// extended number of type Value, i.e. a finite number of type 
   379     /// Value or INF.
   380     virtual Value _getRowUpperBound(int i) = 0;
   381     /// \e
   382     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
   383     /// \e
   384     virtual Value _getObjCoeff(int i) = 0;
   385     
   386     //SOLUTION RETRIEVING
   387 
   388     /// \e
   389     virtual Value _getPrimal(int i) = 0;
   390     //@}
   391     
   392     /*! @name High level interface (public members)
   393       Problem manipulating functions in the high level interface
   394     */
   395     //@{
   396   public:
   397 
   398     //MATRIX MANIPULATING FUNCTIONS
   399 
   400     /// \e
   401     Col addCol() {
   402       int i=_addCol();  
   403       Col col;
   404       col_iter_map.first(col, INVALID_CLASS);
   405       if (col_iter_map.valid(col)) { //van hasznalhato hely
   406 	col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
   407 	col_iter_map[col]=i;
   408       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
   409 	col=col_iter_map.push_back(i, VALID_CLASS);
   410       }
   411       int_col_map.push_back(col);
   412       return col;
   413     }
   414     /// \e
   415     Row addRow() {
   416       int i=_addRow();
   417       Row row;
   418       row_iter_map.first(row, INVALID_CLASS);
   419       if (row_iter_map.valid(row)) { //van hasznalhato hely
   420 	row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
   421 	row_iter_map[row]=i;
   422       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
   423 	row=row_iter_map.push_back(i, VALID_CLASS);
   424       }
   425       int_row_map.push_back(row);
   426       return row;
   427     }
   428     /// \e
   429     void eraseCol(const Col& col) {
   430       col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
   431       int cols[2];
   432       cols[1]=col_iter_map[col];
   433       _eraseCol(cols[1]);
   434       col_iter_map[col]=0; //glpk specifikus, de kell ez??
   435       Col it;
   436       for (col_iter_map.first(it, VALID_CLASS); 
   437 	   col_iter_map.valid(it); col_iter_map.next(it)) {
   438 	if (col_iter_map[it]>cols[1]) --col_iter_map[it];
   439       }
   440       int_col_map.erase(int_col_map.begin()+cols[1]);
   441     }
   442     /// \e
   443     void eraseRow(const Row& row) {
   444       row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
   445       int rows[2];
   446       rows[1]=row_iter_map[row];
   447       _eraseRow(rows[1]);
   448       row_iter_map[row]=0; //glpk specifikus, de kell ez??
   449       Row it;
   450       for (row_iter_map.first(it, VALID_CLASS); 
   451 	   row_iter_map.valid(it); row_iter_map.next(it)) {
   452 	if (row_iter_map[it]>rows[1]) --row_iter_map[it];
   453       }
   454       int_row_map.erase(int_row_map.begin()+rows[1]);
   455     }
   456     /// \e
   457     void setCoeff(Col col, Row row, Value value) {
   458       _setCoeff(col_iter_map[col], row_iter_map[row], value);
   459     }
   460     /// \e
   461     Value getCoeff(Col col, Row row) {
   462       return _getCoeff(col_iter_map[col], row_iter_map[row], value);
   463     }
   464     /// \e
   465     void setColLowerBound(Col col, Value lo) {
   466       _setColLowerBound(col_iter_map[col], lo);
   467     }
   468     /// \e
   469     Value getColLowerBound(Col col) {
   470       return _getColLowerBound(col_iter_map[col]);
   471     }
   472     /// \e
   473     void setColUpperBound(Col col, Value up) {
   474       _setColUpperBound(col_iter_map[col], up);
   475     }
   476     /// \e
   477     Value getColUpperBound(Col col) {      
   478       return _getColUpperBound(col_iter_map[col]);
   479     }
   480     /// \e
   481     void setRowLowerBound(Row row, Value lo) {
   482       _setRowLowerBound(row_iter_map[row], lo);
   483     }
   484     /// \e
   485     Value getRowLowerBound(Row row) {
   486       return _getRowLowerBound(row_iter_map[row]);
   487     }
   488     /// \e
   489     void setRowUpperBound(Row row, Value up) {
   490       _setRowUpperBound(row_iter_map[row], up);
   491     }
   492     /// \e
   493     Value getRowUpperBound(Row row) {      
   494       return _getRowUpperBound(row_iter_map[row]);
   495     }
   496     /// \e
   497     void setObjCoeff(const Col& col, Value obj_coef) {
   498       _setObjCoeff(col_iter_map[col], obj_coef);
   499     }
   500     /// \e
   501     Value getObjCoeff(const Col& col) {
   502       return _getObjCoeff(col_iter_map[col]);
   503     }
   504 
   505     //SOLUTION RETRIEVING FUNCTIONS
   506 
   507     /// \e
   508     Value getPrimal(const Col& col) {
   509       return _getPrimal(col_iter_map[col]);
   510     }    
   511 
   512     //@}
   513 
   514     /*! @name User friend interface
   515       Problem manipulating functions in the user friend interface
   516     */
   517     //@{
   518 
   519     //EXPRESSION TYPES
   520 
   521     /// \e
   522     typedef Expr<Col, Value> Expression;
   523     /// \e
   524     typedef Expr<Row, Value> DualExpression;
   525     /// \e
   526     typedef Constr<Col, Value> Constraint;
   527 
   528     //MATRIX MANIPULATING FUNCTIONS
   529 
   530     /// \e
   531     void setRowCoeffs(Row row, const Expression& expr) {
   532       std::vector<std::pair<int, Value> > row_coeffs;
   533       for(typename Expression::Data::const_iterator i=expr.data.begin(); 
   534 	  i!=expr.data.end(); ++i) {
   535 	row_coeffs.push_back(std::make_pair
   536 			     (col_iter_map[(*i).first], (*i).second));
   537       }
   538       _setRowCoeffs(row_iter_map[row], row_coeffs);
   539     }
   540     /// \e 
   541     void setRow(Row row, const Constraint& constr) {
   542       setRowCoeffs(row, constr.expr);
   543       setRowLowerBound(row, constr.lo);
   544       setRowUpperBound(row, constr.up);
   545     }
   546     /// \e 
   547     Row addRow(const Constraint& constr) {
   548       Row row=addRow();
   549       setRowCoeffs(row, constr.expr);
   550       setRowLowerBound(row, constr.lo);
   551       setRowUpperBound(row, constr.up);
   552       return row;
   553     }
   554     /// \e
   555     /// This routine modifies \c expr by only adding to it.
   556     void getRowCoeffs(Row row, Expression& expr) {
   557       std::vector<std::pair<int, Value> > row_coeffs;
   558       _getRowCoeffs(row_iter_map[row], row_coeffs);
   559       for(typename std::vector<std::pair<int, Value> >::const_iterator 
   560  	    i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
   561  	expr+= (*i).second*int_col_map[(*i).first];
   562       }
   563     }
   564     /// \e
   565     void setColCoeffs(Col col, const DualExpression& expr) {
   566       std::vector<std::pair<int, Value> > col_coeffs;
   567       for(typename DualExpression::Data::const_iterator i=expr.data.begin(); 
   568 	  i!=expr.data.end(); ++i) {
   569 	col_coeffs.push_back(std::make_pair
   570 			     (row_iter_map[(*i).first], (*i).second));
   571       }
   572       _setColCoeffs(col_iter_map[col], col_coeffs);
   573     }
   574     /// \e
   575     /// This routine modifies \c expr by only adding to it.
   576     void getColCoeffs(Col col, DualExpression& expr) {
   577       std::vector<std::pair<int, Value> > col_coeffs;
   578       _getColCoeffs(col_iter_map[col], col_coeffs);
   579       for(typename std::vector<std::pair<int, Value> >::const_iterator 
   580  	    i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
   581  	expr+= (*i).second*int_row_map[(*i).first];
   582       }
   583     }
   584     /// \e
   585     void setObjCoeffs(const Expression& expr) {
   586       // writing zero everywhere
   587       for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
   588 	setObjCoeff(it, 0.0);
   589       // writing the data needed
   590       for(typename Expression::Data::const_iterator i=expr.data.begin(); 
   591 	  i!=expr.data.end(); ++i) {
   592 	setObjCoeff((*i).first, (*i).second);
   593       }
   594     }
   595     /// \e
   596     /// This routine modifies \c expr by only adding to it.
   597     void getObjCoeffs(Expression& expr) {
   598       for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
   599 	expr+=getObjCoeff(it)*it;
   600     }
   601     //@}
   602 
   603 
   604     /*! @name MIP functions and types (public members)
   605     */
   606     //@{
   607   public:
   608     /// \e
   609     virtual void solveBandB() = 0;
   610     /// \e
   611     virtual void setLP() = 0;
   612     /// \e
   613     virtual void setMIP() = 0;
   614   protected:
   615    /// \e
   616     virtual void _setColCont(int i) = 0;
   617     /// \e
   618     virtual void _setColInt(int i) = 0;
   619     /// \e
   620     virtual Value _getMIPPrimal(int i) = 0;
   621   public:
   622     /// \e
   623     void setColCont(Col col) {
   624       _setColCont(col_iter_map[col]);
   625     }
   626     /// \e
   627     void setColInt(Col col) {
   628       _setColInt(col_iter_map[col]);
   629     }
   630     /// \e
   631     Value getMIPPrimal(Col col) {
   632       return _getMIPPrimal(col_iter_map[col]);
   633     }
   634     //@}
   635   };
   636 
   637 } //namespace lemon
   638 
   639 #endif //LEMON_LP_SOLVER_BASE_H