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

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

     2 #ifndef LEMON_LP_SOLVER_BASE_H

     3 #define LEMON_LP_SOLVER_BASE_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>

    16 #include <iostream>

    17 #include <vector>

    18 #include <string>

    19 #include <list>

    20 #include <memory>

    21 #include <utility>

    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>

    30 using std::cout;

    31 using std::cin;

    32 using std::endl;

    34 namespace lemon {

    36   /// \addtogroup misc

    37   /// @{

    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; }

   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     };

   185   };

   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 {

   201     /*! @name Uncategorized functions and types (public members)

   202     */

   203     //@{

   204   public:

   206     //UNCATEGORIZED

   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     //@}

   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:

   253     //UNCATEGORIZED FUNCTIONS

   255     /// \e

   256     virtual void setMinimize() = 0;

   257     /// \e

   258     virtual void setMaximize() = 0;

   260     //SOLVER FUNCTIONS

   262     /// \e

   263     virtual void solveSimplex() = 0;

   264     /// \e

   265     virtual void solvePrimalSimplex() = 0;

   266     /// \e

   267     virtual void solveDualSimplex() = 0;

   269     //SOLUTION RETRIEVING

   271     /// \e

   272     virtual Value getObjVal() = 0;

   274     //OTHER FUNCTIONS

   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;

   301     //@}

   303     /*! @name Low level interface (protected members)

   304       Problem manipulating functions in the low level interface

   305     */

   306     //@{

   307   protected:

   309     //MATRIX MANIPULATING FUNCTIONS

   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;

   386     //SOLUTION RETRIEVING

   388     /// \e

   389     virtual Value _getPrimal(int i) = 0;

   390     //@}

   392     /*! @name High level interface (public members)

   393       Problem manipulating functions in the high level interface

   394     */

   395     //@{

   396   public:

   398     //MATRIX MANIPULATING FUNCTIONS

   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     }

   505     //SOLUTION RETRIEVING FUNCTIONS

   507     /// \e

   508     Value getPrimal(const Col& col) {

   509       return _getPrimal(col_iter_map[col]);

   510     }

   512     //@}

   514     /*! @name User friend interface

   515       Problem manipulating functions in the user friend interface

   516     */

   517     //@{

   519     //EXPRESSION TYPES

   521     /// \e

   522     typedef Expr<Col, Value> Expression;

   523     /// \e

   524     typedef Expr<Row, Value> DualExpression;

   525     /// \e

   526     typedef Constr<Col, Value> Constraint;

   528     //MATRIX MANIPULATING FUNCTIONS

   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     //@}

   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   };

   637 } //namespace lemon

   639 #endif //LEMON_LP_SOLVER_BASE_H

author	athos
	Tue, 22 Mar 2005 12:02:29 +0000
changeset 1241	dadc9987c537
parent 1240	88a2ab6bfc4a
permissions	-rw-r--r--