2 #ifndef LEMON_LP_SOLVER_WRAPPER_H
3 #define LEMON_LP_SOLVER_WRAPPER_H
7 ///\brief Dijkstra algorithm.
27 //#include <lemon/list_graph.h>
28 #include <lemon/invalid.h>
29 #include <expression.h>
30 //#include <bfs_dfs.h>
32 //#include <lemon/max_flow.h>
33 //#include <augmenting_flow.h>
34 //#include <iter_map.h>
45 /// \brief A partitioned vector with iterable classes.
47 /// This class implements a container in which the data is stored in an
48 /// stl vector, the range is partitioned into sets and each set is
49 /// doubly linked in a list.
50 /// That is, each class is iterable by lemon iterators, and any member of
51 /// the vector can bo moved to an other class.
53 class IterablePartition {
57 int prev; //invalid az -1
60 std::vector<Node> nodes;
65 std::vector<Tip> tips;
67 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
68 int classNum() const { return tips.size(); }
69 /// This lemon style iterator iterates through a class.
71 /// Constructor. The number of classes is to be given which is fixed
72 /// over the life of the container.
73 /// The partition classes are indexed from 0 to class_num-1.
74 IterablePartition(int class_num) {
75 for (int i=0; i<class_num; ++i) {
82 void befuz(ClassIt it, int class_id) {
83 if (tips[class_id].first==-1) {
84 if (tips[class_id].last==-1) {
85 nodes[it.i].prev=nodes[it.i].next=-1;
86 tips[class_id].first=tips[class_id].last=it.i;
89 nodes[it.i].prev=tips[class_id].last;
91 nodes[tips[class_id].last].next=it.i;
92 tips[class_id].last=it.i;
95 void kifuz(ClassIt it, int class_id) {
96 if (tips[class_id].first==it.i) {
97 if (tips[class_id].last==it.i) {
98 tips[class_id].first=tips[class_id].last=-1;
100 tips[class_id].first=nodes[it.i].next;
101 nodes[nodes[it.i].next].prev=-1;
104 if (tips[class_id].last==it.i) {
105 tips[class_id].last=nodes[it.i].prev;
106 nodes[nodes[it.i].prev].next=-1;
108 nodes[nodes[it.i].next].prev=nodes[it.i].prev;
109 nodes[nodes[it.i].prev].next=nodes[it.i].next;
114 /// A new element with data \c t is pushed into the vector and into class
116 ClassIt push_back(const T& t, int class_id) {
120 int i=nodes.size()-1;
124 /// A member is moved to an other class.
125 void set(ClassIt it, int old_class_id, int new_class_id) {
126 kifuz(it.i, old_class_id);
127 befuz(it.i, new_class_id);
129 /// Returns the data pointed by \c it.
130 T& operator[](ClassIt it) { return nodes[it.i].data; }
131 /// Returns the data pointed by \c it.
132 const T& operator[](ClassIt it) const { return nodes[it.i].data; }
135 friend class IterablePartition;
139 /// Default constructor.
141 /// This constructor constructs an iterator which points
142 /// to the member of th container indexed by the integer _i.
143 ClassIt(const int& _i) : i(_i) { }
144 /// Invalid constructor.
145 ClassIt(const Invalid&) : i(-1) { }
146 friend bool operator<(const ClassIt& x, const ClassIt& y);
147 friend std::ostream& operator<<(std::ostream& os,
150 friend bool operator<(const ClassIt& x, const ClassIt& y) {
153 friend std::ostream& operator<<(std::ostream& os,
158 /// First member of class \c class_id.
159 ClassIt& first(ClassIt& it, int class_id) const {
160 it.i=tips[class_id].first;
164 ClassIt& next(ClassIt& it) const {
165 it.i=nodes[it.i].next;
168 /// True iff the iterator is valid.
169 bool valid(const ClassIt& it) const { return it.i!=-1; }
174 \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
175 \todo LEKERDEZESEK!!!
176 \todo DOKSI!!!! Doxygen group!!!
177 The aim of this class is to give a general surface to different
178 solvers, i.e. it makes possible to write algorithms using LP's,
179 in which the solver can be changed to an other one easily.
182 template <typename _Value>
185 /*! @name Unchategorized functions and types (public members)
193 typedef _Value Value;
195 typedef IterablePartition<int>::ClassIt RowIt;
197 typedef IterablePartition<int>::ClassIt ColIt;
200 IterablePartition<int> row_iter_map;
202 IterablePartition<int> col_iter_map;
204 const int VALID_CLASS;
206 const int INVALID_CLASS;
208 static const _Value INF;
211 LPSolverBase() : row_iter_map(2),
213 VALID_CLASS(0), INVALID_CLASS(1) { }
215 virtual ~LPSolverBase() { }
218 /*! @name Medium level interface (public members)
219 These functions appear in the low level and also in the high level
220 interfaces thus these each of these functions have to be implemented
221 only once in the different interfaces.
222 This means that these functions have to be reimplemented for all of the
223 different lp solvers. These are basic functions, and have the same
224 parameter lists in the low and high level interfaces.
229 //UNCATEGORIZED FUNCTIONS
232 virtual void setMinimize() = 0;
234 virtual void setMaximize() = 0;
239 virtual void solveSimplex() = 0;
241 virtual void solvePrimalSimplex() = 0;
243 virtual void solveDualSimplex() = 0;
246 //SOLUTION RETRIEVING
249 virtual _Value getObjVal() = 0;
254 virtual int rowNum() const = 0;
256 virtual int colNum() const = 0;
258 virtual int warmUp() = 0;
260 virtual void printWarmUpStatus(int i) = 0;
262 virtual int getPrimalStatus() = 0;
264 virtual void printPrimalStatus(int i) = 0;
266 virtual int getDualStatus() = 0;
268 virtual void printDualStatus(int i) = 0;
269 /// Returns the status of the slack variable assigned to row \c row_it.
270 virtual int getRowStat(const RowIt& row_it) = 0;
272 virtual void printRowStatus(int i) = 0;
273 /// Returns the status of the variable assigned to column \c col_it.
274 virtual int getColStat(const ColIt& col_it) = 0;
276 virtual void printColStatus(int i) = 0;
280 /*! @name Low level interface (protected members)
281 Problem manipulating functions in the low level interface
286 //MATRIX MANIPULATING FUNCTIONS
289 virtual int _addCol() = 0;
291 virtual int _addRow() = 0;
293 virtual void _eraseCol(int i) = 0;
295 virtual void _eraseRow(int i) = 0;
297 virtual void _setRowCoeffs(int i,
298 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
300 virtual void _setColCoeffs(int i,
301 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
304 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
307 /// The lower bound of a variable (column) have to be given by an
308 /// extended number of type _Value, i.e. a finite number of type
310 virtual void _setColLowerBound(int i, _Value value) = 0;
312 /// The lower bound of a variable (column) is an
313 /// extended number of type _Value, i.e. a finite number of type
315 virtual _Value _getColLowerBound(int i) = 0;
317 /// The upper bound of a variable (column) have to be given by an
318 /// extended number of type _Value, i.e. a finite number of type
320 virtual void _setColUpperBound(int i, _Value value) = 0;
322 /// The upper bound of a variable (column) is an
323 /// extended number of type _Value, i.e. a finite number of type
325 virtual _Value _getColUpperBound(int i) = 0;
327 /// The lower bound of a linear expression (row) have to be given by an
328 /// extended number of type _Value, i.e. a finite number of type
330 virtual void _setRowLowerBound(int i, _Value value) = 0;
332 /// The lower bound of a linear expression (row) is an
333 /// extended number of type _Value, i.e. a finite number of type
335 virtual _Value _getRowLowerBound(int i) = 0;
337 /// The upper bound of a linear expression (row) have to be given by an
338 /// extended number of type _Value, i.e. a finite number of type
340 virtual void _setRowUpperBound(int i, _Value value) = 0;
342 /// The upper bound of a linear expression (row) is an
343 /// extended number of type _Value, i.e. a finite number of type
345 virtual _Value _getRowUpperBound(int i) = 0;
347 virtual void _setObjCoef(int i, _Value obj_coef) = 0;
349 virtual _Value _getObjCoef(int i) = 0;
351 //SOLUTION RETRIEVING
354 virtual _Value _getPrimal(int i) = 0;
357 /*! @name High level interface (public members)
358 Problem manipulating functions in the high level interface
363 //MATRIX MANIPULATING FUNCTIONS
369 col_iter_map.first(col_it, INVALID_CLASS);
370 if (col_iter_map.valid(col_it)) { //van hasznalhato hely
371 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
372 col_iter_map[col_it]=i;
373 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
374 col_it=col_iter_map.push_back(i, VALID_CLASS);
382 row_iter_map.first(row_it, INVALID_CLASS);
383 if (row_iter_map.valid(row_it)) { //van hasznalhato hely
384 row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
385 row_iter_map[row_it]=i;
386 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
387 row_it=row_iter_map.push_back(i, VALID_CLASS);
392 void eraseCol(const ColIt& col_it) {
393 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
395 cols[1]=col_iter_map[col_it];
397 col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
399 for (col_iter_map.first(it, VALID_CLASS);
400 col_iter_map.valid(it); col_iter_map.next(it)) {
401 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
405 void eraseRow(const RowIt& row_it) {
406 row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
408 rows[1]=row_iter_map[row_it];
410 row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
412 for (row_iter_map.first(it, VALID_CLASS);
413 row_iter_map.valid(it); row_iter_map.next(it)) {
414 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
418 template <typename Begin, typename End>
419 void setRowCoeffs(RowIt row_it, Begin begin, End end) {
420 std::vector<std::pair<int, double> > coeffs;
421 for ( ; begin!=end; ++begin) {
422 coeffs.push_back(std::
423 make_pair(col_iter_map[begin->first], begin->second));
425 _setRowCoeffs(row_iter_map[row_it], coeffs);
428 template <typename Begin, typename End>
429 void setColCoeffs(ColIt col_it, Begin begin, End end) {
430 std::vector<std::pair<int, double> > coeffs;
431 for ( ; begin!=end; ++begin) {
432 coeffs.push_back(std::
433 make_pair(row_iter_map[begin->first], begin->second));
435 _setColCoeffs(col_iter_map[col_it], coeffs);
438 void setColLowerBound(ColIt col_it, _Value lo) {
439 _setColLowerBound(col_iter_map[col_it], lo);
442 _Value getColLowerBound(ColIt col_it) {
443 return _getColLowerBound(col_iter_map[col_it]);
446 void setColUpperBound(ColIt col_it, _Value up) {
447 _setColUpperBound(col_iter_map[col_it], up);
450 _Value getColUpperBound(ColIt col_it) {
451 return _getColUpperBound(col_iter_map[col_it]);
454 void setRowLowerBound(RowIt row_it, _Value lo) {
455 _setRowLowerBound(row_iter_map[row_it], lo);
458 _Value getRowLowerBound(RowIt row_it) {
459 return _getRowLowerBound(row_iter_map[row_it]);
462 void setRowUpperBound(RowIt row_it, _Value up) {
463 _setRowUpperBound(row_iter_map[row_it], up);
466 _Value getRowUpperBound(RowIt row_it) {
467 return _getRowUpperBound(row_iter_map[row_it]);
470 void setObjCoef(const ColIt& col_it, _Value obj_coef) {
471 _setObjCoef(col_iter_map[col_it], obj_coef);
474 _Value getObjCoef(const ColIt& col_it) {
475 return _getObjCoef(col_iter_map[col_it]);
478 //SOLUTION RETRIEVING FUNCTIONS
481 _Value getPrimal(const ColIt& col_it) {
482 return _getPrimal(col_iter_map[col_it]);
487 /*! @name User friend interface
488 Problem manipulating functions in the user friend interface
495 typedef Expr<ColIt, _Value> Expression;
497 typedef Expr<RowIt, _Value> DualExpression;
499 //MATRIX MANIPULATING FUNCTIONS
502 void setRowCoeffs(RowIt row_it, const Expression& expr) {
503 std::vector<std::pair<int, _Value> > row_coeffs;
504 for(typename Expression::Data::const_iterator i=expr.data.begin();
505 i!=expr.data.end(); ++i) {
506 row_coeffs.push_back(std::make_pair
507 (col_iter_map[(*i).first], (*i).second));
509 _setRowCoeffs(row_iter_map[row_it], row_coeffs);
512 void setColCoeffs(ColIt col_it, const DualExpression& expr) {
513 std::vector<std::pair<int, _Value> > col_coeffs;
514 for(typename DualExpression::Data::const_iterator i=expr.data.begin();
515 i!=expr.data.end(); ++i) {
516 col_coeffs.push_back(std::make_pair
517 (row_iter_map[(*i).first], (*i).second));
519 _setColCoeffs(col_iter_map[col_it], col_coeffs);
522 void setObjCoeffs(const Expression& expr) {
523 for(typename Expression::Data::const_iterator i=expr.data.begin();
524 i!=expr.data.end(); ++i) {
525 setObjCoef((*i).first, (*i).second);
531 template <typename _Value>
532 const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
535 /// \brief Wrapper for GLPK solver
537 /// This class implements a lemon wrapper for GLPK.
538 class LPGLPK : public LPSolverBase<double> {
540 typedef LPSolverBase<double> Parent;
549 lp(lpx_create_prob()) {
550 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
557 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
561 lpx_set_obj_dir(lp, LPX_MIN);
565 lpx_set_obj_dir(lp, LPX_MAX);
568 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
573 int i=lpx_add_cols(lp, 1);
574 _setColLowerBound(i, -INF);
575 _setColUpperBound(i, INF);
580 int i=lpx_add_rows(lp, 1);
584 virtual void _setRowCoeffs(int i,
585 const std::vector<std::pair<int, double> >& coeffs) {
586 int mem_length=1+colNum();
587 int* indices = new int[mem_length];
588 double* doubles = new double[mem_length];
590 for (std::vector<std::pair<int, double> >::
591 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
593 indices[length]=it->first;
594 doubles[length]=it->second;
595 // std::cout << " " << indices[length] << " "
596 // << doubles[length] << std::endl;
598 // std::cout << i << " " << length << std::endl;
599 lpx_set_mat_row(lp, i, length, indices, doubles);
604 virtual void _setColCoeffs(int i,
605 const std::vector<std::pair<int, double> >& coeffs) {
606 int mem_length=1+rowNum();
607 int* indices = new int[mem_length];
608 double* doubles = new double[mem_length];
610 for (std::vector<std::pair<int, double> >::
611 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
613 indices[length]=it->first;
614 doubles[length]=it->second;
616 lpx_set_mat_col(lp, i, length, indices, doubles);
621 virtual void _eraseCol(int i) {
624 lpx_del_cols(lp, 1, cols);
626 virtual void _eraseRow(int i) {
629 lpx_del_rows(lp, 1, rows);
631 virtual void _setColLowerBound(int i, double lo) {
635 int b=lpx_get_col_type(lp, i);
636 double up=lpx_get_col_ub(lp, i);
641 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
647 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
656 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
662 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
664 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
671 virtual double _getColLowerBound(int i) {
672 int b=lpx_get_col_type(lp, i);
677 return lpx_get_col_lb(lp, i);
682 return lpx_get_col_lb(lp, i);
688 virtual void _setColUpperBound(int i, double up) {
692 int b=lpx_get_col_type(lp, i);
693 double lo=lpx_get_col_lb(lp, i);
700 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
704 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
712 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
715 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
717 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
720 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
725 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
727 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
734 virtual double _getColUpperBound(int i) {
735 int b=lpx_get_col_type(lp, i);
743 return lpx_get_col_ub(lp, i);
749 virtual void _setRowLowerBound(int i, double lo) {
753 int b=lpx_get_row_type(lp, i);
754 double up=lpx_get_row_ub(lp, i);
759 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
765 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
774 lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
780 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
782 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
789 virtual double _getRowLowerBound(int i) {
790 int b=lpx_get_row_type(lp, i);
795 return lpx_get_row_lb(lp, i);
800 return lpx_get_row_lb(lp, i);
806 virtual void _setRowUpperBound(int i, double up) {
810 int b=lpx_get_row_type(lp, i);
811 double lo=lpx_get_row_lb(lp, i);
818 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
822 lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
830 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
833 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
835 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
838 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
843 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
845 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
852 virtual double _getRowUpperBound(int i) {
853 int b=lpx_get_row_type(lp, i);
861 return lpx_get_row_ub(lp, i);
868 virtual double _getObjCoef(int i) {
869 return lpx_get_obj_coef(lp, i);
872 virtual void _setObjCoef(int i, double obj_coef) {
873 lpx_set_obj_coef(lp, i, obj_coef);
877 void solveSimplex() { lpx_simplex(lp); }
879 void solvePrimalSimplex() { lpx_simplex(lp); }
881 void solveDualSimplex() { lpx_simplex(lp); }
884 virtual double _getPrimal(int i) {
885 return lpx_get_col_prim(lp, i);
889 double getObjVal() { return lpx_get_obj_val(lp); }
891 int rowNum() const { return lpx_get_num_rows(lp); }
893 int colNum() const { return lpx_get_num_cols(lp); }
895 int warmUp() { return lpx_warm_up(lp); }
897 void printWarmUpStatus(int i) {
899 case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
900 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
901 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
902 case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
906 int getPrimalStatus() { return lpx_get_prim_stat(lp); }
908 void printPrimalStatus(int i) {
910 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
911 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
912 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
913 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
917 int getDualStatus() { return lpx_get_dual_stat(lp); }
919 void printDualStatus(int i) {
921 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
922 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
923 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
924 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
927 /// Returns the status of the slack variable assigned to row \c row_it.
928 int getRowStat(const RowIt& row_it) {
929 return lpx_get_row_stat(lp, row_iter_map[row_it]);
932 void printRowStatus(int i) {
934 case LPX_BS: cout << "LPX_BS" << endl; break;
935 case LPX_NL: cout << "LPX_NL" << endl; break;
936 case LPX_NU: cout << "LPX_NU" << endl; break;
937 case LPX_NF: cout << "LPX_NF" << endl; break;
938 case LPX_NS: cout << "LPX_NS" << endl; break;
941 /// Returns the status of the variable assigned to column \c col_it.
942 int getColStat(const ColIt& col_it) {
943 return lpx_get_col_stat(lp, col_iter_map[col_it]);
946 void printColStatus(int i) {
948 case LPX_BS: cout << "LPX_BS" << endl; break;
949 case LPX_NL: cout << "LPX_NL" << endl; break;
950 case LPX_NU: cout << "LPX_NU" << endl; break;
951 case LPX_NF: cout << "LPX_NF" << endl; break;
952 case LPX_NS: cout << "LPX_NS" << endl; break;
961 #endif //LEMON_LP_SOLVER_WRAPPER_H