# HG changeset patch # User Balazs Dezso # Date 1254608922 -7200 # Node ID e4554cd6b2bf7d7efc98c123fcf39d6f0de74354 # Parent 68792fb2870f54f66104b3cc20eba1e6e6ca5255 Faster add row operation (#203) One virtual function call instead of more diff -r 68792fb2870f -r e4554cd6b2bf lemon/cbc.cc --- a/lemon/cbc.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/cbc.cc Sun Oct 04 00:28:42 2009 +0200 @@ -94,6 +94,18 @@ return _prob->numberRows() - 1; } + int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { + std::vector indexes; + std::vector values; + + for(ExprIterator it = b; it != e; ++it) { + indexes.push_back(it->first); + values.push_back(it->second); + } + + _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); + return _prob->numberRows() - 1; + } void CbcMip::_eraseCol(int i) { _prob->deleteColumn(i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/cbc.h --- a/lemon/cbc.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/cbc.h Sun Oct 04 00:28:42 2009 +0200 @@ -62,6 +62,7 @@ virtual int _addCol(); virtual int _addRow(); + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _eraseRow(int i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/clp.cc --- a/lemon/clp.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/clp.cc Sun Oct 04 00:28:42 2009 +0200 @@ -78,6 +78,19 @@ return _prob->numberRows() - 1; } + int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { + std::vector indexes; + std::vector values; + + for(ExprIterator it = b; it != e; ++it) { + indexes.push_back(it->first); + values.push_back(it->second); + } + + _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); + return _prob->numberRows() - 1; + } + void ClpLp::_eraseCol(int c) { _col_names_ref.erase(_prob->getColumnName(c)); diff -r 68792fb2870f -r e4554cd6b2bf lemon/clp.h --- a/lemon/clp.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/clp.h Sun Oct 04 00:28:42 2009 +0200 @@ -75,6 +75,7 @@ virtual int _addCol(); virtual int _addRow(); + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _eraseRow(int i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/cplex.cc --- a/lemon/cplex.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/cplex.cc Sun Oct 04 00:28:42 2009 +0200 @@ -111,6 +111,39 @@ return i; } + int CplexBase::_addRow(Value lb, ExprIterator b, + ExprIterator e, Value ub) { + int i = CPXgetnumrows(cplexEnv(), _prob); + if (lb == -INF) { + const char s = 'L'; + CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); + } else if (ub == INF) { + const char s = 'G'; + CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); + } else if (lb == ub){ + const char s = 'E'; + CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); + } else { + const char s = 'R'; + double len = ub - lb; + CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0); + } + + std::vector indices; + std::vector rowlist; + std::vector values; + + for(ExprIterator it=b; it!=e; ++it) { + indices.push_back(it->first); + values.push_back(it->second); + rowlist.push_back(i); + } + + CPXchgcoeflist(cplexEnv(), _prob, values.size(), + &rowlist.front(), &indices.front(), &values.front()); + + return i; + } void CplexBase::_eraseCol(int i) { CPXdelcols(cplexEnv(), _prob, i, i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/cplex.h --- a/lemon/cplex.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/cplex.h Sun Oct 04 00:28:42 2009 +0200 @@ -93,6 +93,7 @@ virtual int _addCol(); virtual int _addRow(); + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _eraseRow(int i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/glpk.cc --- a/lemon/glpk.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/glpk.cc Sun Oct 04 00:28:42 2009 +0200 @@ -59,6 +59,42 @@ return i; } + int GlpkBase::_addRow(Value lo, ExprIterator b, + ExprIterator e, Value up) { + int i = glp_add_rows(lp, 1); + + if (lo == -INF) { + if (up == INF) { + glp_set_row_bnds(lp, i, GLP_FR, lo, up); + } else { + glp_set_row_bnds(lp, i, GLP_UP, lo, up); + } + } else { + if (up == INF) { + glp_set_row_bnds(lp, i, GLP_LO, lo, up); + } else if (lo != up) { + glp_set_row_bnds(lp, i, GLP_DB, lo, up); + } else { + glp_set_row_bnds(lp, i, GLP_FX, lo, up); + } + } + + std::vector indexes; + std::vector values; + + indexes.push_back(0); + values.push_back(0); + + for(ExprIterator it = b; it != e; ++it) { + indexes.push_back(it->first); + values.push_back(it->second); + } + + glp_set_mat_row(lp, i, values.size() - 1, + &indexes.front(), &values.front()); + return i; + } + void GlpkBase::_eraseCol(int i) { int ca[2]; ca[1] = i; diff -r 68792fb2870f -r e4554cd6b2bf lemon/glpk.h --- a/lemon/glpk.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/glpk.h Sun Oct 04 00:28:42 2009 +0200 @@ -54,6 +54,7 @@ virtual int _addCol(); virtual int _addRow(); + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _eraseRow(int i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/lp_base.h --- a/lemon/lp_base.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/lp_base.h Sun Oct 04 00:28:42 2009 +0200 @@ -943,6 +943,14 @@ virtual int _addCol() = 0; virtual int _addRow() = 0; + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) { + int row = _addRow(); + _setRowCoeffs(row, b, e); + _setRowLowerBound(row, l); + _setRowUpperBound(row, u); + return row; + } + virtual void _eraseCol(int col) = 0; virtual void _eraseRow(int row) = 0; @@ -1207,8 +1215,10 @@ ///\param u is the upper bound (\ref INF means no bound) ///\return The created row. Row addRow(Value l,const Expr &e, Value u) { - Row r=addRow(); - row(r,l,e,u); + Row r; + e.simplify(); + r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols), + ExprIterator(e.comps.end(), cols), u - *e)); return r; } @@ -1217,8 +1227,12 @@ ///\param c is a linear expression (see \ref Constr) ///\return The created row. Row addRow(const Constr &c) { - Row r=addRow(); - row(r,c); + Row r; + c.expr().simplify(); + r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF, + ExprIterator(c.expr().comps.begin(), cols), + ExprIterator(c.expr().comps.end(), cols), + c.upperBounded()?c.upperBound():INF)); return r; } ///Erase a column (i.e a variable) from the LP diff -r 68792fb2870f -r e4554cd6b2bf lemon/lp_skeleton.cc --- a/lemon/lp_skeleton.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/lp_skeleton.cc Sun Oct 04 00:28:42 2009 +0200 @@ -32,6 +32,11 @@ return ++row_num; } + int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value) + { + return ++row_num; + } + void SkeletonSolverBase::_eraseCol(int) {} void SkeletonSolverBase::_eraseRow(int) {} diff -r 68792fb2870f -r e4554cd6b2bf lemon/lp_skeleton.h --- a/lemon/lp_skeleton.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/lp_skeleton.h Sun Oct 04 00:28:42 2009 +0200 @@ -45,6 +45,8 @@ /// \e virtual int _addRow(); /// \e + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); + /// \e virtual void _eraseCol(int i); /// \e virtual void _eraseRow(int i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/soplex.cc --- a/lemon/soplex.cc Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/soplex.cc Sun Oct 04 00:28:42 2009 +0200 @@ -91,6 +91,19 @@ return soplex->nRows() - 1; } + int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { + soplex::DSVector v; + for (ExprIterator it = b; it != e; ++it) { + v.add(it->first, it->second); + } + soplex::LPRow r(l, v, u); + soplex->addRow(r); + + _row_names.push_back(std::string()); + + return soplex->nRows() - 1; + } + void SoplexLp::_eraseCol(int i) { soplex->removeCol(i); diff -r 68792fb2870f -r e4554cd6b2bf lemon/soplex.h --- a/lemon/soplex.h Fri Oct 02 17:03:43 2009 +0200 +++ b/lemon/soplex.h Sun Oct 04 00:28:42 2009 +0200 @@ -84,6 +84,7 @@ virtual int _addCol(); virtual int _addRow(); + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _eraseRow(int i);