marci@764: // -*- c++ -*- alpar@921: #ifndef LEMON_LP_SOLVER_WRAPPER_H marci@1015: #define LEMON_LP_SOLVER_WRAPPER_H marci@764: alpar@765: ///\ingroup misc alpar@765: ///\file alpar@765: ///\brief Dijkstra algorithm. alpar@765: marci@764: // #include <stdio.h> marci@764: #include <stdlib.h> marci@764: // #include <stdio> marci@764: //#include <stdlib> marci@1014: extern "C" { marci@764: #include "glpk.h" marci@1014: } marci@764: marci@764: #include <iostream> marci@764: #include <vector> marci@764: #include <string> marci@764: #include <list> marci@764: #include <memory> marci@764: #include <utility> marci@764: marci@764: //#include <sage_graph.h> alpar@921: //#include <lemon/list_graph.h> alpar@921: //#include <lemon/graph_wrapper.h> alpar@921: #include <lemon/invalid.h> marci@764: //#include <bfs_dfs.h> marci@764: //#include <stp.h> alpar@921: //#include <lemon/max_flow.h> marci@764: //#include <augmenting_flow.h> marci@764: //#include <iter_map.h> marci@764: marci@764: using std::cout; marci@764: using std::cin; marci@764: using std::endl; marci@764: alpar@921: namespace lemon { marci@764: alpar@765: alpar@765: /// \addtogroup misc alpar@765: /// @{ alpar@765: marci@764: /// \brief A partitioned vector with iterable classes. marci@764: /// marci@764: /// This class implements a container in which the data is stored in an marci@764: /// stl vector, the range is partitioned into sets and each set is marci@764: /// doubly linked in a list. alpar@921: /// That is, each class is iterable by lemon iterators, and any member of marci@764: /// the vector can bo moved to an other class. marci@764: template <typename T> marci@764: class IterablePartition { marci@764: protected: marci@764: struct Node { marci@764: T data; marci@764: int prev; //invalid az -1 marci@764: int next; marci@764: }; marci@764: std::vector<Node> nodes; marci@764: struct Tip { marci@764: int first; marci@764: int last; marci@764: }; marci@764: std::vector<Tip> tips; marci@764: public: marci@764: /// The classes are indexed by integers from \c 0 to \c classNum()-1. marci@764: int classNum() const { return tips.size(); } alpar@921: /// This lemon style iterator iterates through a class. marci@764: class ClassIt; marci@764: /// Constructor. The number of classes is to be given which is fixed marci@764: /// over the life of the container. marci@764: /// The partition classes are indexed from 0 to class_num-1. marci@764: IterablePartition(int class_num) { marci@764: for (int i=0; i<class_num; ++i) { marci@764: Tip t; marci@764: t.first=t.last=-1; marci@764: tips.push_back(t); marci@764: } marci@764: } marci@764: protected: marci@764: void befuz(ClassIt it, int class_id) { marci@764: if (tips[class_id].first==-1) { marci@764: if (tips[class_id].last==-1) { marci@764: nodes[it.i].prev=nodes[it.i].next=-1; marci@764: tips[class_id].first=tips[class_id].last=it.i; marci@764: } marci@764: } else { marci@764: nodes[it.i].prev=tips[class_id].last; marci@764: nodes[it.i].next=-1; marci@764: nodes[tips[class_id].last].next=it.i; marci@764: tips[class_id].last=it.i; marci@764: } marci@764: } marci@764: void kifuz(ClassIt it, int class_id) { marci@764: if (tips[class_id].first==it.i) { marci@764: if (tips[class_id].last==it.i) { marci@764: tips[class_id].first=tips[class_id].last=-1; marci@764: } else { marci@764: tips[class_id].first=nodes[it.i].next; marci@764: nodes[nodes[it.i].next].prev=-1; marci@764: } marci@764: } else { marci@764: if (tips[class_id].last==it.i) { marci@764: tips[class_id].last=nodes[it.i].prev; marci@764: nodes[nodes[it.i].prev].next=-1; marci@764: } else { marci@764: nodes[nodes[it.i].next].prev=nodes[it.i].prev; marci@764: nodes[nodes[it.i].prev].next=nodes[it.i].next; marci@764: } marci@764: } marci@764: } marci@764: public: marci@764: /// A new element with data \c t is pushed into the vector and into class marci@764: /// \c class_id. marci@764: ClassIt push_back(const T& t, int class_id) { marci@764: Node n; marci@764: n.data=t; marci@764: nodes.push_back(n); marci@764: int i=nodes.size()-1; marci@764: befuz(i, class_id); marci@764: return i; marci@764: } marci@764: /// A member is moved to an other class. marci@764: void set(ClassIt it, int old_class_id, int new_class_id) { marci@764: kifuz(it.i, old_class_id); marci@764: befuz(it.i, new_class_id); marci@764: } marci@764: /// Returns the data pointed by \c it. marci@764: T& operator[](ClassIt it) { return nodes[it.i].data; } marci@764: /// Returns the data pointed by \c it. marci@764: const T& operator[](ClassIt it) const { return nodes[it.i].data; } alpar@765: ///. marci@764: class ClassIt { marci@764: friend class IterablePartition; marci@764: protected: marci@764: int i; marci@764: public: marci@764: /// Default constructor. marci@764: ClassIt() { } marci@764: /// This constructor constructs an iterator which points marci@764: /// to the member of th container indexed by the integer _i. marci@764: ClassIt(const int& _i) : i(_i) { } marci@764: /// Invalid constructor. marci@764: ClassIt(const Invalid&) : i(-1) { } marci@764: }; marci@764: /// First member of class \c class_id. marci@764: ClassIt& first(ClassIt& it, int class_id) const { marci@764: it.i=tips[class_id].first; marci@764: return it; marci@764: } marci@764: /// Next member. marci@764: ClassIt& next(ClassIt& it) const { marci@764: it.i=nodes[it.i].next; marci@764: return it; marci@764: } marci@764: /// True iff the iterator is valid. marci@764: bool valid(const ClassIt& it) const { return it.i!=-1; } marci@764: }; marci@764: marci@764: /// \brief Wrappers for LP solvers marci@764: /// alpar@921: /// This class implements a lemon wrapper for glpk. alpar@921: /// Later other LP-solvers will be wrapped into lemon. marci@764: /// The aim of this class is to give a general surface to different marci@764: /// solvers, i.e. it makes possible to write algorithms using LP's, marci@764: /// in which the solver can be changed to an other one easily. marci@764: class LPSolverWrapper { marci@764: public: marci@764: marci@764: // class Row { marci@764: // protected: marci@764: // int i; marci@764: // public: marci@764: // Row() { } marci@764: // Row(const Invalid&) : i(0) { } marci@764: // Row(const int& _i) : i(_i) { } marci@764: // operator int() const { return i; } marci@764: // }; marci@764: // class RowIt : public Row { marci@764: // public: marci@764: // RowIt(const Row& row) : Row(row) { } marci@764: // }; marci@764: marci@764: // class Col { marci@764: // protected: marci@764: // int i; marci@764: // public: marci@764: // Col() { } marci@764: // Col(const Invalid&) : i(0) { } marci@764: // Col(const int& _i) : i(_i) { } marci@764: // operator int() const { return i; } marci@764: // }; marci@764: // class ColIt : public Col { marci@764: // ColIt(const Col& col) : Col(col) { } marci@764: // }; marci@764: marci@764: public: alpar@765: ///. marci@764: LPX* lp; alpar@765: ///. marci@764: typedef IterablePartition<int>::ClassIt RowIt; alpar@765: ///. marci@764: IterablePartition<int> row_iter_map; alpar@765: ///. marci@764: typedef IterablePartition<int>::ClassIt ColIt; alpar@765: ///. marci@764: IterablePartition<int> col_iter_map; marci@764: //std::vector<int> row_id_to_lp_row_id; marci@764: //std::vector<int> col_id_to_lp_col_id; alpar@765: ///. marci@764: const int VALID_ID; alpar@765: ///. marci@764: const int INVALID_ID; marci@764: marci@764: public: alpar@765: ///. marci@764: LPSolverWrapper() : lp(lpx_create_prob()), marci@764: row_iter_map(2), marci@764: col_iter_map(2), marci@764: //row_id_to_lp_row_id(), col_id_to_lp_col_id(), marci@764: VALID_ID(0), INVALID_ID(1) { marci@764: lpx_set_int_parm(lp, LPX_K_DUAL, 1); marci@764: } alpar@765: ///. marci@764: ~LPSolverWrapper() { marci@764: lpx_delete_prob(lp); marci@764: } alpar@765: ///. marci@764: void setMinimize() { marci@764: lpx_set_obj_dir(lp, LPX_MIN); marci@764: } alpar@765: ///. marci@764: void setMaximize() { marci@764: lpx_set_obj_dir(lp, LPX_MAX); marci@764: } alpar@765: ///. marci@764: ColIt addCol() { marci@764: int i=lpx_add_cols(lp, 1); marci@764: ColIt col_it; marci@764: col_iter_map.first(col_it, INVALID_ID); marci@764: if (col_iter_map.valid(col_it)) { //van hasznalhato hely marci@764: col_iter_map.set(col_it, INVALID_ID, VALID_ID); marci@764: col_iter_map[col_it]=i; marci@764: //col_id_to_lp_col_id[col_iter_map[col_it]]=i; marci@764: } else { //a cucc vegere kell inzertalni mert nincs szabad hely marci@764: //col_id_to_lp_col_id.push_back(i); marci@764: //int j=col_id_to_lp_col_id.size()-1; marci@764: col_it=col_iter_map.push_back(i, VALID_ID); marci@764: } marci@764: // edge_index_map.set(e, i); marci@764: // lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0); marci@764: // lpx_set_obj_coef(lp, i, cost[e]); marci@764: return col_it; marci@764: } alpar@765: ///. marci@764: RowIt addRow() { marci@764: int i=lpx_add_rows(lp, 1); marci@764: RowIt row_it; marci@764: row_iter_map.first(row_it, INVALID_ID); marci@764: if (row_iter_map.valid(row_it)) { //van hasznalhato hely marci@764: row_iter_map.set(row_it, INVALID_ID, VALID_ID); marci@764: row_iter_map[row_it]=i; marci@764: } else { //a cucc vegere kell inzertalni mert nincs szabad hely marci@764: row_it=row_iter_map.push_back(i, VALID_ID); marci@764: } marci@764: return row_it; marci@764: } marci@764: //pair<RowIt, double>-bol kell megadni egy std range-et alpar@765: ///. marci@764: template <typename Begin, typename End> marci@764: void setColCoeffs(const ColIt& col_it, marci@764: Begin begin, End end) { marci@764: int mem_length=1+lpx_get_num_rows(lp); marci@764: int* indices = new int[mem_length]; marci@764: double* doubles = new double[mem_length]; marci@764: int length=0; marci@764: for ( ; begin!=end; ++begin) { marci@764: ++length; marci@764: indices[length]=row_iter_map[begin->first]; marci@764: doubles[length]=begin->second; marci@764: } marci@764: lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles); marci@764: delete [] indices; marci@764: delete [] doubles; marci@764: } marci@764: //pair<ColIt, double>-bol kell megadni egy std range-et alpar@765: ///. marci@764: template <typename Begin, typename End> marci@764: void setRowCoeffs(const RowIt& row_it, marci@764: Begin begin, End end) { marci@764: int mem_length=1+lpx_get_num_cols(lp); marci@764: int* indices = new int[mem_length]; marci@764: double* doubles = new double[mem_length]; marci@764: int length=0; marci@764: for ( ; begin!=end; ++begin) { marci@764: ++length; marci@764: indices[length]=col_iter_map[begin->first]; marci@764: doubles[length]=begin->second; marci@764: } marci@764: lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles); marci@764: delete [] indices; marci@764: delete [] doubles; marci@764: } alpar@765: ///. marci@764: void eraseCol(const ColIt& col_it) { marci@764: col_iter_map.set(col_it, VALID_ID, INVALID_ID); marci@764: int cols[2]; marci@764: cols[1]=col_iter_map[col_it]; marci@764: lpx_del_cols(lp, 1, cols); marci@764: col_iter_map[col_it]=0; //glpk specifikus marci@764: ColIt it; marci@764: for (col_iter_map.first(it, VALID_ID); marci@764: col_iter_map.valid(it); col_iter_map.next(it)) { marci@764: if (col_iter_map[it]>cols[1]) --col_iter_map[it]; marci@764: } marci@764: } alpar@765: ///. marci@764: void eraseRow(const RowIt& row_it) { marci@764: row_iter_map.set(row_it, VALID_ID, INVALID_ID); marci@764: int rows[2]; marci@764: rows[1]=row_iter_map[row_it]; marci@764: lpx_del_rows(lp, 1, rows); marci@764: row_iter_map[row_it]=0; //glpk specifikus marci@764: RowIt it; marci@764: for (row_iter_map.first(it, VALID_ID); marci@764: row_iter_map.valid(it); row_iter_map.next(it)) { marci@764: if (row_iter_map[it]>rows[1]) --row_iter_map[it]; marci@764: } marci@764: } alpar@765: ///. marci@764: void setColBounds(const ColIt& col_it, int bound_type, marci@764: double lo, double up) { marci@764: lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up); marci@764: } alpar@765: ///. marci@768: double getObjCoef(const ColIt& col_it) { marci@768: return lpx_get_obj_coef(lp, col_iter_map[col_it]); marci@764: } alpar@765: ///. marci@764: void setRowBounds(const RowIt& row_it, int bound_type, marci@764: double lo, double up) { marci@764: lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up); marci@764: } marci@888: ///. marci@888: void setObjCoef(const ColIt& col_it, double obj_coef) { marci@888: lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef); marci@888: } alpar@765: ///. marci@764: void solveSimplex() { lpx_simplex(lp); } alpar@765: ///. marci@764: void solvePrimalSimplex() { lpx_simplex(lp); } alpar@765: ///. marci@764: void solveDualSimplex() { lpx_simplex(lp); } alpar@765: ///. marci@764: double getPrimal(const ColIt& col_it) { marci@764: return lpx_get_col_prim(lp, col_iter_map[col_it]); marci@764: } alpar@765: ///. marci@764: double getObjVal() { return lpx_get_obj_val(lp); } alpar@765: ///. marci@764: int rowNum() const { return lpx_get_num_rows(lp); } alpar@765: ///. marci@764: int colNum() const { return lpx_get_num_cols(lp); } alpar@765: ///. marci@764: int warmUp() { return lpx_warm_up(lp); } alpar@765: ///. marci@764: void printWarmUpStatus(int i) { marci@764: switch (i) { marci@764: case LPX_E_OK: cout << "LPX_E_OK" << endl; break; marci@764: case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; marci@764: case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; marci@764: case LPX_E_SING: cout << "LPX_E_SING" << endl; break; marci@764: } marci@764: } alpar@765: ///. marci@764: int getPrimalStatus() { return lpx_get_prim_stat(lp); } alpar@765: ///. marci@764: void printPrimalStatus(int i) { marci@764: switch (i) { marci@764: case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; marci@764: case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; marci@764: case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; marci@764: case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; marci@764: } marci@764: } alpar@765: ///. marci@764: int getDualStatus() { return lpx_get_dual_stat(lp); } alpar@765: ///. marci@764: void printDualStatus(int i) { marci@764: switch (i) { marci@764: case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; marci@764: case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; marci@764: case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; marci@764: case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; marci@764: } marci@764: } marci@764: /// Returns the status of the slack variable assigned to row \c row_it. marci@764: int getRowStat(const RowIt& row_it) { marci@764: return lpx_get_row_stat(lp, row_iter_map[row_it]); marci@764: } alpar@765: ///. marci@764: void printRowStatus(int i) { marci@764: switch (i) { marci@764: case LPX_BS: cout << "LPX_BS" << endl; break; marci@764: case LPX_NL: cout << "LPX_NL" << endl; break; marci@764: case LPX_NU: cout << "LPX_NU" << endl; break; marci@764: case LPX_NF: cout << "LPX_NF" << endl; break; marci@764: case LPX_NS: cout << "LPX_NS" << endl; break; marci@764: } marci@764: } marci@764: /// Returns the status of the variable assigned to column \c col_it. marci@764: int getColStat(const ColIt& col_it) { marci@764: return lpx_get_col_stat(lp, col_iter_map[col_it]); marci@764: } alpar@765: ///. marci@764: void printColStatus(int i) { marci@764: switch (i) { marci@764: case LPX_BS: cout << "LPX_BS" << endl; break; marci@764: case LPX_NL: cout << "LPX_NL" << endl; break; marci@764: case LPX_NU: cout << "LPX_NU" << endl; break; marci@764: case LPX_NF: cout << "LPX_NF" << endl; break; marci@764: case LPX_NS: cout << "LPX_NS" << endl; break; marci@764: } marci@764: } marci@764: }; alpar@765: alpar@765: /// @} marci@764: alpar@921: } //namespace lemon marci@764: alpar@921: #endif //LEMON_LP_SOLVER_WRAPPER_H