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 kellenene uj iterable structure bele, mert ez nem az igazi
175 \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
176 \todo LEKERDEZESEK!!!
177 \todo DOKSI!!!! Doxygen group!!!
178 The aim of this class is to give a general surface to different
179 solvers, i.e. it makes possible to write algorithms using LP's,
180 in which the solver can be changed to an other one easily.
183 template <typename _Value>
186 /*! @name Uncategorized functions and types (public members)
194 typedef _Value Value;
196 typedef IterablePartition<int>::ClassIt Row;
198 typedef IterablePartition<int>::ClassIt Col;
201 IterablePartition<int> row_iter_map;
203 IterablePartition<int> col_iter_map;
205 std::vector<Row> int_row_map;
207 std::vector<Col> int_col_map;
209 const int VALID_CLASS;
211 const int INVALID_CLASS;
213 static const _Value INF;
216 LPSolverBase() : row_iter_map(2),
218 VALID_CLASS(0), INVALID_CLASS(1) { }
220 virtual ~LPSolverBase() { }
223 /*! @name Medium level interface (public members)
224 These functions appear in the low level and also in the high level
225 interfaces thus these each of these functions have to be implemented
226 only once in the different interfaces.
227 This means that these functions have to be reimplemented for all of the
228 different lp solvers. These are basic functions, and have the same
229 parameter lists in the low and high level interfaces.
234 //UNCATEGORIZED FUNCTIONS
237 virtual void setMinimize() = 0;
239 virtual void setMaximize() = 0;
244 virtual void solveSimplex() = 0;
246 virtual void solvePrimalSimplex() = 0;
248 virtual void solveDualSimplex() = 0;
251 //SOLUTION RETRIEVING
254 virtual _Value getObjVal() = 0;
259 virtual int rowNum() const = 0;
261 virtual int colNum() const = 0;
263 virtual int warmUp() = 0;
265 virtual void printWarmUpStatus(int i) = 0;
267 virtual int getPrimalStatus() = 0;
269 virtual void printPrimalStatus(int i) = 0;
271 virtual int getDualStatus() = 0;
273 virtual void printDualStatus(int i) = 0;
274 /// Returns the status of the slack variable assigned to row \c row.
275 virtual int getRowStat(const Row& row) = 0;
277 virtual void printRowStatus(int i) = 0;
278 /// Returns the status of the variable assigned to column \c col.
279 virtual int getColStat(const Col& col) = 0;
281 virtual void printColStatus(int i) = 0;
285 /*! @name Low level interface (protected members)
286 Problem manipulating functions in the low level interface
291 //MATRIX MANIPULATING FUNCTIONS
294 virtual int _addCol() = 0;
296 virtual int _addRow() = 0;
298 virtual void _eraseCol(int i) = 0;
300 virtual void _eraseRow(int i) = 0;
302 virtual void _setRowCoeffs(int i,
303 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
305 /// This routine modifies \c coeffs only by the \c push_back method.
306 virtual void _getRowCoeffs(int i,
307 std::vector<std::pair<int, _Value> >& coeffs) = 0;
308 virtual void _setColCoeffs(int i,
309 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
311 /// This routine modifies \c coeffs only by the \c push_back method.
312 virtual void _getColCoeffs(int i,
313 std::vector<std::pair<int, _Value> >& coeffs) = 0;
316 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
319 /// The lower bound of a variable (column) have to be given by an
320 /// extended number of type _Value, i.e. a finite number of type
322 virtual void _setColLowerBound(int i, _Value value) = 0;
324 /// The lower bound of a variable (column) is an
325 /// extended number of type _Value, i.e. a finite number of type
327 virtual _Value _getColLowerBound(int i) = 0;
329 /// The upper bound of a variable (column) have to be given by an
330 /// extended number of type _Value, i.e. a finite number of type
332 virtual void _setColUpperBound(int i, _Value value) = 0;
334 /// The upper bound of a variable (column) is an
335 /// extended number of type _Value, i.e. a finite number of type
337 virtual _Value _getColUpperBound(int i) = 0;
339 /// The lower bound of a linear expression (row) have to be given by an
340 /// extended number of type _Value, i.e. a finite number of type
342 virtual void _setRowLowerBound(int i, _Value value) = 0;
344 /// The lower bound of a linear expression (row) is an
345 /// extended number of type _Value, i.e. a finite number of type
347 virtual _Value _getRowLowerBound(int i) = 0;
349 /// The upper bound of a linear expression (row) have to be given by an
350 /// extended number of type _Value, i.e. a finite number of type
352 virtual void _setRowUpperBound(int i, _Value value) = 0;
354 /// The upper bound of a linear expression (row) is an
355 /// extended number of type _Value, i.e. a finite number of type
357 virtual _Value _getRowUpperBound(int i) = 0;
359 virtual void _setObjCoef(int i, _Value obj_coef) = 0;
361 virtual _Value _getObjCoef(int i) = 0;
363 //SOLUTION RETRIEVING
366 virtual _Value _getPrimal(int i) = 0;
369 /*! @name High level interface (public members)
370 Problem manipulating functions in the high level interface
375 //MATRIX MANIPULATING FUNCTIONS
381 col_iter_map.first(col, INVALID_CLASS);
382 if (col_iter_map.valid(col)) { //van hasznalhato hely
383 col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
385 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
386 col=col_iter_map.push_back(i, VALID_CLASS);
388 int_col_map.push_back(col);
395 row_iter_map.first(row, INVALID_CLASS);
396 if (row_iter_map.valid(row)) { //van hasznalhato hely
397 row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
399 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
400 row=row_iter_map.push_back(i, VALID_CLASS);
402 int_row_map.push_back(row);
406 void eraseCol(const Col& col) {
407 col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
409 cols[1]=col_iter_map[col];
411 col_iter_map[col]=0; //glpk specifikus, de kell ez??
413 for (col_iter_map.first(it, VALID_CLASS);
414 col_iter_map.valid(it); col_iter_map.next(it)) {
415 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
417 int_col_map.erase(int_col_map.begin()+cols[1]);
420 void eraseRow(const Row& row) {
421 row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
423 rows[1]=row_iter_map[row];
425 row_iter_map[row]=0; //glpk specifikus, de kell ez??
427 for (row_iter_map.first(it, VALID_CLASS);
428 row_iter_map.valid(it); row_iter_map.next(it)) {
429 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
431 int_row_map.erase(int_row_map.begin()+rows[1]);
434 void setColLowerBound(Col col, _Value lo) {
435 _setColLowerBound(col_iter_map[col], lo);
438 _Value getColLowerBound(Col col) {
439 return _getColLowerBound(col_iter_map[col]);
442 void setColUpperBound(Col col, _Value up) {
443 _setColUpperBound(col_iter_map[col], up);
446 _Value getColUpperBound(Col col) {
447 return _getColUpperBound(col_iter_map[col]);
450 void setRowLowerBound(Row row, _Value lo) {
451 _setRowLowerBound(row_iter_map[row], lo);
454 _Value getRowLowerBound(Row row) {
455 return _getRowLowerBound(row_iter_map[row]);
458 void setRowUpperBound(Row row, _Value up) {
459 _setRowUpperBound(row_iter_map[row], up);
462 _Value getRowUpperBound(Row row) {
463 return _getRowUpperBound(row_iter_map[row]);
466 void setObjCoef(const Col& col, _Value obj_coef) {
467 _setObjCoef(col_iter_map[col], obj_coef);
470 _Value getObjCoef(const Col& col) {
471 return _getObjCoef(col_iter_map[col]);
474 //SOLUTION RETRIEVING FUNCTIONS
477 _Value getPrimal(const Col& col) {
478 return _getPrimal(col_iter_map[col]);
483 /*! @name User friend interface
484 Problem manipulating functions in the user friend interface
491 typedef Expr<Col, _Value> Expression;
493 typedef Expr<Row, _Value> DualExpression;
495 typedef Constr<Col, _Value> Constraint;
497 //MATRIX MANIPULATING FUNCTIONS
500 void setRowCoeffs(Row row, const Expression& expr) {
501 std::vector<std::pair<int, _Value> > row_coeffs;
502 for(typename Expression::Data::const_iterator i=expr.data.begin();
503 i!=expr.data.end(); ++i) {
504 row_coeffs.push_back(std::make_pair
505 (col_iter_map[(*i).first], (*i).second));
507 _setRowCoeffs(row_iter_map[row], row_coeffs);
510 void setRow(Row row, const Constraint& constr) {
511 setRowCoeffs(row, constr.expr);
512 setRowLowerBound(row, constr.lo);
513 setRowUpperBound(row, constr.up);
516 Row addRow(const Constraint& constr) {
518 setRowCoeffs(row, constr.expr);
519 setRowLowerBound(row, constr.lo);
520 setRowUpperBound(row, constr.up);
524 /// This routine modifies \c expr by only adding to it.
525 void getRowCoeffs(Row row, Expression& expr) {
526 std::vector<std::pair<int, _Value> > row_coeffs;
527 _getRowCoeffs(row_iter_map[row], row_coeffs);
528 for(typename std::vector<std::pair<int, _Value> >::const_iterator
529 i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
530 expr+= (*i).second*int_col_map[(*i).first];
534 void setColCoeffs(Col col, const DualExpression& expr) {
535 std::vector<std::pair<int, _Value> > col_coeffs;
536 for(typename DualExpression::Data::const_iterator i=expr.data.begin();
537 i!=expr.data.end(); ++i) {
538 col_coeffs.push_back(std::make_pair
539 (row_iter_map[(*i).first], (*i).second));
541 _setColCoeffs(col_iter_map[col], col_coeffs);
544 /// This routine modifies \c expr by only adding to it.
545 void getColCoeffs(Col col, DualExpression& expr) {
546 std::vector<std::pair<int, _Value> > col_coeffs;
547 _getColCoeffs(col_iter_map[col], col_coeffs);
548 for(typename std::vector<std::pair<int, _Value> >::const_iterator
549 i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
550 expr+= (*i).second*int_row_map[(*i).first];
554 /// \bug ez igy nem jo
555 void setObjCoeffs(const Expression& expr) {
556 for(typename Expression::Data::const_iterator i=expr.data.begin();
557 i!=expr.data.end(); ++i) {
558 setObjCoef((*i).first, (*i).second);
562 /// This routine modifies \c expr by only adding to it.
563 void getObjCoeffs(Expression& expr) {
564 /// FIXME not yet implemented
569 template <typename _Value>
570 const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
573 /// \brief Wrapper for GLPK solver
575 /// This class implements a lemon wrapper for GLPK.
576 class LPGLPK : public LPSolverBase<double> {
578 typedef LPSolverBase<double> Parent;
587 lp(lpx_create_prob()) {
588 int_row_map.push_back(Row());
589 int_col_map.push_back(Col());
590 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
597 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
601 lpx_set_obj_dir(lp, LPX_MIN);
605 lpx_set_obj_dir(lp, LPX_MAX);
608 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
613 int i=lpx_add_cols(lp, 1);
614 _setColLowerBound(i, -INF);
615 _setColUpperBound(i, INF);
620 int i=lpx_add_rows(lp, 1);
624 virtual void _setRowCoeffs(int i,
625 const std::vector<std::pair<int, double> >& coeffs) {
626 int mem_length=1+colNum();
627 int* indices = new int[mem_length];
628 double* doubles = new double[mem_length];
630 for (std::vector<std::pair<int, double> >::
631 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
633 indices[length]=it->first;
634 doubles[length]=it->second;
636 lpx_set_mat_row(lp, i, length, indices, doubles);
641 virtual void _getRowCoeffs(int i,
642 std::vector<std::pair<int, double> >& coeffs) {
643 int mem_length=1+colNum();
644 int* indices = new int[mem_length];
645 double* doubles = new double[mem_length];
646 int length=lpx_get_mat_row(lp, i, indices, doubles);
647 for (int i=1; i<=length; ++i) {
648 coeffs.push_back(std::make_pair(indices[i], doubles[i]));
654 virtual void _setColCoeffs(int i,
655 const std::vector<std::pair<int, double> >& coeffs) {
656 int mem_length=1+rowNum();
657 int* indices = new int[mem_length];
658 double* doubles = new double[mem_length];
660 for (std::vector<std::pair<int, double> >::
661 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
663 indices[length]=it->first;
664 doubles[length]=it->second;
666 lpx_set_mat_col(lp, i, length, indices, doubles);
671 virtual void _getColCoeffs(int i,
672 std::vector<std::pair<int, double> >& coeffs) {
673 int mem_length=1+rowNum();
674 int* indices = new int[mem_length];
675 double* doubles = new double[mem_length];
676 int length=lpx_get_mat_col(lp, i, indices, doubles);
677 for (int i=1; i<=length; ++i) {
678 coeffs.push_back(std::make_pair(indices[i], doubles[i]));
684 virtual void _eraseCol(int i) {
687 lpx_del_cols(lp, 1, cols);
689 virtual void _eraseRow(int i) {
692 lpx_del_rows(lp, 1, rows);
694 virtual void _setColLowerBound(int i, double lo) {
698 int b=lpx_get_col_type(lp, i);
699 double up=lpx_get_col_ub(lp, i);
704 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
710 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
719 lpx_set_col_bnds(lp, i, LPX_LO, 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 _getColLowerBound(int i) {
735 int b=lpx_get_col_type(lp, i);
740 return lpx_get_col_lb(lp, i);
745 return lpx_get_col_lb(lp, i);
751 virtual void _setColUpperBound(int i, double up) {
755 int b=lpx_get_col_type(lp, i);
756 double lo=lpx_get_col_lb(lp, i);
763 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
767 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
775 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
778 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
780 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
783 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
788 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
790 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
797 virtual double _getColUpperBound(int i) {
798 int b=lpx_get_col_type(lp, i);
806 return lpx_get_col_ub(lp, i);
812 virtual void _setRowLowerBound(int i, double lo) {
816 int b=lpx_get_row_type(lp, i);
817 double up=lpx_get_row_ub(lp, i);
822 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
828 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
837 lpx_set_row_bnds(lp, i, LPX_LO, 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 _getRowLowerBound(int i) {
853 int b=lpx_get_row_type(lp, i);
858 return lpx_get_row_lb(lp, i);
863 return lpx_get_row_lb(lp, i);
869 virtual void _setRowUpperBound(int i, double up) {
873 int b=lpx_get_row_type(lp, i);
874 double lo=lpx_get_row_lb(lp, i);
881 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
885 lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
893 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
896 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
898 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
901 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
906 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
908 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
915 virtual double _getRowUpperBound(int i) {
916 int b=lpx_get_row_type(lp, i);
924 return lpx_get_row_ub(lp, i);
931 virtual double _getObjCoef(int i) {
932 return lpx_get_obj_coef(lp, i);
935 virtual void _setObjCoef(int i, double obj_coef) {
936 lpx_set_obj_coef(lp, i, obj_coef);
940 void solveSimplex() { lpx_simplex(lp); }
942 void solvePrimalSimplex() { lpx_simplex(lp); }
944 void solveDualSimplex() { lpx_simplex(lp); }
947 virtual double _getPrimal(int i) {
948 return lpx_get_col_prim(lp, i);
952 double getObjVal() { return lpx_get_obj_val(lp); }
954 int rowNum() const { return lpx_get_num_rows(lp); }
956 int colNum() const { return lpx_get_num_cols(lp); }
958 int warmUp() { return lpx_warm_up(lp); }
960 void printWarmUpStatus(int i) {
962 case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
963 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
964 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
965 case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
969 int getPrimalStatus() { return lpx_get_prim_stat(lp); }
971 void printPrimalStatus(int i) {
973 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
974 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
975 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
976 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
980 int getDualStatus() { return lpx_get_dual_stat(lp); }
982 void printDualStatus(int i) {
984 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
985 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
986 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
987 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
990 /// Returns the status of the slack variable assigned to row \c row.
991 int getRowStat(const Row& row) {
992 return lpx_get_row_stat(lp, row_iter_map[row]);
995 void printRowStatus(int i) {
997 case LPX_BS: cout << "LPX_BS" << endl; break;
998 case LPX_NL: cout << "LPX_NL" << endl; break;
999 case LPX_NU: cout << "LPX_NU" << endl; break;
1000 case LPX_NF: cout << "LPX_NF" << endl; break;
1001 case LPX_NS: cout << "LPX_NS" << endl; break;
1004 /// Returns the status of the variable assigned to column \c col.
1005 int getColStat(const Col& col) {
1006 return lpx_get_col_stat(lp, col_iter_map[col]);
1009 void printColStatus(int i) {
1011 case LPX_BS: cout << "LPX_BS" << endl; break;
1012 case LPX_NL: cout << "LPX_NL" << endl; break;
1013 case LPX_NU: cout << "LPX_NU" << endl; break;
1014 case LPX_NF: cout << "LPX_NF" << endl; break;
1015 case LPX_NS: cout << "LPX_NS" << endl; break;
1024 #endif //LEMON_LP_SOLVER_WRAPPER_H