2 #ifndef LEMON_LP_SOLVER_WRAPPER_H
3 #define LEMON_LP_SOLVER_WRAPPER_H
7 ///\brief Dijkstra algorithm.
26 //#include <sage_graph.h>
27 //#include <lemon/list_graph.h>
28 //#include <lemon/graph_wrapper.h>
29 #include <lemon/invalid.h>
30 #include <expression.h>
31 //#include <bfs_dfs.h>
33 //#include <lemon/max_flow.h>
34 //#include <augmenting_flow.h>
35 //#include <iter_map.h>
46 /// \brief A partitioned vector with iterable classes.
48 /// This class implements a container in which the data is stored in an
49 /// stl vector, the range is partitioned into sets and each set is
50 /// doubly linked in a list.
51 /// That is, each class is iterable by lemon iterators, and any member of
52 /// the vector can bo moved to an other class.
54 class IterablePartition {
58 int prev; //invalid az -1
61 std::vector<Node> nodes;
66 std::vector<Tip> tips;
68 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
69 int classNum() const { return tips.size(); }
70 /// This lemon style iterator iterates through a class.
72 /// Constructor. The number of classes is to be given which is fixed
73 /// over the life of the container.
74 /// The partition classes are indexed from 0 to class_num-1.
75 IterablePartition(int class_num) {
76 for (int i=0; i<class_num; ++i) {
83 void befuz(ClassIt it, int class_id) {
84 if (tips[class_id].first==-1) {
85 if (tips[class_id].last==-1) {
86 nodes[it.i].prev=nodes[it.i].next=-1;
87 tips[class_id].first=tips[class_id].last=it.i;
90 nodes[it.i].prev=tips[class_id].last;
92 nodes[tips[class_id].last].next=it.i;
93 tips[class_id].last=it.i;
96 void kifuz(ClassIt it, int class_id) {
97 if (tips[class_id].first==it.i) {
98 if (tips[class_id].last==it.i) {
99 tips[class_id].first=tips[class_id].last=-1;
101 tips[class_id].first=nodes[it.i].next;
102 nodes[nodes[it.i].next].prev=-1;
105 if (tips[class_id].last==it.i) {
106 tips[class_id].last=nodes[it.i].prev;
107 nodes[nodes[it.i].prev].next=-1;
109 nodes[nodes[it.i].next].prev=nodes[it.i].prev;
110 nodes[nodes[it.i].prev].next=nodes[it.i].next;
115 /// A new element with data \c t is pushed into the vector and into class
117 ClassIt push_back(const T& t, int class_id) {
121 int i=nodes.size()-1;
125 /// A member is moved to an other class.
126 void set(ClassIt it, int old_class_id, int new_class_id) {
127 kifuz(it.i, old_class_id);
128 befuz(it.i, new_class_id);
130 /// Returns the data pointed by \c it.
131 T& operator[](ClassIt it) { return nodes[it.i].data; }
132 /// Returns the data pointed by \c it.
133 const T& operator[](ClassIt it) const { return nodes[it.i].data; }
136 friend class IterablePartition;
140 /// Default constructor.
142 /// This constructor constructs an iterator which points
143 /// to the member of th container indexed by the integer _i.
144 ClassIt(const int& _i) : i(_i) { }
145 /// Invalid constructor.
146 ClassIt(const Invalid&) : i(-1) { }
147 friend bool operator<(const ClassIt& x, const ClassIt& y);
148 friend std::ostream& operator<<(std::ostream& os,
151 friend bool operator<(const ClassIt& x, const ClassIt& y) {
154 friend std::ostream& operator<<(std::ostream& os,
159 /// First member of class \c class_id.
160 ClassIt& first(ClassIt& it, int class_id) const {
161 it.i=tips[class_id].first;
165 ClassIt& next(ClassIt& it) const {
166 it.i=nodes[it.i].next;
169 /// True iff the iterator is valid.
170 bool valid(const ClassIt& it) const { return it.i!=-1; }
176 template <typename _Value>
180 typedef _Value Value;
182 typedef IterablePartition<int>::ClassIt RowIt;
184 typedef IterablePartition<int>::ClassIt ColIt;
187 IterablePartition<int> row_iter_map;
189 IterablePartition<int> col_iter_map;
191 const int VALID_CLASS;
193 const int INVALID_CLASS;
196 LPSolverBase() : row_iter_map(2),
198 VALID_CLASS(0), INVALID_CLASS(1) { }
200 virtual ~LPSolverBase() { }
202 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
206 virtual void setMinimize() = 0;
208 virtual void setMaximize() = 0;
210 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
214 virtual int _addRow() = 0;
216 virtual int _addCol() = 0;
218 virtual void _setRowCoeffs(int i,
219 std::vector<std::pair<int, double> > coeffs) = 0;
221 virtual void _setColCoeffs(int i,
222 std::vector<std::pair<int, double> > coeffs) = 0;
224 virtual void _eraseCol(int i) = 0;
226 virtual void _eraseRow(int i) = 0;
229 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
232 virtual void _setColBounds(int i, Bound bound,
233 _Value lo, _Value up) = 0;
235 virtual void _setRowBounds(int i, Bound bound,
236 _Value lo, _Value up) = 0;
238 virtual void _setObjCoef(int i, _Value obj_coef) = 0;
240 virtual _Value _getObjCoef(int i) = 0;
242 //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
245 virtual _Value _getPrimal(int i) = 0;
247 //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
254 row_iter_map.first(row_it, INVALID_CLASS);
255 if (row_iter_map.valid(row_it)) { //van hasznalhato hely
256 row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
257 row_iter_map[row_it]=i;
258 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
259 row_it=row_iter_map.push_back(i, VALID_CLASS);
267 col_iter_map.first(col_it, INVALID_CLASS);
268 if (col_iter_map.valid(col_it)) { //van hasznalhato hely
269 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
270 col_iter_map[col_it]=i;
271 } else { //a cucc vegere kell inzertalni mert nincs szabad hely
272 col_it=col_iter_map.push_back(i, VALID_CLASS);
277 template <typename Begin, typename End>
278 void setRowCoeffs(RowIt row_it, Begin begin, End end) {
279 std::vector<std::pair<int, double> > coeffs;
280 for ( ; begin!=end; ++begin) {
281 coeffs.push_back(std::
282 make_pair(col_iter_map[begin->first], begin->second));
284 _setRowCoeffs(row_iter_map[row_it], coeffs);
287 template <typename Begin, typename End>
288 void setColCoeffs(ColIt col_it, Begin begin, End end) {
289 std::vector<std::pair<int, double> > coeffs;
290 for ( ; begin!=end; ++begin) {
291 coeffs.push_back(std::
292 make_pair(row_iter_map[begin->first], begin->second));
294 _setColCoeffs(col_iter_map[col_it], coeffs);
297 void eraseCol(const ColIt& col_it) {
298 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
300 cols[1]=col_iter_map[col_it];
302 col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
304 for (col_iter_map.first(it, VALID_CLASS);
305 col_iter_map.valid(it); col_iter_map.next(it)) {
306 if (col_iter_map[it]>cols[1]) --col_iter_map[it];
310 void eraseRow(const RowIt& row_it) {
311 row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
313 rows[1]=row_iter_map[row_it];
315 row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
317 for (row_iter_map.first(it, VALID_CLASS);
318 row_iter_map.valid(it); row_iter_map.next(it)) {
319 if (row_iter_map[it]>rows[1]) --row_iter_map[it];
323 void setColBounds(const ColIt& col_it, Bound bound,
324 _Value lo, _Value up) {
325 _setColBounds(col_iter_map[col_it], bound, lo, up);
328 void setRowBounds(const RowIt& row_it, Bound bound,
329 _Value lo, _Value up) {
330 _setRowBounds(row_iter_map[row_it], bound, lo, up);
333 void setObjCoef(const ColIt& col_it, _Value obj_coef) {
334 _setObjCoef(col_iter_map[col_it], obj_coef);
337 _Value getObjCoef(const ColIt& col_it) {
338 return _getObjCoef(col_iter_map[col_it]);
341 //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
344 typedef Expr<ColIt, _Value> Expression;
346 typedef Expr<RowIt, _Value> DualExpression;
348 void setRowCoeffs(RowIt row_it, const Expression& expr) {
349 std::vector<std::pair<int, _Value> > row_coeffs;
350 for(typename Expression::Data::const_iterator i=expr.data.begin();
351 i!=expr.data.end(); ++i) {
352 row_coeffs.push_back(std::make_pair
353 (col_iter_map[(*i).first], (*i).second));
355 _setRowCoeffs(row_iter_map[row_it], row_coeffs);
358 void setColCoeffs(ColIt col_it, const DualExpression& expr) {
359 std::vector<std::pair<int, _Value> > col_coeffs;
360 for(typename DualExpression::Data::const_iterator i=expr.data.begin();
361 i!=expr.data.end(); ++i) {
362 col_coeffs.push_back(std::make_pair
363 (row_iter_map[(*i).first], (*i).second));
365 _setColCoeffs(col_iter_map[col_it], col_coeffs);
368 void setObjCoeffs(const Expression& expr) {
369 for(typename Expression::Data::const_iterator i=expr.data.begin();
370 i!=expr.data.end(); ++i) {
371 setObjCoef((*i).first, (*i).second);
377 virtual void solveSimplex() = 0;
379 virtual void solvePrimalSimplex() = 0;
381 virtual void solveDualSimplex() = 0;
384 //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
387 _Value getPrimal(const ColIt& col_it) {
388 return _getPrimal(col_iter_map[col_it]);
391 virtual _Value getObjVal() = 0;
396 virtual int rowNum() const = 0;
398 virtual int colNum() const = 0;
400 virtual int warmUp() = 0;
402 virtual void printWarmUpStatus(int i) = 0;
404 virtual int getPrimalStatus() = 0;
406 virtual void printPrimalStatus(int i) = 0;
408 virtual int getDualStatus() = 0;
410 virtual void printDualStatus(int i) = 0;
411 /// Returns the status of the slack variable assigned to row \c row_it.
412 virtual int getRowStat(const RowIt& row_it) = 0;
414 virtual void printRowStatus(int i) = 0;
415 /// Returns the status of the variable assigned to column \c col_it.
416 virtual int getColStat(const ColIt& col_it) = 0;
418 virtual void printColStatus(int i) = 0;
422 /// \brief Wrappers for LP solvers
424 /// This class implements a lemon wrapper for glpk.
425 /// Later other LP-solvers will be wrapped into lemon.
426 /// The aim of this class is to give a general surface to different
427 /// solvers, i.e. it makes possible to write algorithms using LP's,
428 /// in which the solver can be changed to an other one easily.
429 class LPGLPK : public LPSolverBase<double> {
431 typedef LPSolverBase<double> Parent;
440 lp(lpx_create_prob()) {
441 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
448 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
452 lpx_set_obj_dir(lp, LPX_MIN);
456 lpx_set_obj_dir(lp, LPX_MAX);
459 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
464 return lpx_add_cols(lp, 1);
468 return lpx_add_rows(lp, 1);
471 virtual void _setRowCoeffs(int i,
472 std::vector<std::pair<int, double> > coeffs) {
473 int mem_length=1+colNum();
474 int* indices = new int[mem_length];
475 double* doubles = new double[mem_length];
477 for (std::vector<std::pair<int, double> >::
478 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
480 indices[length]=it->first;
481 doubles[length]=it->second;
482 // std::cout << " " << indices[length] << " "
483 // << doubles[length] << std::endl;
485 // std::cout << i << " " << length << std::endl;
486 lpx_set_mat_row(lp, i, length, indices, doubles);
491 virtual void _setColCoeffs(int i,
492 std::vector<std::pair<int, double> > coeffs) {
493 int mem_length=1+rowNum();
494 int* indices = new int[mem_length];
495 double* doubles = new double[mem_length];
497 for (std::vector<std::pair<int, double> >::
498 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
500 indices[length]=it->first;
501 doubles[length]=it->second;
503 lpx_set_mat_col(lp, i, length, indices, doubles);
508 virtual void _eraseCol(int i) {
511 lpx_del_cols(lp, 1, cols);
513 virtual void _eraseRow(int i) {
516 lpx_del_rows(lp, 1, rows);
518 virtual void _setColBounds(int i, Bound bound,
519 double lo, double up) {
522 lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
525 lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
528 lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
531 lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
534 lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
538 virtual void _setRowBounds(int i, Bound bound,
539 double lo, double up) {
542 lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
545 lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
548 lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
551 lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
554 lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
560 virtual double _getObjCoef(int i) {
561 return lpx_get_obj_coef(lp, i);
564 virtual void _setObjCoef(int i, double obj_coef) {
565 lpx_set_obj_coef(lp, i, obj_coef);
569 void solveSimplex() { lpx_simplex(lp); }
571 void solvePrimalSimplex() { lpx_simplex(lp); }
573 void solveDualSimplex() { lpx_simplex(lp); }
576 virtual double _getPrimal(int i) {
577 return lpx_get_col_prim(lp, i);
581 double getObjVal() { return lpx_get_obj_val(lp); }
583 int rowNum() const { return lpx_get_num_rows(lp); }
585 int colNum() const { return lpx_get_num_cols(lp); }
587 int warmUp() { return lpx_warm_up(lp); }
589 void printWarmUpStatus(int i) {
591 case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
592 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
593 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
594 case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
598 int getPrimalStatus() { return lpx_get_prim_stat(lp); }
600 void printPrimalStatus(int i) {
602 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
603 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
604 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
605 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
609 int getDualStatus() { return lpx_get_dual_stat(lp); }
611 void printDualStatus(int i) {
613 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
614 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
615 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
616 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
619 /// Returns the status of the slack variable assigned to row \c row_it.
620 int getRowStat(const RowIt& row_it) {
621 return lpx_get_row_stat(lp, row_iter_map[row_it]);
624 void printRowStatus(int i) {
626 case LPX_BS: cout << "LPX_BS" << endl; break;
627 case LPX_NL: cout << "LPX_NL" << endl; break;
628 case LPX_NU: cout << "LPX_NU" << endl; break;
629 case LPX_NF: cout << "LPX_NF" << endl; break;
630 case LPX_NS: cout << "LPX_NS" << endl; break;
633 /// Returns the status of the variable assigned to column \c col_it.
634 int getColStat(const ColIt& col_it) {
635 return lpx_get_col_stat(lp, col_iter_map[col_it]);
638 void printColStatus(int i) {
640 case LPX_BS: cout << "LPX_BS" << endl; break;
641 case LPX_NL: cout << "LPX_NL" << endl; break;
642 case LPX_NU: cout << "LPX_NU" << endl; break;
643 case LPX_NF: cout << "LPX_NF" << endl; break;
644 case LPX_NS: cout << "LPX_NS" << endl; break;
653 #endif //LEMON_LP_SOLVER_WRAPPER_H