athos@1260: // -*- c++ -*- athos@1260: #ifndef LEMON_LP_SOLVER_GLPK_H athos@1260: #define LEMON_LP_SOLVER_GLPK_H athos@1260: athos@1260: ///\ingroup misc athos@1260: ///\file athos@1260: athos@1260: extern "C" { athos@1260: #include "glpk.h" athos@1260: } athos@1260: #include athos@1260: athos@1260: namespace lemon { athos@1260: athos@1260: athos@1260: template athos@1260: const Value LpSolverBase::INF=std::numeric_limits::infinity(); athos@1260: athos@1260: athos@1260: /// \brief Wrapper for GLPK solver athos@1260: /// athos@1260: /// This class implements a lemon wrapper for GLPK. athos@1260: class LpGlpk : public LpSolverBase { athos@1260: athos@1260: public: athos@1260: athos@1260: typedef LpSolverBase Parent; athos@1260: athos@1260: /// \e athos@1260: LPX* lp; athos@1260: athos@1260: /// \e athos@1260: LpGlpk() : Parent(), athos@1260: lp(lpx_create_prob()) { athos@1260: //int_row_map.push_back(Row()); athos@1260: //int_col_map.push_back(Col()); athos@1260: lpx_set_int_parm(lp, LPX_K_DUAL, 1); athos@1260: } athos@1260: /// \e athos@1260: ~LpGlpk() { athos@1260: lpx_delete_prob(lp); athos@1260: } athos@1260: athos@1260: //MATRIX INDEPEDENT MANIPULATING FUNCTIONS athos@1260: athos@1260: /// \e athos@1260: void setMinimize() { athos@1260: lpx_set_obj_dir(lp, LPX_MIN); athos@1260: } athos@1260: /// \e athos@1260: void setMaximize() { athos@1260: lpx_set_obj_dir(lp, LPX_MAX); athos@1260: } athos@1260: athos@1260: /// \e athos@1260: /// Retrieve number of rows athos@1260: int rowNum() const { return lpx_get_num_rows(lp); } athos@1260: /// \e athos@1260: /// Retrieve number of coloumns athos@1260: int colNum() const { return lpx_get_num_cols(lp); } athos@1260: athos@1260: protected: athos@1260: /// \e athos@1260: int LpGlpk::_addCol() { athos@1260: int i=lpx_add_cols(lp, 1); athos@1260: _setColLowerBound(i, -INF); athos@1260: _setColUpperBound(i, INF); athos@1260: return i; athos@1260: } athos@1260: /// \e athos@1260: int LpGlpk::_addRow() { athos@1260: int i=lpx_add_rows(lp, 1); athos@1260: return i; athos@1260: } athos@1260: /// \e athos@1260: virtual void _setRowCoeffs(int i, athos@1260: const std::vector >& coeffs) { athos@1260: int mem_length=1+colNum(); athos@1260: int* indices = new int[mem_length]; athos@1260: double* doubles = new double[mem_length]; athos@1260: int length=0; athos@1260: for (std::vector >:: athos@1260: const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { athos@1260: ++length; athos@1260: indices[length]=it->first; athos@1260: doubles[length]=it->second; athos@1260: } athos@1260: lpx_set_mat_row(lp, i, length, indices, doubles); athos@1260: delete [] indices; athos@1260: delete [] doubles; athos@1260: } athos@1260: /// \e athos@1260: virtual void _getRowCoeffs(int i, athos@1260: std::vector >& coeffs) { athos@1260: int mem_length=1+colNum(); athos@1260: int* indices = new int[mem_length]; athos@1260: double* doubles = new double[mem_length]; athos@1260: int length=lpx_get_mat_row(lp, i, indices, doubles); athos@1260: for (int i=1; i<=length; ++i) { athos@1260: coeffs.push_back(std::make_pair(indices[i], doubles[i])); athos@1260: } athos@1260: delete [] indices; athos@1260: delete [] doubles; athos@1260: } athos@1260: /// \e athos@1260: virtual void _setColCoeffs(int i, athos@1260: const std::vector >& coeffs) { athos@1260: int mem_length=1+rowNum(); athos@1260: int* indices = new int[mem_length]; athos@1260: double* doubles = new double[mem_length]; athos@1260: int length=0; athos@1260: for (std::vector >:: athos@1260: const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { athos@1260: ++length; athos@1260: indices[length]=it->first; athos@1260: doubles[length]=it->second; athos@1260: } athos@1260: lpx_set_mat_col(lp, i, length, indices, doubles); athos@1260: delete [] indices; athos@1260: delete [] doubles; athos@1260: } athos@1260: /// \e athos@1260: virtual void _getColCoeffs(int i, athos@1260: std::vector >& coeffs) { athos@1260: int mem_length=1+rowNum(); athos@1260: int* indices = new int[mem_length]; athos@1260: double* doubles = new double[mem_length]; athos@1260: int length=lpx_get_mat_col(lp, i, indices, doubles); athos@1260: for (int i=1; i<=length; ++i) { athos@1260: coeffs.push_back(std::make_pair(indices[i], doubles[i])); athos@1260: } athos@1260: delete [] indices; athos@1260: delete [] doubles; athos@1260: } athos@1260: /// \e athos@1260: virtual void _eraseCol(int i) { athos@1260: int cols[2]; athos@1260: cols[1]=i; athos@1260: lpx_del_cols(lp, 1, cols); athos@1260: } athos@1260: virtual void _eraseRow(int i) { athos@1260: int rows[2]; athos@1260: rows[1]=i; athos@1260: lpx_del_rows(lp, 1, rows); athos@1260: } athos@1260: athos@1260: void _setCoeff(int row, int col, double value) { athos@1260: ///FIXME Of course this is not efficient at all, but GLPK knows not more. athos@1260: /// First approach: get one row, apply changes and set it again athos@1260: athos@1260: int mem_length=1+colNum(); athos@1260: int* indices = new int[mem_length]; athos@1260: double* doubles = new double[mem_length]; athos@1260: athos@1260: athos@1260: int length=lpx_get_mat_row(lp, i, indices, doubles); athos@1260: athos@1260: //The following code does not suppose that the elements of the array indices are sorted athos@1260: int i=1; athos@1260: bool found=false; athos@1260: while (i <= length && !found){ athos@1260: if (indices[i]=col){ athos@1260: found = true; athos@1260: doubles[i]=value; athos@1260: } athos@1260: ++i; athos@1260: } athos@1260: if (!found){ athos@1260: ++length; athos@1260: indices[length]=col; athos@1260: doubles[length]=value; athos@1260: } athos@1260: athos@1260: // This is a piece of code that assumes that the array 'indices' is sorted. athos@1260: // Not ready, I suppose. athos@1260: // //We need another arrays to put the data back, anyway athos@1260: // int* new_indices = new int[length+1]; athos@1260: // double* new_doubles = new double[length+1]; athos@1260: // int offset; athos@1260: athos@1260: // int i=1; athos@1260: // while (i <= length && indices[i]length || indices[i]>col){ athos@1260: // //Ha atugrottuk, vagy a vegen van athos@1260: // new_indices[i]=col; athos@1260: // new_doubles[i]=value; athos@1260: // offset = 1; athos@1260: // } athos@1260: // else{ athos@1260: // //I.e.: indices[i]=col athos@1260: // new_doubles[i]=value; athos@1260: // offset = 0; athos@1260: // ++i; athos@1260: // } athos@1260: // while (i <= length){ athos@1260: // new_indices[i+offset]=indices[i]; athos@1260: // new_values[i+offset]=values[i]; athos@1260: // } athos@1260: athos@1260: lpx_set_mat_row(lp, row, length, indices, doubles); athos@1260: delete [] indices; athos@1260: delete [] doubles; athos@1260: athos@1260: // lpx_set_mat_row(lp, row, length+offset, new_indices, new_doubles); athos@1260: // delete [] new_indices; athos@1260: // delete [] new_doubles; athos@1260: athos@1260: athos@1260: } athos@1260: double _getCoeff(int col, int row) { athos@1260: /// FIXME not yet implemented athos@1260: return 0.0; athos@1260: } athos@1260: virtual void _setColLowerBound(int i, double lo) { athos@1260: if (lo==INF) { athos@1260: //FIXME error athos@1260: } athos@1260: int b=lpx_get_col_type(lp, i); athos@1260: double up=lpx_get_col_ub(lp, i); athos@1260: if (lo==-INF) { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } else { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: if (lo==up) athos@1260: lpx_set_col_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_col_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } athos@1260: } athos@1260: virtual double _getColLowerBound(int i) { athos@1260: int b=lpx_get_col_type(lp, i); athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: return -INF; athos@1260: case LPX_LO: athos@1260: return lpx_get_col_lb(lp, i); athos@1260: case LPX_UP: athos@1260: return -INF; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: return lpx_get_col_lb(lp, i); athos@1260: default: ; athos@1260: //FIXME error athos@1260: return 0.0; athos@1260: } athos@1260: } athos@1260: virtual void _setColUpperBound(int i, double up) { athos@1260: if (up==-INF) { athos@1260: //FIXME error athos@1260: } athos@1260: int b=lpx_get_col_type(lp, i); athos@1260: double lo=lpx_get_col_lb(lp, i); athos@1260: if (up==INF) { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: break; athos@1260: case LPX_UP: athos@1260: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } else { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); athos@1260: case LPX_LO: athos@1260: if (lo==up) athos@1260: lpx_set_col_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_col_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: if (lo==up) athos@1260: lpx_set_col_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_col_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } athos@1260: } athos@1260: virtual double _getColUpperBound(int i) { athos@1260: int b=lpx_get_col_type(lp, i); athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: return INF; athos@1260: case LPX_UP: athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: return lpx_get_col_ub(lp, i); athos@1260: default: ; athos@1260: //FIXME error athos@1260: return 0.0; athos@1260: } athos@1260: } athos@1260: virtual void _setRowLowerBound(int i, double lo) { athos@1260: if (lo==INF) { athos@1260: //FIXME error athos@1260: } athos@1260: int b=lpx_get_row_type(lp, i); athos@1260: double up=lpx_get_row_ub(lp, i); athos@1260: if (lo==-INF) { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: lpx_set_row_bnds(lp, i, LPX_FR, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } else { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: lpx_set_row_bnds(lp, i, LPX_LO, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: if (lo==up) athos@1260: lpx_set_row_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_row_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } athos@1260: } athos@1260: virtual double _getRowLowerBound(int i) { athos@1260: int b=lpx_get_row_type(lp, i); athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: return -INF; athos@1260: case LPX_LO: athos@1260: return lpx_get_row_lb(lp, i); athos@1260: case LPX_UP: athos@1260: return -INF; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: return lpx_get_row_lb(lp, i); athos@1260: default: ; athos@1260: //FIXME error athos@1260: return 0.0; athos@1260: } athos@1260: } athos@1260: virtual void _setRowUpperBound(int i, double up) { athos@1260: if (up==-INF) { athos@1260: //FIXME error athos@1260: } athos@1260: int b=lpx_get_row_type(lp, i); athos@1260: double lo=lpx_get_row_lb(lp, i); athos@1260: if (up==INF) { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: break; athos@1260: case LPX_UP: athos@1260: lpx_set_row_bnds(lp, i, LPX_FR, lo, up); athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: lpx_set_row_bnds(lp, i, LPX_LO, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } else { athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1260: case LPX_LO: athos@1260: if (lo==up) athos@1260: lpx_set_row_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_row_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: case LPX_UP: athos@1260: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1260: break; athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: if (lo==up) athos@1260: lpx_set_row_bnds(lp, i, LPX_FX, lo, up); athos@1260: else athos@1260: lpx_set_row_bnds(lp, i, LPX_DB, lo, up); athos@1260: break; athos@1260: default: ; athos@1260: //FIXME error athos@1260: } athos@1260: } athos@1260: } athos@1260: virtual double _getRowUpperBound(int i) { athos@1260: int b=lpx_get_row_type(lp, i); athos@1260: switch (b) { athos@1260: case LPX_FR: athos@1260: case LPX_LO: athos@1260: return INF; athos@1260: case LPX_UP: athos@1260: case LPX_DB: athos@1260: case LPX_FX: athos@1260: return lpx_get_row_ub(lp, i); athos@1260: default: ; athos@1260: //FIXME error athos@1260: return 0.0; athos@1260: } athos@1260: } athos@1260: /// \e athos@1260: virtual double _getObjCoeff(int i) { athos@1260: return lpx_get_obj_coef(lp, i); athos@1260: } athos@1260: /// \e athos@1260: virtual void _setObjCoeff(int i, double obj_coef) { athos@1260: lpx_set_obj_coef(lp, i, obj_coef); athos@1260: } athos@1260: athos@1260: protected: athos@1260: virtual double _getPrimal(int i) { athos@1260: return lpx_get_col_prim(lp, i); athos@1260: } athos@1260: athos@1260: //MIP athos@1260: protected: athos@1260: /// \e athos@1260: void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); } athos@1260: /// \e athos@1260: void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); } athos@1260: /// \e athos@1260: double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); } athos@1260: athos@1260: athos@1260: // public: athos@1260: // /// \e athos@1260: // void solveSimplex() { lpx_simplex(lp); } athos@1260: // /// \e athos@1260: // void solvePrimalSimplex() { lpx_simplex(lp); } athos@1260: // /// \e athos@1260: // void solveDualSimplex() { lpx_simplex(lp); } athos@1260: // /// \e athos@1260: // double getObjVal() { return lpx_get_obj_val(lp); } athos@1260: // /// \e athos@1260: // int warmUp() { return lpx_warm_up(lp); } athos@1260: // /// \e athos@1260: // void printWarmUpStatus(int i) { athos@1260: // switch (i) { athos@1260: // case LPX_E_OK: cout << "LPX_E_OK" << endl; break; athos@1260: // case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; athos@1260: // case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; athos@1260: // case LPX_E_SING: cout << "LPX_E_SING" << endl; break; athos@1260: // } athos@1260: // } athos@1260: // /// \e athos@1260: // int getPrimalStatus() { return lpx_get_prim_stat(lp); } athos@1260: // /// \e athos@1260: // void printPrimalStatus(int i) { athos@1260: // switch (i) { athos@1260: // case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; athos@1260: // case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; athos@1260: // case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; athos@1260: // case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; athos@1260: // } athos@1260: // } athos@1260: // /// \e athos@1260: // int getDualStatus() { return lpx_get_dual_stat(lp); } athos@1260: // /// \e athos@1260: // void printDualStatus(int i) { athos@1260: // switch (i) { athos@1260: // case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; athos@1260: // case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; athos@1260: // case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; athos@1260: // case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; athos@1260: // } athos@1260: // } athos@1260: // /// Returns the status of the slack variable assigned to row \c row. athos@1260: // int getRowStat(const Row& row) { athos@1260: // return lpx_get_row_stat(lp, row_iter_map[row]); athos@1260: // } athos@1260: // /// \e athos@1260: // void printRowStatus(int i) { athos@1260: // switch (i) { athos@1260: // case LPX_BS: cout << "LPX_BS" << endl; break; athos@1260: // case LPX_NL: cout << "LPX_NL" << endl; break; athos@1260: // case LPX_NU: cout << "LPX_NU" << endl; break; athos@1260: // case LPX_NF: cout << "LPX_NF" << endl; break; athos@1260: // case LPX_NS: cout << "LPX_NS" << endl; break; athos@1260: // } athos@1260: // } athos@1260: // /// Returns the status of the variable assigned to column \c col. athos@1260: // int getColStat(const Col& col) { athos@1260: // return lpx_get_col_stat(lp, col_iter_map[col]); athos@1260: // } athos@1260: // /// \e athos@1260: // void printColStatus(int i) { athos@1260: // switch (i) { athos@1260: // case LPX_BS: cout << "LPX_BS" << endl; break; athos@1260: // case LPX_NL: cout << "LPX_NL" << endl; break; athos@1260: // case LPX_NU: cout << "LPX_NU" << endl; break; athos@1260: // case LPX_NF: cout << "LPX_NF" << endl; break; athos@1260: // case LPX_NS: cout << "LPX_NS" << endl; break; athos@1260: // } athos@1260: // } athos@1260: athos@1260: // // MIP athos@1260: // /// \e athos@1260: // void solveBandB() { lpx_integer(lp); } athos@1260: // /// \e athos@1260: // void setLP() { lpx_set_class(lp, LPX_LP); } athos@1260: // /// \e athos@1260: // void setMIP() { lpx_set_class(lp, LPX_MIP); } athos@1260: athos@1260: athos@1260: athos@1260: }; athos@1260: athos@1260: /// @} athos@1260: athos@1260: } //namespace lemon athos@1260: athos@1260: #endif //LEMON_LP_SOLVER_GLPK_H