2 #ifndef LEMON_LP_SOLVER_WRAPPER_H
3 #define LEMON_LP_SOLVER_WRAPPER_H
7 ///\brief Dijkstra algorithm.
27 //#include <sage_graph.h>
28 //#include <lemon/list_graph.h>
29 //#include <lemon/graph_wrapper.h>
30 #include <lemon/invalid.h>
31 #include <expression.h>
32 //#include <bfs_dfs.h>
34 //#include <lemon/max_flow.h>
35 //#include <augmenting_flow.h>
36 //#include <iter_map.h>
47 /// \brief A partitioned vector with iterable classes.
49 /// This class implements a container in which the data is stored in an
50 /// stl vector, the range is partitioned into sets and each set is
51 /// doubly linked in a list.
52 /// That is, each class is iterable by lemon iterators, and any member of
53 /// the vector can bo moved to an other class.
55 class IterablePartition {
59 int prev; //invalid az -1
62 std::vector<Node> nodes;
67 std::vector<Tip> tips;
69 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
70 int classNum() const { return tips.size(); }
71 /// This lemon style iterator iterates through a class.
73 /// Constructor. The number of classes is to be given which is fixed
74 /// over the life of the container.
75 /// The partition classes are indexed from 0 to class_num-1.
76 IterablePartition(int class_num) {
77 for (int i=0; i<class_num; ++i) {
84 void befuz(ClassIt it, int class_id) {
85 if (tips[class_id].first==-1) {
86 if (tips[class_id].last==-1) {
87 nodes[it.i].prev=nodes[it.i].next=-1;
88 tips[class_id].first=tips[class_id].last=it.i;
91 nodes[it.i].prev=tips[class_id].last;
93 nodes[tips[class_id].last].next=it.i;
94 tips[class_id].last=it.i;
97 void kifuz(ClassIt it, int class_id) {
98 if (tips[class_id].first==it.i) {
99 if (tips[class_id].last==it.i) {
100 tips[class_id].first=tips[class_id].last=-1;
102 tips[class_id].first=nodes[it.i].next;
103 nodes[nodes[it.i].next].prev=-1;
106 if (tips[class_id].last==it.i) {
107 tips[class_id].last=nodes[it.i].prev;
108 nodes[nodes[it.i].prev].next=-1;
110 nodes[nodes[it.i].next].prev=nodes[it.i].prev;
111 nodes[nodes[it.i].prev].next=nodes[it.i].next;
116 /// A new element with data \c t is pushed into the vector and into class
118 ClassIt push_back(const T& t, int class_id) {
122 int i=nodes.size()-1;
126 /// A member is moved to an other class.
127 void set(ClassIt it, int old_class_id, int new_class_id) {
128 kifuz(it.i, old_class_id);
129 befuz(it.i, new_class_id);
131 /// Returns the data pointed by \c it.
132 T& operator[](ClassIt it) { return nodes[it.i].data; }
133 /// Returns the data pointed by \c it.
134 const T& operator[](ClassIt it) const { return nodes[it.i].data; }
137 friend class IterablePartition;
141 /// Default constructor.
143 /// This constructor constructs an iterator which points
144 /// to the member of th container indexed by the integer _i.
145 ClassIt(const int& _i) : i(_i) { }
146 /// Invalid constructor.
147 ClassIt(const Invalid&) : i(-1) { }
148 friend bool operator<(const ClassIt& x, const ClassIt& y);
149 friend std::ostream& operator<<(std::ostream& os,
152 friend bool operator<(const ClassIt& x, const ClassIt& y) {
155 friend std::ostream& operator<<(std::ostream& os,
160 /// First member of class \c class_id.
161 ClassIt& first(ClassIt& it, int class_id) const {
162 it.i=tips[class_id].first;
166 ClassIt& next(ClassIt& it) const {
167 it.i=nodes[it.i].next;
170 /// True iff the iterator is valid.
171 bool valid(const ClassIt& it) const { return it.i!=-1; }
177 \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
178 \todo LEKERDEZESEK!!!
179 \todo DOKSI!!!! Doxygen group!!!
182 template <typename _Value>
186 typedef _Value Value;
188 typedef IterablePartition<int>::ClassIt RowIt;
190 typedef IterablePartition<int>::ClassIt ColIt;
193 IterablePartition<int> row_iter_map;
195 IterablePartition<int> col_iter_map;
197 const int VALID_CLASS;
199 const int INVALID_CLASS;
201 static const _Value INF;
204 LPSolverBase() : row_iter_map(2),
206 VALID_CLASS(0), INVALID_CLASS(1) { }
208 virtual ~LPSolverBase() { }
210 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
214 virtual void setMinimize() = 0;
216 virtual void setMaximize() = 0;
218 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
222 virtual int _addRow() = 0;
224 virtual int _addCol() = 0;
226 virtual void _setRowCoeffs(int i,
227 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
229 virtual void _setColCoeffs(int i,
230 const std::vector<std::pair<int, _Value> >& coeffs) = 0;
232 virtual void _eraseCol(int i) = 0;
234 virtual void _eraseRow(int i) = 0;
237 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
240 /// The lower bound of a variable (column) have to be given by an
241 /// extended number of type _Value, i.e. a finite number of type
243 virtual void _setColLowerBound(int i, _Value value) = 0;
245 /// The upper bound of a variable (column) have to be given by an
246 /// extended number of type _Value, i.e. a finite number of type
248 virtual void _setColUpperBound(int i, _Value value) = 0;
250 /// The lower bound of a variable (column) is an
251 /// extended number of type _Value, i.e. a finite number of type
253 virtual _Value _getColLowerBound(int i) = 0;
255 /// The upper bound of a variable (column) is an
256 /// extended number of type _Value, i.e. a finite number of type
258 virtual _Value _getColUpperBound(int i) = 0;
260 virtual void _setColBounds(int i, Bound bound,
261 _Value lo, _Value up) = 0;
263 virtual void _setRowBounds(int i, Bound bound,
264 _Value lo, _Value up) = 0;
266 virtual void _setObjCoef(int i, _Value obj_coef) = 0;
268 virtual _Value _getObjCoef(int i) = 0;
270 //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
273 virtual _Value _getPrimal(int i) = 0;
275 //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
282 row_iter_map.first(row_it, INVALID_CLASS);
283 if (row_iter_map.valid(row_it)) { //van hasznalhato hely
284 row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
285 row_iter_map[row_it]=i;
286 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
287 row_it=row_iter_map.push_back(i, VALID_CLASS);
295 col_iter_map.first(col_it, INVALID_CLASS);
296 if (col_iter_map.valid(col_it)) { //van hasznalhato hely
297 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
298 col_iter_map[col_it]=i;
299 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
300 col_it=col_iter_map.push_back(i, VALID_CLASS);
305 template <typename Begin, typename End>
306 void setRowCoeffs(RowIt row_it, Begin begin, End end) {
307 std::vector<std::pair<int, double> > coeffs;
308 for ( ; begin!=end; ++begin) {
309 coeffs.push_back(std::
310 make_pair(col_iter_map[begin->first], begin->second));
312 _setRowCoeffs(row_iter_map[row_it], coeffs);
315 template <typename Begin, typename End>
316 void setColCoeffs(ColIt col_it, Begin begin, End end) {
317 std::vector<std::pair<int, double> > coeffs;
318 for ( ; begin!=end; ++begin) {
319 coeffs.push_back(std::
320 make_pair(row_iter_map[begin->first], begin->second));
322 _setColCoeffs(col_iter_map[col_it], coeffs);
325 void eraseCol(const ColIt& col_it) {
326 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
328 cols[1]=col_iter_map[col_it];
330 col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
332 for (col_iter_map.first(it, VALID_CLASS);
333 col_iter_map.valid(it); col_iter_map.next(it)) {
334 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
338 void eraseRow(const RowIt& row_it) {
339 row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
341 rows[1]=row_iter_map[row_it];
343 row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
345 for (row_iter_map.first(it, VALID_CLASS);
346 row_iter_map.valid(it); row_iter_map.next(it)) {
347 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
351 void setColLowerBound(ColIt col_it, _Value lo) {
352 _setColLowerBound(col_iter_map[col_it], lo);
355 void setColUpperBound(ColIt col_it, _Value up) {
356 _setColUpperBound(col_iter_map[col_it], up);
359 _Value getColLowerBound(ColIt col_it) {
360 return _getColLowerBound(col_iter_map[col_it]);
363 _Value getColUpperBound(ColIt col_it) {
364 return _getColUpperBound(col_iter_map[col_it]);
367 void setColBounds(const ColIt& col_it, Bound bound,
368 _Value lo, _Value up) {
369 _setColBounds(col_iter_map[col_it], bound, lo, up);
372 void setRowBounds(const RowIt& row_it, Bound bound,
373 _Value lo, _Value up) {
374 _setRowBounds(row_iter_map[row_it], bound, lo, up);
377 void setObjCoef(const ColIt& col_it, _Value obj_coef) {
378 _setObjCoef(col_iter_map[col_it], obj_coef);
381 _Value getObjCoef(const ColIt& col_it) {
382 return _getObjCoef(col_iter_map[col_it]);
385 //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
388 typedef Expr<ColIt, _Value> Expression;
390 typedef Expr<RowIt, _Value> DualExpression;
392 void setRowCoeffs(RowIt row_it, const Expression& expr) {
393 std::vector<std::pair<int, _Value> > row_coeffs;
394 for(typename Expression::Data::const_iterator i=expr.data.begin();
395 i!=expr.data.end(); ++i) {
396 row_coeffs.push_back(std::make_pair
397 (col_iter_map[(*i).first], (*i).second));
399 _setRowCoeffs(row_iter_map[row_it], row_coeffs);
402 void setColCoeffs(ColIt col_it, const DualExpression& expr) {
403 std::vector<std::pair<int, _Value> > col_coeffs;
404 for(typename DualExpression::Data::const_iterator i=expr.data.begin();
405 i!=expr.data.end(); ++i) {
406 col_coeffs.push_back(std::make_pair
407 (row_iter_map[(*i).first], (*i).second));
409 _setColCoeffs(col_iter_map[col_it], col_coeffs);
412 void setObjCoeffs(const Expression& expr) {
413 for(typename Expression::Data::const_iterator i=expr.data.begin();
414 i!=expr.data.end(); ++i) {
415 setObjCoef((*i).first, (*i).second);
421 virtual void solveSimplex() = 0;
423 virtual void solvePrimalSimplex() = 0;
425 virtual void solveDualSimplex() = 0;
428 //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
431 _Value getPrimal(const ColIt& col_it) {
432 return _getPrimal(col_iter_map[col_it]);
435 virtual _Value getObjVal() = 0;
440 virtual int rowNum() const = 0;
442 virtual int colNum() const = 0;
444 virtual int warmUp() = 0;
446 virtual void printWarmUpStatus(int i) = 0;
448 virtual int getPrimalStatus() = 0;
450 virtual void printPrimalStatus(int i) = 0;
452 virtual int getDualStatus() = 0;
454 virtual void printDualStatus(int i) = 0;
455 /// Returns the status of the slack variable assigned to row \c row_it.
456 virtual int getRowStat(const RowIt& row_it) = 0;
458 virtual void printRowStatus(int i) = 0;
459 /// Returns the status of the variable assigned to column \c col_it.
460 virtual int getColStat(const ColIt& col_it) = 0;
462 virtual void printColStatus(int i) = 0;
465 template <typename _Value>
466 const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
469 /// \brief Wrappers for LP solvers
471 /// This class implements a lemon wrapper for glpk.
472 /// Later other LP-solvers will be wrapped into lemon.
473 /// The aim of this class is to give a general surface to different
474 /// solvers, i.e. it makes possible to write algorithms using LP's,
475 /// in which the solver can be changed to an other one easily.
476 class LPGLPK : public LPSolverBase<double> {
478 typedef LPSolverBase<double> Parent;
487 lp(lpx_create_prob()) {
488 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
495 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
499 lpx_set_obj_dir(lp, LPX_MIN);
503 lpx_set_obj_dir(lp, LPX_MAX);
506 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
511 int i=lpx_add_cols(lp, 1);
512 _setColLowerBound(i, -INF);
513 _setColUpperBound(i, INF);
518 int i=lpx_add_rows(lp, 1);
522 virtual void _setRowCoeffs(int i,
523 const std::vector<std::pair<int, double> >& coeffs) {
524 int mem_length=1+colNum();
525 int* indices = new int[mem_length];
526 double* doubles = new double[mem_length];
528 for (std::vector<std::pair<int, double> >::
529 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
531 indices[length]=it->first;
532 doubles[length]=it->second;
533 // std::cout << " " << indices[length] << " "
534 // << doubles[length] << std::endl;
536 // std::cout << i << " " << length << std::endl;
537 lpx_set_mat_row(lp, i, length, indices, doubles);
542 virtual void _setColCoeffs(int i,
543 const std::vector<std::pair<int, double> >& coeffs) {
544 int mem_length=1+rowNum();
545 int* indices = new int[mem_length];
546 double* doubles = new double[mem_length];
548 for (std::vector<std::pair<int, double> >::
549 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
551 indices[length]=it->first;
552 doubles[length]=it->second;
554 lpx_set_mat_col(lp, i, length, indices, doubles);
559 virtual void _eraseCol(int i) {
562 lpx_del_cols(lp, 1, cols);
564 virtual void _eraseRow(int i) {
567 lpx_del_rows(lp, 1, rows);
569 virtual void _setColLowerBound(int i, double lo) {
573 int b=lpx_get_col_type(lp, i);
574 double up=lpx_get_col_ub(lp, i);
579 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
585 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
594 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
600 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
602 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
609 virtual void _setColUpperBound(int i, double up) {
613 int b=lpx_get_col_type(lp, i);
614 double lo=lpx_get_col_lb(lp, i);
621 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
625 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
633 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
636 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
638 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
641 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
646 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
648 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
655 virtual double _getColLowerBound(int i) {
656 int b=lpx_get_col_type(lp, i);
661 return lpx_get_col_lb(lp, i);
666 return lpx_get_col_lb(lp, i);
672 virtual double _getColUpperBound(int i) {
673 int b=lpx_get_col_type(lp, i);
681 return lpx_get_col_ub(lp, i);
687 virtual void _setColBounds(int i, Bound bound,
688 double lo, double up) {
691 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
694 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
697 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
700 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
703 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
707 virtual void _setRowBounds(int i, Bound bound,
708 double lo, double up) {
711 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
714 lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
717 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
720 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
723 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
729 virtual double _getObjCoef(int i) {
730 return lpx_get_obj_coef(lp, i);
733 virtual void _setObjCoef(int i, double obj_coef) {
734 lpx_set_obj_coef(lp, i, obj_coef);
738 void solveSimplex() { lpx_simplex(lp); }
740 void solvePrimalSimplex() { lpx_simplex(lp); }
742 void solveDualSimplex() { lpx_simplex(lp); }
745 virtual double _getPrimal(int i) {
746 return lpx_get_col_prim(lp, i);
750 double getObjVal() { return lpx_get_obj_val(lp); }
752 int rowNum() const { return lpx_get_num_rows(lp); }
754 int colNum() const { return lpx_get_num_cols(lp); }
756 int warmUp() { return lpx_warm_up(lp); }
758 void printWarmUpStatus(int i) {
760 case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
761 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
762 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
763 case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
767 int getPrimalStatus() { return lpx_get_prim_stat(lp); }
769 void printPrimalStatus(int i) {
771 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
772 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
773 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
774 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
778 int getDualStatus() { return lpx_get_dual_stat(lp); }
780 void printDualStatus(int i) {
782 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
783 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
784 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
785 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
788 /// Returns the status of the slack variable assigned to row \c row_it.
789 int getRowStat(const RowIt& row_it) {
790 return lpx_get_row_stat(lp, row_iter_map[row_it]);
793 void printRowStatus(int i) {
795 case LPX_BS: cout << "LPX_BS" << endl; break;
796 case LPX_NL: cout << "LPX_NL" << endl; break;
797 case LPX_NU: cout << "LPX_NU" << endl; break;
798 case LPX_NF: cout << "LPX_NF" << endl; break;
799 case LPX_NS: cout << "LPX_NS" << endl; break;
802 /// Returns the status of the variable assigned to column \c col_it.
803 int getColStat(const ColIt& col_it) {
804 return lpx_get_col_stat(lp, col_iter_map[col_it]);
807 void printColStatus(int i) {
809 case LPX_BS: cout << "LPX_BS" << endl; break;
810 case LPX_NL: cout << "LPX_NL" << endl; break;
811 case LPX_NU: cout << "LPX_NU" << endl; break;
812 case LPX_NF: cout << "LPX_NF" << endl; break;
813 case LPX_NS: cout << "LPX_NS" << endl; break;
822 #endif //LEMON_LP_SOLVER_WRAPPER_H