lemon-0.x: src/work/marci/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>

    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 <stp.h>

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

    30 //#include <augmenting_flow.h>

    31 //#include <iter_map.h>

    33 using std::cout;

    34 using std::cin;

    35 using std::endl;

    37 namespace lemon {

    39   /// \addtogroup misc

    40   /// @{

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

    43   ///

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

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

    46   /// doubly linked in a list.

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

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

    49   template <typename T>

    50   class IterablePartition {

    51   protected:

    52     struct Node {

    53       T data;

    54       int prev; //invalid az -1

    55       int next;

    56     };

    57     std::vector<Node> nodes;

    58     struct Tip {

    59       int first;

    60       int last;

    61     };

    62     std::vector<Tip> tips;

    63   public:

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

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

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

    67     class Class;

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

    69     /// over the life of the container.

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

    71     IterablePartition(int class_num) {

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

    73 	Tip t;

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

    75 	tips.push_back(t);

    76       }

    77     }

    78   protected:

    79     void befuz(Class it, int class_id) {

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

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

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

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

    84 	}

    85       } else {

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

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

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

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

    90       }

    91     }

    92     void kifuz(Class it, int class_id) {

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

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

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

    96 	} else {

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

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

    99 	}

   100       } else {

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

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

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

   104 	} else {

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

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

   107 	}

   108       }

   109     }

   110   public:

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

   112     /// \c class_id.

   113     Class push_back(const T& t, int class_id) {

   114       Node n;

   115       n.data=t;

   116       nodes.push_back(n);

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

   118       befuz(i, class_id);

   119       return i;

   120     }

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

   122     void set(Class it, int old_class_id, int new_class_id) {

   123       kifuz(it.i, old_class_id);

   124       befuz(it.i, new_class_id);

   125     }

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

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

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

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

   130     ///.

   131     class Class {

   132       friend class IterablePartition;

   133     protected:

   134       int i;

   135     public:

   136       /// Default constructor.

   137       Class() { }

   138       /// This constructor constructs an iterator which points

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

   140       Class(const int& _i) : i(_i) { }

   141       /// Invalid constructor.

   142       Class(const Invalid&) : i(-1) { }

   143       friend bool operator<(const Class& x, const Class& y);

   144       friend std::ostream& operator<<(std::ostream& os,

   145 				      const Class& it);

   146       bool operator==(const Class& node) const {return i == node.i;}

   147       bool operator!=(const Class& node) const {return i != node.i;}

   148     };

   149     friend bool operator<(const Class& x, const Class& y) {

   150       return (x.i < y.i);

   151     }

   152     friend std::ostream& operator<<(std::ostream& os,

   153 				    const Class& it) {

   154       os << it.i;

   155       return os;

   156     }

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

   158     Class& first(Class& it, int class_id) const {

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

   160       return it;

   161     }

   162     /// Next member.

   163     Class& next(Class& it) const {

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

   165       return it;

   166     }

   167     /// True iff the iterator is valid.

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

   170     class ClassIt : public Class {

   171       const IterablePartition* iterable_partition;

   172     public:

   173       ClassIt() { }

   174       ClassIt(Invalid i) : Class(i) { }

   175       ClassIt(const IterablePartition& _iterable_partition,

   176 	      const int& i) : iterable_partition(&_iterable_partition) {

   177         _iterable_partition.first(*this, i);

   178       }

   179       ClassIt(const IterablePartition& _iterable_partition,

   180 	      const Class& _class) :

   181 	Class(_class), iterable_partition(&_iterable_partition) { }

   182       ClassIt& operator++() {

   183         iterable_partition->next(*this);

   184         return *this;

   185       }

   186     };

   188   };

   191   /*! \e

   192     \todo kellenene uj iterable structure bele, mert ez nem az igazi

   193     \todo A[x,y]-t cserel. Jobboldal, baloldal csere.

   194     \todo LEKERDEZESEK!!!

   195     \todo DOKSI!!!! Doxygen group!!!

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

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

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

   199     \nosubgrouping

   200   */

   201   template <typename _Value>

   202   class LPSolverBase {

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

   205     */

   206     //@{

   207   public:

   209     //UNCATEGORIZED

   211     /// \e

   212     typedef IterablePartition<int> Rows;

   213     /// \e

   214     typedef IterablePartition<int> Cols;

   215     /// \e

   216     typedef _Value Value;

   217     /// \e

   218     typedef Rows::Class Row;

   219     /// \e

   220     typedef Cols::Class Col;

   221   public:

   222     /// \e

   223     IterablePartition<int> row_iter_map;

   224     /// \e

   225     IterablePartition<int> col_iter_map;

   226     /// \e

   227     std::vector<Row> int_row_map;

   228     /// \e

   229     std::vector<Col> int_col_map;

   230     /// \e

   231     const int VALID_CLASS;

   232     /// \e

   233     const int INVALID_CLASS;

   234     /// \e

   235     static const _Value INF;

   236   public:

   237     /// \e

   238     LPSolverBase() : row_iter_map(2),

   239 		     col_iter_map(2),

   240 		     VALID_CLASS(0), INVALID_CLASS(1) { }

   241     /// \e

   242     virtual ~LPSolverBase() { }

   243     //@}

   245     /*! @name Medium level interface (public members)

   246       These functions appear in the low level and also in the high level

   247       interfaces thus these each of these functions have to be implemented

   248       only once in the different interfaces.

   249       This means that these functions have to be reimplemented for all of the

   250       different lp solvers. These are basic functions, and have the same

   251       parameter lists in the low and high level interfaces.

   252     */

   253     //@{

   254   public:

   256     //UNCATEGORIZED FUNCTIONS

   258     /// \e

   259     virtual void setMinimize() = 0;

   260     /// \e

   261     virtual void setMaximize() = 0;

   263     //SOLVER FUNCTIONS

   265     /// \e

   266     virtual void solveSimplex() = 0;

   267     /// \e

   268     virtual void solvePrimalSimplex() = 0;

   269     /// \e

   270     virtual void solveDualSimplex() = 0;

   272     //SOLUTION RETRIEVING

   274     /// \e

   275     virtual _Value getObjVal() = 0;

   277     //OTHER FUNCTIONS

   279     /// \e

   280     virtual int rowNum() const = 0;

   281     /// \e

   282     virtual int colNum() const = 0;

   283     /// \e

   284     virtual int warmUp() = 0;

   285     /// \e

   286     virtual void printWarmUpStatus(int i) = 0;

   287     /// \e

   288     virtual int getPrimalStatus() = 0;

   289     /// \e

   290     virtual void printPrimalStatus(int i) = 0;

   291     /// \e

   292     virtual int getDualStatus() = 0;

   293     /// \e

   294     virtual void printDualStatus(int i) = 0;

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

   296     virtual int getRowStat(const Row& row) = 0;

   297     /// \e

   298     virtual void printRowStatus(int i) = 0;

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

   300     virtual int getColStat(const Col& col) = 0;

   301     /// \e

   302     virtual void printColStatus(int i) = 0;

   304     //@}

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

   307       Problem manipulating functions in the low level interface

   308     */

   309     //@{

   310   protected:

   312     //MATRIX MANIPULATING FUNCTIONS

   314     /// \e

   315     virtual int _addCol() = 0;

   316     /// \e

   317     virtual int _addRow() = 0;

   318     /// \e

   319     virtual void _eraseCol(int i) = 0;

   320     /// \e

   321     virtual void _eraseRow(int i) = 0;

   322     /// \e

   323     virtual void _setRowCoeffs(int i,

   324 			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;

   325     /// \e

   326     /// This routine modifies \c coeffs only by the \c push_back method.

   327     virtual void _getRowCoeffs(int i,

   328 			       std::vector<std::pair<int, _Value> >& coeffs) = 0;

   329     /// \e

   330     virtual void _setColCoeffs(int i,

   331 			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;

   332     /// \e

   333     /// This routine modifies \c coeffs only by the \c push_back method.

   334     virtual void _getColCoeffs(int i,

   335 			       std::vector<std::pair<int, _Value> >& coeffs) = 0;

   336     /// \e

   337     virtual void _setCoeff(int col, int row, _Value value) = 0;

   338     /// \e

   339     virtual _Value _getCoeff(int col, int row) = 0;

   340     //  public:

   341     //    /// \e

   342     //    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };

   343   protected:

   344     /// \e

   345     /// The lower bound of a variable (column) have to be given by an

   346     /// extended number of type _Value, i.e. a finite number of type

   347     /// _Value or -INF.

   348     virtual void _setColLowerBound(int i, _Value value) = 0;

   349     /// \e

   350     /// The lower bound of a variable (column) is an

   351     /// extended number of type _Value, i.e. a finite number of type

   352     /// _Value or -INF.

   353     virtual _Value _getColLowerBound(int i) = 0;

   354     /// \e

   355     /// The upper bound of a variable (column) have to be given by an

   356     /// extended number of type _Value, i.e. a finite number of type

   357     /// _Value or INF.

   358     virtual void _setColUpperBound(int i, _Value value) = 0;

   359     /// \e

   360     /// The upper bound of a variable (column) is an

   361     /// extended number of type _Value, i.e. a finite number of type

   362     /// _Value or INF.

   363     virtual _Value _getColUpperBound(int i) = 0;

   364     /// \e

   365     /// The lower bound of a linear expression (row) have to be given by an

   366     /// extended number of type _Value, i.e. a finite number of type

   367     /// _Value or -INF.

   368     virtual void _setRowLowerBound(int i, _Value value) = 0;

   369     /// \e

   370     /// The lower bound of a linear expression (row) is an

   371     /// extended number of type _Value, i.e. a finite number of type

   372     /// _Value or -INF.

   373     virtual _Value _getRowLowerBound(int i) = 0;

   374     /// \e

   375     /// The upper bound of a linear expression (row) have to be given by an

   376     /// extended number of type _Value, i.e. a finite number of type

   377     /// _Value or INF.

   378     virtual void _setRowUpperBound(int i, _Value value) = 0;

   379     /// \e

   380     /// The upper bound of a linear expression (row) is an

   381     /// extended number of type _Value, i.e. a finite number of type

   382     /// _Value or INF.

   383     virtual _Value _getRowUpperBound(int i) = 0;

   384     /// \e

   385     virtual void _setObjCoeff(int i, _Value obj_coef) = 0;

   386     /// \e

   387     virtual _Value _getObjCoeff(int i) = 0;

   389     //SOLUTION RETRIEVING

   391     /// \e

   392     virtual _Value _getPrimal(int i) = 0;

   393     //@}

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

   396       Problem manipulating functions in the high level interface

   397     */

   398     //@{

   399   public:

   401     //MATRIX MANIPULATING FUNCTIONS

   403     /// \e

   404     Col addCol() {

   405       int i=_addCol();

   406       Col col;

   407       col_iter_map.first(col, INVALID_CLASS);

   408       if (col_iter_map.valid(col)) { //van hasznalhato hely

   409 	col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);

   410 	col_iter_map[col]=i;

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

   412 	col=col_iter_map.push_back(i, VALID_CLASS);

   413       }

   414       int_col_map.push_back(col);

   415       return col;

   416     }

   417     /// \e

   418     Row addRow() {

   419       int i=_addRow();

   420       Row row;

   421       row_iter_map.first(row, INVALID_CLASS);

   422       if (row_iter_map.valid(row)) { //van hasznalhato hely

   423 	row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);

   424 	row_iter_map[row]=i;

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

   426 	row=row_iter_map.push_back(i, VALID_CLASS);

   427       }

   428       int_row_map.push_back(row);

   429       return row;

   430     }

   431     /// \e

   432     void eraseCol(const Col& col) {

   433       col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);

   434       int cols[2];

   435       cols[1]=col_iter_map[col];

   436       _eraseCol(cols[1]);

   437       col_iter_map[col]=0; //glpk specifikus, de kell ez??

   438       Col it;

   439       for (col_iter_map.first(it, VALID_CLASS);

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

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

   442       }

   443       int_col_map.erase(int_col_map.begin()+cols[1]);

   444     }

   445     /// \e

   446     void eraseRow(const Row& row) {

   447       row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);

   448       int rows[2];

   449       rows[1]=row_iter_map[row];

   450       _eraseRow(rows[1]);

   451       row_iter_map[row]=0; //glpk specifikus, de kell ez??

   452       Row it;

   453       for (row_iter_map.first(it, VALID_CLASS);

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

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

   456       }

   457       int_row_map.erase(int_row_map.begin()+rows[1]);

   458     }

   459     /// \e

   460     void setCoeff(Col col, Row row, _Value value) {

   461       _setCoeff(col_iter_map[col], row_iter_map[row], value);

   462     }

   463     /// \e

   464     _Value getCoeff(Col col, Row row) {

   465       return _getCoeff(col_iter_map[col], row_iter_map[row], value);

   466     }

   467     /// \e

   468     void setColLowerBound(Col col, _Value lo) {

   469       _setColLowerBound(col_iter_map[col], lo);

   470     }

   471     /// \e

   472     _Value getColLowerBound(Col col) {

   473       return _getColLowerBound(col_iter_map[col]);

   474     }

   475     /// \e

   476     void setColUpperBound(Col col, _Value up) {

   477       _setColUpperBound(col_iter_map[col], up);

   478     }

   479     /// \e

   480     _Value getColUpperBound(Col col) {

   481       return _getColUpperBound(col_iter_map[col]);

   482     }

   483     /// \e

   484     void setRowLowerBound(Row row, _Value lo) {

   485       _setRowLowerBound(row_iter_map[row], lo);

   486     }

   487     /// \e

   488     _Value getRowLowerBound(Row row) {

   489       return _getRowLowerBound(row_iter_map[row]);

   490     }

   491     /// \e

   492     void setRowUpperBound(Row row, _Value up) {

   493       _setRowUpperBound(row_iter_map[row], up);

   494     }

   495     /// \e

   496     _Value getRowUpperBound(Row row) {

   497       return _getRowUpperBound(row_iter_map[row]);

   498     }

   499     /// \e

   500     void setObjCoeff(const Col& col, _Value obj_coef) {

   501       _setObjCoeff(col_iter_map[col], obj_coef);

   502     }

   503     /// \e

   504     _Value getObjCoeff(const Col& col) {

   505       return _getObjCoeff(col_iter_map[col]);

   506     }

   508     //SOLUTION RETRIEVING FUNCTIONS

   510     /// \e

   511     _Value getPrimal(const Col& col) {

   512       return _getPrimal(col_iter_map[col]);

   513     }

   515     //@}

   517     /*! @name User friend interface

   518       Problem manipulating functions in the user friend interface

   519     */

   520     //@{

   522     //EXPRESSION TYPES

   524     /// \e

   525     typedef Expr<Col, _Value> Expression;

   526     /// \e

   527     typedef Expr<Row, _Value> DualExpression;

   528     /// \e

   529     typedef Constr<Col, _Value> Constraint;

   531     //MATRIX MANIPULATING FUNCTIONS

   533     /// \e

   534     void setRowCoeffs(Row row, const Expression& expr) {

   535       std::vector<std::pair<int, _Value> > row_coeffs;

   536       for(typename Expression::Data::const_iterator i=expr.data.begin();

   537 	  i!=expr.data.end(); ++i) {

   538 	row_coeffs.push_back(std::make_pair

   539 			     (col_iter_map[(*i).first], (*i).second));

   540       }

   541       _setRowCoeffs(row_iter_map[row], row_coeffs);

   542     }

   543     /// \e

   544     void setRow(Row row, const Constraint& constr) {

   545       setRowCoeffs(row, constr.expr);

   546       setRowLowerBound(row, constr.lo);

   547       setRowUpperBound(row, constr.up);

   548     }

   549     /// \e

   550     Row addRow(const Constraint& constr) {

   551       Row row=addRow();

   552       setRowCoeffs(row, constr.expr);

   553       setRowLowerBound(row, constr.lo);

   554       setRowUpperBound(row, constr.up);

   555       return row;

   556     }

   557     /// \e

   558     /// This routine modifies \c expr by only adding to it.

   559     void getRowCoeffs(Row row, Expression& expr) {

   560       std::vector<std::pair<int, _Value> > row_coeffs;

   561       _getRowCoeffs(row_iter_map[row], row_coeffs);

   562       for(typename std::vector<std::pair<int, _Value> >::const_iterator

   563  	    i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {

   564  	expr+= (*i).second*int_col_map[(*i).first];

   565       }

   566     }

   567     /// \e

   568     void setColCoeffs(Col col, const DualExpression& expr) {

   569       std::vector<std::pair<int, _Value> > col_coeffs;

   570       for(typename DualExpression::Data::const_iterator i=expr.data.begin();

   571 	  i!=expr.data.end(); ++i) {

   572 	col_coeffs.push_back(std::make_pair

   573 			     (row_iter_map[(*i).first], (*i).second));

   574       }

   575       _setColCoeffs(col_iter_map[col], col_coeffs);

   576     }

   577     /// \e

   578     /// This routine modifies \c expr by only adding to it.

   579     void getColCoeffs(Col col, DualExpression& expr) {

   580       std::vector<std::pair<int, _Value> > col_coeffs;

   581       _getColCoeffs(col_iter_map[col], col_coeffs);

   582       for(typename std::vector<std::pair<int, _Value> >::const_iterator

   583  	    i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {

   584  	expr+= (*i).second*int_row_map[(*i).first];

   585       }

   586     }

   587     /// \e

   588     void setObjCoeffs(const Expression& expr) {

   589       // writing zero everywhere

   590       for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)

   591 	setObjCoeff(it, 0.0);

   592       // writing the data needed

   593       for(typename Expression::Data::const_iterator i=expr.data.begin();

   594 	  i!=expr.data.end(); ++i) {

   595 	setObjCoeff((*i).first, (*i).second);

   596       }

   597     }

   598     /// \e

   599     /// This routine modifies \c expr by only adding to it.

   600     void getObjCoeffs(Expression& expr) {

   601       for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)

   602 	expr+=getObjCoeff(it)*it;

   603     }

   604     //@}

   607     /*! @name MIP functions and types (public members)

   608     */

   609     //@{

   610   public:

   611     /// \e

   612     virtual void solveBandB() = 0;

   613     /// \e

   614     virtual void setLP() = 0;

   615     /// \e

   616     virtual void setMIP() = 0;

   617   protected:

   618    /// \e

   619     virtual void _setColCont(int i) = 0;

   620     /// \e

   621     virtual void _setColInt(int i) = 0;

   622   public:

   623     /// \e

   624     void setColCont(Col col) {

   625       _setColCont(col_iter_map[col]);

   626     }

   627     /// \e

   628     void setColInt(Col col) {

   629       _setColInt(col_iter_map[col]);

   630     }

   631     //@}

   632   };

   634   template <typename _Value>

   635   const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();

   638   /// \brief Wrapper for GLPK solver

   639   ///

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

   641   class LPGLPK : public LPSolverBase<double> {

   642   public:

   643     typedef LPSolverBase<double> Parent;

   645   public:

   646     /// \e

   647     LPX* lp;

   649   public:

   650     /// \e

   651     LPGLPK() : Parent(),

   652 			lp(lpx_create_prob()) {

   653       int_row_map.push_back(Row());

   654       int_col_map.push_back(Col());

   655       lpx_set_int_parm(lp, LPX_K_DUAL, 1);

   656     }

   657     /// \e

   658     ~LPGLPK() {

   659       lpx_delete_prob(lp);

   660     }

   662     //MATRIX INDEPEDENT MANIPULATING FUNCTIONS

   664     /// \e

   665     void setMinimize() {

   666       lpx_set_obj_dir(lp, LPX_MIN);

   667     }

   668     /// \e

   669     void setMaximize() {

   670       lpx_set_obj_dir(lp, LPX_MAX);

   671     }

   673     //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS

   675   protected:

   676     /// \e

   677     int _addCol() {

   678       int i=lpx_add_cols(lp, 1);

   679       _setColLowerBound(i, -INF);

   680       _setColUpperBound(i, INF);

   681       return i;

   682     }

   683     /// \e

   684     int _addRow() {

   685       int i=lpx_add_rows(lp, 1);

   686       return i;

   687     }

   688     /// \e

   689     virtual void _setRowCoeffs(int i,

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

   691       int mem_length=1+colNum();

   692       int* indices = new int[mem_length];

   693       double* doubles = new double[mem_length];

   694       int length=0;

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

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

   697 	++length;

   698 	indices[length]=it->first;

   699 	doubles[length]=it->second;

   700       }

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

   702       delete [] indices;

   703       delete [] doubles;

   704     }

   705     /// \e

   706     virtual void _getRowCoeffs(int i,

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

   708       int mem_length=1+colNum();

   709       int* indices = new int[mem_length];

   710       double* doubles = new double[mem_length];

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

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

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

   714       }

   715       delete [] indices;

   716       delete [] doubles;

   717     }

   718     /// \e

   719     virtual void _setColCoeffs(int i,

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

   721       int mem_length=1+rowNum();

   722       int* indices = new int[mem_length];

   723       double* doubles = new double[mem_length];

   724       int length=0;

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

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

   727 	++length;

   728 	indices[length]=it->first;

   729 	doubles[length]=it->second;

   730       }

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

   732       delete [] indices;

   733       delete [] doubles;

   734     }

   735     /// \e

   736     virtual void _getColCoeffs(int i,

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

   738       int mem_length=1+rowNum();

   739       int* indices = new int[mem_length];

   740       double* doubles = new double[mem_length];

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

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

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

   744       }

   745       delete [] indices;

   746       delete [] doubles;

   747     }

   748     /// \e

   749     virtual void _eraseCol(int i) {

   750       int cols[2];

   751       cols[1]=i;

   752       lpx_del_cols(lp, 1, cols);

   753     }

   754     virtual void _eraseRow(int i) {

   755       int rows[2];

   756       rows[1]=i;

   757       lpx_del_rows(lp, 1, rows);

   758     }

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

   760       /// FIXME not yet implemented

   761     }

   762     double _getCoeff(int col, int row) {

   763       /// FIXME not yet implemented

   764       return 0.0;

   765     }

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

   767       if (lo==INF) {

   768 	//FIXME error

   769       }

   770       int b=lpx_get_col_type(lp, i);

   771       double up=lpx_get_col_ub(lp, i);

   772       if (lo==-INF) {

   773 	switch (b) {

   774 	case LPX_FR:

   775 	case LPX_LO:

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

   777 	  break;

   778 	case LPX_UP:

   779 	  break;

   780 	case LPX_DB:

   781 	case LPX_FX:

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

   783 	  break;

   784 	default: ;

   785 	  //FIXME error

   786 	}

   787       } else {

   788 	switch (b) {

   789 	case LPX_FR:

   790 	case LPX_LO:

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

   792 	  break;

   793 	case LPX_UP:

   794 	case LPX_DB:

   795 	case LPX_FX:

   796 	  if (lo==up)

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

   798 	  else

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

   800 	  break;

   801 	default: ;

   802 	  //FIXME error

   803 	}

   804       }

   805     }

   806     virtual double _getColLowerBound(int i) {

   807       int b=lpx_get_col_type(lp, i);

   808       switch (b) {

   809       case LPX_FR:

   810 	return -INF;

   811       case LPX_LO:

   812 	return lpx_get_col_lb(lp, i);

   813       case LPX_UP:

   814 	return -INF;

   815       case LPX_DB:

   816       case LPX_FX:

   817 	return lpx_get_col_lb(lp, i);

   818       default: ;

   819 	//FIXME error

   820 	return 0.0;

   821       }

   822     }

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

   824       if (up==-INF) {

   825 	//FIXME error

   826       }

   827       int b=lpx_get_col_type(lp, i);

   828       double lo=lpx_get_col_lb(lp, i);

   829       if (up==INF) {

   830 	switch (b) {

   831 	case LPX_FR:

   832 	case LPX_LO:

   833 	  break;

   834 	case LPX_UP:

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

   836 	  break;

   837 	case LPX_DB:

   838 	case LPX_FX:

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

   840 	  break;

   841 	default: ;

   842 	  //FIXME error

   843 	}

   844       } else {

   845 	switch (b) {

   846 	case LPX_FR:

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

   848 	case LPX_LO:

   849 	  if (lo==up)

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

   851 	  else

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

   853 	  break;

   854 	case LPX_UP:

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

   856 	  break;

   857 	case LPX_DB:

   858 	case LPX_FX:

   859 	  if (lo==up)

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

   861 	  else

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

   863 	  break;

   864 	default: ;

   865 	  //FIXME error

   866 	}

   867       }

   868     }

   869     virtual double _getColUpperBound(int i) {

   870       int b=lpx_get_col_type(lp, i);

   871       switch (b) {

   872       case LPX_FR:

   873       case LPX_LO:

   874 	return INF;

   875       case LPX_UP:

   876       case LPX_DB:

   877       case LPX_FX:

   878 	return lpx_get_col_ub(lp, i);

   879       default: ;

   880 	//FIXME error

   881 	return 0.0;

   882       }

   883     }

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

   885       if (lo==INF) {

   886 	//FIXME error

   887       }

   888       int b=lpx_get_row_type(lp, i);

   889       double up=lpx_get_row_ub(lp, i);

   890       if (lo==-INF) {

   891 	switch (b) {

   892 	case LPX_FR:

   893 	case LPX_LO:

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

   895 	  break;

   896 	case LPX_UP:

   897 	  break;

   898 	case LPX_DB:

   899 	case LPX_FX:

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

   901 	  break;

   902 	default: ;

   903 	  //FIXME error

   904 	}

   905       } else {

   906 	switch (b) {

   907 	case LPX_FR:

   908 	case LPX_LO:

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

   910 	  break;

   911 	case LPX_UP:

   912 	case LPX_DB:

   913 	case LPX_FX:

   914 	  if (lo==up)

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

   916 	  else

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

   918 	  break;

   919 	default: ;

   920 	  //FIXME error

   921 	}

   922       }

   923     }

   924     virtual double _getRowLowerBound(int i) {

   925       int b=lpx_get_row_type(lp, i);

   926       switch (b) {

   927       case LPX_FR:

   928 	return -INF;

   929       case LPX_LO:

   930 	return lpx_get_row_lb(lp, i);

   931       case LPX_UP:

   932 	return -INF;

   933       case LPX_DB:

   934       case LPX_FX:

   935 	return lpx_get_row_lb(lp, i);

   936       default: ;

   937 	//FIXME error

   938 	return 0.0;

   939       }

   940     }

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

   942       if (up==-INF) {

   943 	//FIXME error

   944       }

   945       int b=lpx_get_row_type(lp, i);

   946       double lo=lpx_get_row_lb(lp, i);

   947       if (up==INF) {

   948 	switch (b) {

   949 	case LPX_FR:

   950 	case LPX_LO:

   951 	  break;

   952 	case LPX_UP:

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

   954 	  break;

   955 	case LPX_DB:

   956 	case LPX_FX:

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

   958 	  break;

   959 	default: ;

   960 	  //FIXME error

   961 	}

   962       } else {

   963 	switch (b) {

   964 	case LPX_FR:

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

   966 	case LPX_LO:

   967 	  if (lo==up)

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

   969 	  else

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

   971 	  break;

   972 	case LPX_UP:

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

   974 	  break;

   975 	case LPX_DB:

   976 	case LPX_FX:

   977 	  if (lo==up)

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

   979 	  else

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

   981 	  break;

   982 	default: ;

   983 	  //FIXME error

   984 	}

   985       }

   986     }

   987     virtual double _getRowUpperBound(int i) {

   988       int b=lpx_get_row_type(lp, i);

   989       switch (b) {

   990       case LPX_FR:

   991       case LPX_LO:

   992 	return INF;

   993       case LPX_UP:

   994       case LPX_DB:

   995       case LPX_FX:

   996 	return lpx_get_row_ub(lp, i);

   997       default: ;

   998 	//FIXME error

   999 	return 0.0;

  1000       }

  1001     }

  1002     /// \e

  1003     virtual double _getObjCoeff(int i) {

  1004       return lpx_get_obj_coef(lp, i);

  1005     }

  1006     /// \e

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

  1008       lpx_set_obj_coef(lp, i, obj_coef);

  1009     }

  1010   public:

  1011     /// \e

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

  1013     /// \e

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

  1015     /// \e

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

  1017   protected:

  1018     virtual double _getPrimal(int i) {

  1019       return lpx_get_col_prim(lp, i);

  1020     }

  1021   public:

  1022     /// \e

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

  1024     /// \e

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

  1026     /// \e

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

  1028     /// \e

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

  1030     /// \e

  1031     void printWarmUpStatus(int i) {

  1032       switch (i) {

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

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

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

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

  1037       }

  1038     }

  1039     /// \e

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

  1041     /// \e

  1042     void printPrimalStatus(int i) {

  1043       switch (i) {

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

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

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

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

  1048       }

  1049     }

  1050     /// \e

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

  1052     /// \e

  1053     void printDualStatus(int i) {

  1054       switch (i) {

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

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

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

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

  1059       }

  1060     }

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

  1062     int getRowStat(const Row& row) {

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

  1064     }

  1065     /// \e

  1066     void printRowStatus(int i) {

  1067       switch (i) {

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

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

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

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

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

  1073       }

  1074     }

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

  1076     int getColStat(const Col& col) {

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

  1078     }

  1079     /// \e

  1080     void printColStatus(int i) {

  1081       switch (i) {

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

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

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

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

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

  1087       }

  1088     }

  1090     // MIP

  1091     /// \e

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

  1093     /// \e

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

  1095     /// \e

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

  1097   protected:

  1098     /// \e

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

  1100     /// \e

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

  1102   };

  1104   /// @}

  1106 } //namespace lemon

  1108 #endif //LEMON_LP_SOLVER_BASE_H

author	marci
	Wed, 16 Feb 2005 21:40:16 +0000
changeset 1152	1765ff9fefa1
parent 1144	1cfabf245433
child 1153	4b0468de3a31
permissions	-rw-r--r--