Ignore:
Timestamp:
03/22/05 13:02:29 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1668
Message:

Modified a bit.

Location:
src/work/athos/lp
Files:
4 edited

Unmodified
Removed
• ## src/work/athos/lp/lp_solver_base.h

 r1240 // #include //#include extern "C" { #include "glpk.h" } #include */ template class LPSolverBase { class LpSolverBase { /*! @name Uncategorized functions and types (public members) const int INVALID_CLASS; /// \e static const _Value INF; public: /// \e LPSolverBase() : row_iter_map(2), static const Value INF; public: /// \e LpSolverBase() : row_iter_map(2), col_iter_map(2), VALID_CLASS(0), INVALID_CLASS(1) { } /// \e virtual ~LPSolverBase() { } virtual ~LpSolverBase() { } //@} /// \e virtual _Value getObjVal() = 0; virtual Value getObjVal() = 0; //OTHER FUNCTIONS /// \e virtual void _setRowCoeffs(int i, const std::vector >& coeffs) = 0; const std::vector >& coeffs) = 0; /// \e /// This routine modifies \c coeffs only by the \c push_back method. virtual void _getRowCoeffs(int i, std::vector >& coeffs) = 0; std::vector >& coeffs) = 0; /// \e virtual void _setColCoeffs(int i, const std::vector >& coeffs) = 0; const std::vector >& coeffs) = 0; /// \e /// This routine modifies \c coeffs only by the \c push_back method. virtual void _getColCoeffs(int i, std::vector >& coeffs) = 0; /// \e virtual void _setCoeff(int col, int row, _Value value) = 0; /// \e virtual _Value _getCoeff(int col, int row) = 0; std::vector >& coeffs) = 0; /// \e virtual void _setCoeff(int col, int row, Value value) = 0; /// \e virtual Value _getCoeff(int col, int row) = 0; //  public: //    /// \e /// \e /// The lower bound of a variable (column) have to be given by an /// extended number of type _Value, i.e. a finite number of type /// _Value or -INF. virtual void _setColLowerBound(int i, _Value value) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or -INF. virtual void _setColLowerBound(int i, Value value) = 0; /// \e /// The lower bound of a variable (column) is an /// extended number of type _Value, i.e. a finite number of type /// _Value or -INF. virtual _Value _getColLowerBound(int i) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or -INF. virtual Value _getColLowerBound(int i) = 0; /// \e /// The upper bound of a variable (column) have to be given by an /// extended number of type _Value, i.e. a finite number of type /// _Value or INF. virtual void _setColUpperBound(int i, _Value value) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or INF. virtual void _setColUpperBound(int i, Value value) = 0; /// \e /// The upper bound of a variable (column) is an /// extended number of type _Value, i.e. a finite number of type /// _Value or INF. virtual _Value _getColUpperBound(int i) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or INF. virtual Value _getColUpperBound(int i) = 0; /// \e /// The lower bound of a linear expression (row) have to be given by an /// extended number of type _Value, i.e. a finite number of type /// _Value or -INF. virtual void _setRowLowerBound(int i, _Value value) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or -INF. virtual void _setRowLowerBound(int i, Value value) = 0; /// \e /// The lower bound of a linear expression (row) is an /// extended number of type _Value, i.e. a finite number of type /// _Value or -INF. virtual _Value _getRowLowerBound(int i) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or -INF. virtual Value _getRowLowerBound(int i) = 0; /// \e /// The upper bound of a linear expression (row) have to be given by an /// extended number of type _Value, i.e. a finite number of type /// _Value or INF. virtual void _setRowUpperBound(int i, _Value value) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or INF. virtual void _setRowUpperBound(int i, Value value) = 0; /// \e /// The upper bound of a linear expression (row) is an /// extended number of type _Value, i.e. a finite number of type /// _Value or INF. virtual _Value _getRowUpperBound(int i) = 0; /// \e virtual void _setObjCoeff(int i, _Value obj_coef) = 0; /// \e virtual _Value _getObjCoeff(int i) = 0; /// extended number of type Value, i.e. a finite number of type /// Value or INF. virtual Value _getRowUpperBound(int i) = 0; /// \e virtual void _setObjCoeff(int i, Value obj_coef) = 0; /// \e virtual Value _getObjCoeff(int i) = 0; //SOLUTION RETRIEVING /// \e virtual _Value _getPrimal(int i) = 0; virtual Value _getPrimal(int i) = 0; //@} } /// \e void setCoeff(Col col, Row row, _Value value) { void setCoeff(Col col, Row row, Value value) { _setCoeff(col_iter_map[col], row_iter_map[row], value); } /// \e _Value getCoeff(Col col, Row row) { Value getCoeff(Col col, Row row) { return _getCoeff(col_iter_map[col], row_iter_map[row], value); } /// \e void setColLowerBound(Col col, _Value lo) { void setColLowerBound(Col col, Value lo) { _setColLowerBound(col_iter_map[col], lo); } /// \e _Value getColLowerBound(Col col) { Value getColLowerBound(Col col) { return _getColLowerBound(col_iter_map[col]); } /// \e void setColUpperBound(Col col, _Value up) { void setColUpperBound(Col col, Value up) { _setColUpperBound(col_iter_map[col], up); } /// \e _Value getColUpperBound(Col col) { Value getColUpperBound(Col col) { return _getColUpperBound(col_iter_map[col]); } /// \e void setRowLowerBound(Row row, _Value lo) { void setRowLowerBound(Row row, Value lo) { _setRowLowerBound(row_iter_map[row], lo); } /// \e _Value getRowLowerBound(Row row) { Value getRowLowerBound(Row row) { return _getRowLowerBound(row_iter_map[row]); } /// \e void setRowUpperBound(Row row, _Value up) { void setRowUpperBound(Row row, Value up) { _setRowUpperBound(row_iter_map[row], up); } /// \e _Value getRowUpperBound(Row row) { Value getRowUpperBound(Row row) { return _getRowUpperBound(row_iter_map[row]); } /// \e void setObjCoeff(const Col& col, _Value obj_coef) { void setObjCoeff(const Col& col, Value obj_coef) { _setObjCoeff(col_iter_map[col], obj_coef); } /// \e _Value getObjCoeff(const Col& col) { Value getObjCoeff(const Col& col) { return _getObjCoeff(col_iter_map[col]); } /// \e _Value getPrimal(const Col& col) { Value getPrimal(const Col& col) { return _getPrimal(col_iter_map[col]); } /// \e typedef Expr Expression; /// \e typedef Expr DualExpression; /// \e typedef Constr Constraint; typedef Expr Expression; /// \e typedef Expr DualExpression; /// \e typedef Constr Constraint; //MATRIX MANIPULATING FUNCTIONS /// \e void setRowCoeffs(Row row, const Expression& expr) { std::vector > row_coeffs; std::vector > row_coeffs; for(typename Expression::Data::const_iterator i=expr.data.begin(); i!=expr.data.end(); ++i) { /// This routine modifies \c expr by only adding to it. void getRowCoeffs(Row row, Expression& expr) { std::vector > row_coeffs; std::vector > row_coeffs; _getRowCoeffs(row_iter_map[row], row_coeffs); for(typename std::vector >::const_iterator for(typename std::vector >::const_iterator i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) { expr+= (*i).second*int_col_map[(*i).first]; /// \e void setColCoeffs(Col col, const DualExpression& expr) { std::vector > col_coeffs; std::vector > col_coeffs; for(typename DualExpression::Data::const_iterator i=expr.data.begin(); i!=expr.data.end(); ++i) { /// This routine modifies \c expr by only adding to it. void getColCoeffs(Col col, DualExpression& expr) { std::vector > col_coeffs; std::vector > col_coeffs; _getColCoeffs(col_iter_map[col], col_coeffs); for(typename std::vector >::const_iterator for(typename std::vector >::const_iterator i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) { expr+= (*i).second*int_row_map[(*i).first]; virtual void _setColInt(int i) = 0; /// \e virtual _Value _getMIPPrimal(int i) = 0; virtual Value _getMIPPrimal(int i) = 0; public: /// \e } /// \e _Value getMIPPrimal(Col col) { Value getMIPPrimal(Col col) { return _getMIPPrimal(col_iter_map[col]); } //@} }; template const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity(); /// \brief Wrapper for GLPK solver /// /// This class implements a lemon wrapper for GLPK. class LPGLPK : public LPSolverBase { public: typedef LPSolverBase Parent; public: /// \e LPX* lp; public: /// \e LPGLPK() : Parent(), lp(lpx_create_prob()) { int_row_map.push_back(Row()); int_col_map.push_back(Col()); lpx_set_int_parm(lp, LPX_K_DUAL, 1); } /// \e ~LPGLPK() { lpx_delete_prob(lp); } //MATRIX INDEPEDENT MANIPULATING FUNCTIONS /// \e void setMinimize() { lpx_set_obj_dir(lp, LPX_MIN); } /// \e void setMaximize() { lpx_set_obj_dir(lp, LPX_MAX); } //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS protected: /// \e int _addCol() { int i=lpx_add_cols(lp, 1); _setColLowerBound(i, -INF); _setColUpperBound(i, INF); return i; } /// \e int _addRow() { int i=lpx_add_rows(lp, 1); return i; } /// \e virtual void _setRowCoeffs(int i, const std::vector >& coeffs) { int mem_length=1+colNum(); int* indices = new int[mem_length]; double* doubles = new double[mem_length]; int length=0; for (std::vector >:: const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { ++length; indices[length]=it->first; doubles[length]=it->second; } lpx_set_mat_row(lp, i, length, indices, doubles); delete [] indices; delete [] doubles; } /// \e virtual void _getRowCoeffs(int i, std::vector >& coeffs) { int mem_length=1+colNum(); int* indices = new int[mem_length]; double* doubles = new double[mem_length]; int length=lpx_get_mat_row(lp, i, indices, doubles); for (int i=1; i<=length; ++i) { coeffs.push_back(std::make_pair(indices[i], doubles[i])); } delete [] indices; delete [] doubles; } /// \e virtual void _setColCoeffs(int i, const std::vector >& coeffs) { int mem_length=1+rowNum(); int* indices = new int[mem_length]; double* doubles = new double[mem_length]; int length=0; for (std::vector >:: const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { ++length; indices[length]=it->first; doubles[length]=it->second; } lpx_set_mat_col(lp, i, length, indices, doubles); delete [] indices; delete [] doubles; } /// \e virtual void _getColCoeffs(int i, std::vector >& coeffs) { int mem_length=1+rowNum(); int* indices = new int[mem_length]; double* doubles = new double[mem_length]; int length=lpx_get_mat_col(lp, i, indices, doubles); for (int i=1; i<=length; ++i) { coeffs.push_back(std::make_pair(indices[i], doubles[i])); } delete [] indices; delete [] doubles; } /// \e virtual void _eraseCol(int i) { int cols[2]; cols[1]=i; lpx_del_cols(lp, 1, cols); } virtual void _eraseRow(int i) { int rows[2]; rows[1]=i; lpx_del_rows(lp, 1, rows); } void _setCoeff(int col, int row, double value) { /// FIXME not yet implemented } double _getCoeff(int col, int row) { /// FIXME not yet implemented return 0.0; } virtual void _setColLowerBound(int i, double lo) { if (lo==INF) { //FIXME error } int b=lpx_get_col_type(lp, i); double up=lpx_get_col_ub(lp, i); if (lo==-INF) { switch (b) { case LPX_FR: case LPX_LO: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); break; case LPX_UP: break; case LPX_DB: case LPX_FX: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); break; default: ; //FIXME error } } else { switch (b) { case LPX_FR: case LPX_LO: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); break; case LPX_UP: case LPX_DB: case LPX_FX: if (lo==up) lpx_set_col_bnds(lp, i, LPX_FX, lo, up); else lpx_set_col_bnds(lp, i, LPX_DB, lo, up); break; default: ; //FIXME error } } } virtual double _getColLowerBound(int i) { int b=lpx_get_col_type(lp, i); switch (b) { case LPX_FR: return -INF; case LPX_LO: return lpx_get_col_lb(lp, i); case LPX_UP: return -INF; case LPX_DB: case LPX_FX: return lpx_get_col_lb(lp, i); default: ; //FIXME error return 0.0; } } virtual void _setColUpperBound(int i, double up) { if (up==-INF) { //FIXME error } int b=lpx_get_col_type(lp, i); double lo=lpx_get_col_lb(lp, i); if (up==INF) { switch (b) { case LPX_FR: case LPX_LO: break; case LPX_UP: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); break; case LPX_DB: case LPX_FX: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); break; default: ; //FIXME error } } else { switch (b) { case LPX_FR: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); case LPX_LO: if (lo==up) lpx_set_col_bnds(lp, i, LPX_FX, lo, up); else lpx_set_col_bnds(lp, i, LPX_DB, lo, up); break; case LPX_UP: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); break; case LPX_DB: case LPX_FX: if (lo==up) lpx_set_col_bnds(lp, i, LPX_FX, lo, up); else lpx_set_col_bnds(lp, i, LPX_DB, lo, up); break; default: ; //FIXME error } } } virtual double _getColUpperBound(int i) { int b=lpx_get_col_type(lp, i); switch (b) { case LPX_FR: case LPX_LO: return INF; case LPX_UP: case LPX_DB: case LPX_FX: return lpx_get_col_ub(lp, i); default: ; //FIXME error return 0.0; } } virtual void _setRowLowerBound(int i, double lo) { if (lo==INF) { //FIXME error } int b=lpx_get_row_type(lp, i); double up=lpx_get_row_ub(lp, i); if (lo==-INF) { switch (b) { case LPX_FR: case LPX_LO: lpx_set_row_bnds(lp, i, LPX_FR, lo, up); break; case LPX_UP: break; case LPX_DB: case LPX_FX: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); break; default: ; //FIXME error } } else { switch (b) { case LPX_FR: case LPX_LO: lpx_set_row_bnds(lp, i, LPX_LO, lo, up); break; case LPX_UP: case LPX_DB: case LPX_FX: if (lo==up) lpx_set_row_bnds(lp, i, LPX_FX, lo, up); else lpx_set_row_bnds(lp, i, LPX_DB, lo, up); break; default: ; //FIXME error } } } virtual double _getRowLowerBound(int i) { int b=lpx_get_row_type(lp, i); switch (b) { case LPX_FR: return -INF; case LPX_LO: return lpx_get_row_lb(lp, i); case LPX_UP: return -INF; case LPX_DB: case LPX_FX: return lpx_get_row_lb(lp, i); default: ; //FIXME error return 0.0; } } virtual void _setRowUpperBound(int i, double up) { if (up==-INF) { //FIXME error } int b=lpx_get_row_type(lp, i); double lo=lpx_get_row_lb(lp, i); if (up==INF) { switch (b) { case LPX_FR: case LPX_LO: break; case LPX_UP: lpx_set_row_bnds(lp, i, LPX_FR, lo, up); break; case LPX_DB: case LPX_FX: lpx_set_row_bnds(lp, i, LPX_LO, lo, up); break; default: ; //FIXME error } } else { switch (b) { case LPX_FR: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); case LPX_LO: if (lo==up) lpx_set_row_bnds(lp, i, LPX_FX, lo, up); else lpx_set_row_bnds(lp, i, LPX_DB, lo, up); break; case LPX_UP: lpx_set_row_bnds(lp, i, LPX_UP, lo, up); break; case LPX_DB: case LPX_FX: if (lo==up) lpx_set_row_bnds(lp, i, LPX_FX, lo, up); else lpx_set_row_bnds(lp, i, LPX_DB, lo, up); break; default: ; //FIXME error } } } virtual double _getRowUpperBound(int i) { int b=lpx_get_row_type(lp, i); switch (b) { case LPX_FR: case LPX_LO: return INF; case LPX_UP: case LPX_DB: case LPX_FX: return lpx_get_row_ub(lp, i); default: ; //FIXME error return 0.0; } } /// \e virtual double _getObjCoeff(int i) { return lpx_get_obj_coef(lp, i); } /// \e virtual void _setObjCoeff(int i, double obj_coef) { lpx_set_obj_coef(lp, i, obj_coef); } public: /// \e void solveSimplex() { lpx_simplex(lp); } /// \e void solvePrimalSimplex() { lpx_simplex(lp); } /// \e void solveDualSimplex() { lpx_simplex(lp); } protected: virtual double _getPrimal(int i) { return lpx_get_col_prim(lp, i); } public: /// \e double getObjVal() { return lpx_get_obj_val(lp); } /// \e int rowNum() const { return lpx_get_num_rows(lp); } /// \e int colNum() const { return lpx_get_num_cols(lp); } /// \e int warmUp() { return lpx_warm_up(lp); } /// \e void printWarmUpStatus(int i) { switch (i) { case LPX_E_OK: cout << "LPX_E_OK" << endl; break; case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; case LPX_E_SING: cout << "LPX_E_SING" << endl; break; } } /// \e int getPrimalStatus() { return lpx_get_prim_stat(lp); } /// \e void printPrimalStatus(int i) { switch (i) { case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; } } /// \e int getDualStatus() { return lpx_get_dual_stat(lp); } /// \e void printDualStatus(int i) { switch (i) { case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; } } /// Returns the status of the slack variable assigned to row \c row. int getRowStat(const Row& row) { return lpx_get_row_stat(lp, row_iter_map[row]); } /// \e void printRowStatus(int i) { switch (i) { case LPX_BS: cout << "LPX_BS" << endl; break; case LPX_NL: cout << "LPX_NL" << endl; break; case LPX_NU: cout << "LPX_NU" << endl; break; case LPX_NF: cout << "LPX_NF" << endl; break; case LPX_NS: cout << "LPX_NS" << endl; break; } } /// Returns the status of the variable assigned to column \c col. int getColStat(const Col& col) { return lpx_get_col_stat(lp, col_iter_map[col]); } /// \e void printColStatus(int i) { switch (i) { case LPX_BS: cout << "LPX_BS" << endl; break; case LPX_NL: cout << "LPX_NL" << endl; break; case LPX_NU: cout << "LPX_NU" << endl; break; case LPX_NF: cout << "LPX_NF" << endl; break; case LPX_NS: cout << "LPX_NS" << endl; break; } } // MIP /// \e void solveBandB() { lpx_integer(lp); } /// \e void setLP() { lpx_set_class(lp, LPX_LP); } /// \e void setMIP() { lpx_set_class(lp, LPX_MIP); } protected: /// \e void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); } /// \e void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); } /// \e double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); } }; /// @} } //namespace lemon
• ## src/work/athos/lp/magic_square.cc

 r1240 #include #include #include using std::cout; Timer ts; ts.reset(); typedef LPGLPK LPSolver; typedef LpGlpk LPSolver; typedef LPSolver::Col Col; LPSolver lp;
• ## src/work/athos/lp/makefile

 r1240 LDFLAGS  =  -lglpk#-lcplex -lm -lpthread -lilocplex -L/usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_mt# -L\$(GLPKROOT)/lib BINARIES = magic_square max_flow_expression expression_test max_flow_by_lp# sample sample2 sample11 sample15 BINARIES = magic_square max_flow_expression #expression_test max_flow_by_lp# sample sample2 sample11 sample15 #include ../makefile
• ## src/work/athos/lp/max_flow_expression.cc

 r1240 #include #include #include #include using std::cout; class PrimalMap { protected: LPGLPK* lp; LpGlpk* lp; EdgeIndexMap* edge_index_map; public: PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) : PrimalMap(LpGlpk& _lp, EdgeIndexMap& _edge_index_map) : lp(&_lp), edge_index_map(&_edge_index_map) { } double operator[](Edge e) const { Timer ts; typedef LPGLPK LPSolver; typedef LpGlpk LPSolver; LPSolver lp; lp.setMaximize();
Note: See TracChangeset for help on using the changeset viewer.