# HG changeset patch # User marci # Date 1107190812 0 # Node ID ba28dfbea5f274c2f67c17ac3d499841d26f74dc # Parent 5222b3d588c3e1c1c07120476cfb1363cdd8e48f new functions for changing lower and upper bounds of variables diff -r 5222b3d588c3 -r ba28dfbea5f2 src/work/marci/lp/lp_solver_wrapper_3.h --- a/src/work/marci/lp/lp_solver_wrapper_3.h Sat Jan 29 23:22:56 2005 +0000 +++ b/src/work/marci/lp/lp_solver_wrapper_3.h Mon Jan 31 17:00:12 2005 +0000 @@ -237,6 +237,26 @@ enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED }; protected: /// \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; + /// \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; + /// \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; + /// \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; + /// \e virtual void _setColBounds(int i, Bound bound, _Value lo, _Value up) = 0; /// \e @@ -257,7 +277,7 @@ public: /// \e RowIt addRow() { - int i=_addRow(); + int i=_addRow(); RowIt row_it; row_iter_map.first(row_it, INVALID_CLASS); if (row_iter_map.valid(row_it)) { //van hasznalhato hely @@ -328,6 +348,22 @@ } } /// \e + void setColLowerBound(ColIt col_it, _Value lo) { + _setColLowerBound(col_iter_map[col_it], lo); + } + /// \e + void setColUpperBound(ColIt col_it, _Value up) { + _setColUpperBound(col_iter_map[col_it], up); + } + /// \e + _Value getColLowerBound(ColIt col_it) { + return _getColLowerBound(col_iter_map[col_it]); + } + /// \e + _Value getColUpperBound(ColIt col_it) { + return _getColUpperBound(col_iter_map[col_it]); + } + /// \e void setColBounds(const ColIt& col_it, Bound bound, _Value lo, _Value up) { _setColBounds(col_iter_map[col_it], bound, lo, up); @@ -472,11 +508,15 @@ protected: /// \e int _addCol() { - return lpx_add_cols(lp, 1); + int i=lpx_add_cols(lp, 1); + _setColLowerBound(i, -INF); + _setColUpperBound(i, INF); + return i; } /// \e int _addRow() { - return lpx_add_rows(lp, 1); + int i=lpx_add_rows(lp, 1); + return i; } /// \e virtual void _setRowCoeffs(int i, @@ -526,6 +566,124 @@ rows[1]=i; lpx_del_rows(lp, 1, rows); } + 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 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 _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 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 _setColBounds(int i, Bound bound, double lo, double up) { switch (bound) { diff -r 5222b3d588c3 -r ba28dfbea5f2 src/work/marci/lp/max_flow_expression.cc --- a/src/work/marci/lp/max_flow_expression.cc Sat Jan 29 23:22:56 2005 +0000 +++ b/src/work/marci/lp/max_flow_expression.cc Mon Jan 31 17:00:12 2005 +0000 @@ -49,16 +49,17 @@ typedef LPSolver::RowIt RowIt; typedef Graph::EdgeMap EdgeIndexMap; EdgeIndexMap edge_index_map(g); - PrimalMap lp_flow(lp, edge_index_map); + PrimalMap flow(lp, edge_index_map); // capacity function for (Graph::EdgeIt e(g); e!=INVALID; ++e) { ColIt col_it=lp.addCol(); edge_index_map.set(e, col_it); - if (cap[e]==0) - lp.setColBounds(col_it, LPSolver::FIXED, 0, cap[e]); - else - lp.setColBounds(col_it, LPSolver::DOUBLE, 0, cap[e]); + // interesting property in GLPK: + // if you change the order of the following two lines, the + // two runs of GLPK are extremely different + lp.setColUpperBound(col_it, cap[e]); + lp.setColLowerBound(col_it, 0); } for (Graph::NodeIt n(g); n!=INVALID; ++n) { @@ -79,9 +80,5 @@ } } lp.solveSimplex(); - //std::cout << lp.colNum() << std::endl; - //std::cout << lp.rowNum() << std::endl; - //std::cout << "flow value: "<< lp.getObjVal() << std::endl; - for (Graph::EdgeIt e(g); e!=INVALID; ++e) - flow.set(e, lp_flow[e]); + cout << "elapsed time: " << ts << endl; }