marci@764: // -*- c++ -*- alpar@921: #ifndef LEMON_LP_SOLVER_WRAPPER_H alpar@921: #define LEMON_LP_SOLVER_WRAPPER marci@764: alpar@765: ///\ingroup misc alpar@765: ///\file alpar@765: ///\brief Dijkstra algorithm. alpar@765: marci@764: // #include marci@764: #include marci@764: // #include marci@764: //#include marci@764: #include "glpk.h" marci@764: marci@764: #include marci@764: #include marci@764: #include marci@764: #include marci@764: #include marci@764: #include marci@764: marci@764: //#include alpar@921: //#include alpar@921: //#include alpar@921: #include marci@764: //#include marci@764: //#include alpar@921: //#include marci@764: //#include marci@764: //#include 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 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 nodes; marci@764: struct Tip { marci@764: int first; marci@764: int last; marci@764: }; marci@764: std::vector 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::ClassIt RowIt; alpar@765: ///. marci@764: IterablePartition row_iter_map; alpar@765: ///. marci@764: typedef IterablePartition::ClassIt ColIt; alpar@765: ///. marci@764: IterablePartition col_iter_map; marci@764: //std::vector row_id_to_lp_row_id; marci@764: //std::vector 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-bol kell megadni egy std range-et alpar@765: ///. marci@764: template 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-bol kell megadni egy std range-et alpar@765: ///. marci@764: template 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