Faster add row operation (#203)
authorBalazs Dezso <deba@inf.elte.hu>
Sun, 04 Oct 2009 00:28:42 +0200
changeset 793e4554cd6b2bf
parent 792 68792fb2870f
child 794 a42f46828cc1
Faster add row operation (#203)

One virtual function call instead of more
lemon/cbc.cc
lemon/cbc.h
lemon/clp.cc
lemon/clp.h
lemon/cplex.cc
lemon/cplex.h
lemon/glpk.cc
lemon/glpk.h
lemon/lp_base.h
lemon/lp_skeleton.cc
lemon/lp_skeleton.h
lemon/soplex.cc
lemon/soplex.h
     1.1 --- a/lemon/cbc.cc	Fri Oct 02 17:03:43 2009 +0200
     1.2 +++ b/lemon/cbc.cc	Sun Oct 04 00:28:42 2009 +0200
     1.3 @@ -94,6 +94,18 @@
     1.4      return _prob->numberRows() - 1;
     1.5    }
     1.6  
     1.7 +  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     1.8 +    std::vector<int> indexes;
     1.9 +    std::vector<Value> values;
    1.10 +
    1.11 +    for(ExprIterator it = b; it != e; ++it) {
    1.12 +      indexes.push_back(it->first);
    1.13 +      values.push_back(it->second);
    1.14 +    }
    1.15 +
    1.16 +    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    1.17 +    return _prob->numberRows() - 1;
    1.18 +  }
    1.19  
    1.20    void CbcMip::_eraseCol(int i) {
    1.21      _prob->deleteColumn(i);
     2.1 --- a/lemon/cbc.h	Fri Oct 02 17:03:43 2009 +0200
     2.2 +++ b/lemon/cbc.h	Sun Oct 04 00:28:42 2009 +0200
     2.3 @@ -62,6 +62,7 @@
     2.4  
     2.5      virtual int _addCol();
     2.6      virtual int _addRow();
     2.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     2.8  
     2.9      virtual void _eraseCol(int i);
    2.10      virtual void _eraseRow(int i);
     3.1 --- a/lemon/clp.cc	Fri Oct 02 17:03:43 2009 +0200
     3.2 +++ b/lemon/clp.cc	Sun Oct 04 00:28:42 2009 +0200
     3.3 @@ -78,6 +78,19 @@
     3.4      return _prob->numberRows() - 1;
     3.5    }
     3.6  
     3.7 +  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     3.8 +    std::vector<int> indexes;
     3.9 +    std::vector<Value> values;
    3.10 +
    3.11 +    for(ExprIterator it = b; it != e; ++it) {
    3.12 +      indexes.push_back(it->first);
    3.13 +      values.push_back(it->second);
    3.14 +    }
    3.15 +
    3.16 +    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    3.17 +    return _prob->numberRows() - 1;
    3.18 +  }
    3.19 +
    3.20  
    3.21    void ClpLp::_eraseCol(int c) {
    3.22      _col_names_ref.erase(_prob->getColumnName(c));
     4.1 --- a/lemon/clp.h	Fri Oct 02 17:03:43 2009 +0200
     4.2 +++ b/lemon/clp.h	Sun Oct 04 00:28:42 2009 +0200
     4.3 @@ -75,6 +75,7 @@
     4.4  
     4.5      virtual int _addCol();
     4.6      virtual int _addRow();
     4.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     4.8  
     4.9      virtual void _eraseCol(int i);
    4.10      virtual void _eraseRow(int i);
     5.1 --- a/lemon/cplex.cc	Fri Oct 02 17:03:43 2009 +0200
     5.2 +++ b/lemon/cplex.cc	Sun Oct 04 00:28:42 2009 +0200
     5.3 @@ -111,6 +111,39 @@
     5.4      return i;
     5.5    }
     5.6  
     5.7 +  int CplexBase::_addRow(Value lb, ExprIterator b, 
     5.8 +                         ExprIterator e, Value ub) {
     5.9 +    int i = CPXgetnumrows(cplexEnv(), _prob);
    5.10 +    if (lb == -INF) {
    5.11 +      const char s = 'L';
    5.12 +      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
    5.13 +    } else if (ub == INF) {
    5.14 +      const char s = 'G';
    5.15 +      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
    5.16 +    } else if (lb == ub){
    5.17 +      const char s = 'E';
    5.18 +      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
    5.19 +    } else {
    5.20 +      const char s = 'R';
    5.21 +      double len = ub - lb;
    5.22 +      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
    5.23 +    }
    5.24 +
    5.25 +    std::vector<int> indices;
    5.26 +    std::vector<int> rowlist;
    5.27 +    std::vector<Value> values;
    5.28 +
    5.29 +    for(ExprIterator it=b; it!=e; ++it) {
    5.30 +      indices.push_back(it->first);
    5.31 +      values.push_back(it->second);
    5.32 +      rowlist.push_back(i);
    5.33 +    }
    5.34 +
    5.35 +    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
    5.36 +                   &rowlist.front(), &indices.front(), &values.front());
    5.37 +
    5.38 +    return i;
    5.39 +  }
    5.40  
    5.41    void CplexBase::_eraseCol(int i) {
    5.42      CPXdelcols(cplexEnv(), _prob, i, i);
     6.1 --- a/lemon/cplex.h	Fri Oct 02 17:03:43 2009 +0200
     6.2 +++ b/lemon/cplex.h	Sun Oct 04 00:28:42 2009 +0200
     6.3 @@ -93,6 +93,7 @@
     6.4  
     6.5      virtual int _addCol();
     6.6      virtual int _addRow();
     6.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     6.8  
     6.9      virtual void _eraseCol(int i);
    6.10      virtual void _eraseRow(int i);
     7.1 --- a/lemon/glpk.cc	Fri Oct 02 17:03:43 2009 +0200
     7.2 +++ b/lemon/glpk.cc	Sun Oct 04 00:28:42 2009 +0200
     7.3 @@ -59,6 +59,42 @@
     7.4      return i;
     7.5    }
     7.6  
     7.7 +  int GlpkBase::_addRow(Value lo, ExprIterator b, 
     7.8 +                        ExprIterator e, Value up) {
     7.9 +    int i = glp_add_rows(lp, 1);
    7.10 +
    7.11 +    if (lo == -INF) {
    7.12 +      if (up == INF) {
    7.13 +        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
    7.14 +      } else {
    7.15 +        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
    7.16 +      }    
    7.17 +    } else {
    7.18 +      if (up == INF) {
    7.19 +        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
    7.20 +      } else if (lo != up) {        
    7.21 +        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
    7.22 +      } else {
    7.23 +        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
    7.24 +      }
    7.25 +    }
    7.26 +
    7.27 +    std::vector<int> indexes;
    7.28 +    std::vector<Value> values;
    7.29 +
    7.30 +    indexes.push_back(0);
    7.31 +    values.push_back(0);
    7.32 +
    7.33 +    for(ExprIterator it = b; it != e; ++it) {
    7.34 +      indexes.push_back(it->first);
    7.35 +      values.push_back(it->second);
    7.36 +    }
    7.37 +
    7.38 +    glp_set_mat_row(lp, i, values.size() - 1,
    7.39 +                    &indexes.front(), &values.front());
    7.40 +    return i;
    7.41 +  }
    7.42 +
    7.43    void GlpkBase::_eraseCol(int i) {
    7.44      int ca[2];
    7.45      ca[1] = i;
     8.1 --- a/lemon/glpk.h	Fri Oct 02 17:03:43 2009 +0200
     8.2 +++ b/lemon/glpk.h	Sun Oct 04 00:28:42 2009 +0200
     8.3 @@ -54,6 +54,7 @@
     8.4  
     8.5      virtual int _addCol();
     8.6      virtual int _addRow();
     8.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     8.8  
     8.9      virtual void _eraseCol(int i);
    8.10      virtual void _eraseRow(int i);
     9.1 --- a/lemon/lp_base.h	Fri Oct 02 17:03:43 2009 +0200
     9.2 +++ b/lemon/lp_base.h	Sun Oct 04 00:28:42 2009 +0200
     9.3 @@ -943,6 +943,14 @@
     9.4      virtual int _addCol() = 0;
     9.5      virtual int _addRow() = 0;
     9.6  
     9.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     9.8 +      int row = _addRow();
     9.9 +      _setRowCoeffs(row, b, e);
    9.10 +      _setRowLowerBound(row, l);
    9.11 +      _setRowUpperBound(row, u);
    9.12 +      return row;
    9.13 +    }
    9.14 +
    9.15      virtual void _eraseCol(int col) = 0;
    9.16      virtual void _eraseRow(int row) = 0;
    9.17  
    9.18 @@ -1207,8 +1215,10 @@
    9.19      ///\param u is the upper bound (\ref INF means no bound)
    9.20      ///\return The created row.
    9.21      Row addRow(Value l,const Expr &e, Value u) {
    9.22 -      Row r=addRow();
    9.23 -      row(r,l,e,u);
    9.24 +      Row r;
    9.25 +      e.simplify();
    9.26 +      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
    9.27 +                                ExprIterator(e.comps.end(), cols), u - *e));
    9.28        return r;
    9.29      }
    9.30  
    9.31 @@ -1217,8 +1227,12 @@
    9.32      ///\param c is a linear expression (see \ref Constr)
    9.33      ///\return The created row.
    9.34      Row addRow(const Constr &c) {
    9.35 -      Row r=addRow();
    9.36 -      row(r,c);
    9.37 +      Row r;
    9.38 +      c.expr().simplify();
    9.39 +      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF, 
    9.40 +                                ExprIterator(c.expr().comps.begin(), cols),
    9.41 +                                ExprIterator(c.expr().comps.end(), cols),
    9.42 +                                c.upperBounded()?c.upperBound():INF));
    9.43        return r;
    9.44      }
    9.45      ///Erase a column (i.e a variable) from the LP
    10.1 --- a/lemon/lp_skeleton.cc	Fri Oct 02 17:03:43 2009 +0200
    10.2 +++ b/lemon/lp_skeleton.cc	Sun Oct 04 00:28:42 2009 +0200
    10.3 @@ -32,6 +32,11 @@
    10.4      return ++row_num;
    10.5    }
    10.6  
    10.7 +  int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value)
    10.8 +  {
    10.9 +    return ++row_num;
   10.10 +  }
   10.11 +
   10.12    void SkeletonSolverBase::_eraseCol(int) {}
   10.13    void SkeletonSolverBase::_eraseRow(int) {}
   10.14  
    11.1 --- a/lemon/lp_skeleton.h	Fri Oct 02 17:03:43 2009 +0200
    11.2 +++ b/lemon/lp_skeleton.h	Sun Oct 04 00:28:42 2009 +0200
    11.3 @@ -45,6 +45,8 @@
    11.4      /// \e
    11.5      virtual int _addRow();
    11.6      /// \e
    11.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    11.8 +    /// \e
    11.9      virtual void _eraseCol(int i);
   11.10      /// \e
   11.11      virtual void _eraseRow(int i);
    12.1 --- a/lemon/soplex.cc	Fri Oct 02 17:03:43 2009 +0200
    12.2 +++ b/lemon/soplex.cc	Sun Oct 04 00:28:42 2009 +0200
    12.3 @@ -91,6 +91,19 @@
    12.4      return soplex->nRows() - 1;
    12.5    }
    12.6  
    12.7 +  int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    12.8 +    soplex::DSVector v;
    12.9 +    for (ExprIterator it = b; it != e; ++it) {
   12.10 +      v.add(it->first, it->second);
   12.11 +    }
   12.12 +    soplex::LPRow r(l, v, u);
   12.13 +    soplex->addRow(r);
   12.14 +
   12.15 +    _row_names.push_back(std::string());
   12.16 +
   12.17 +    return soplex->nRows() - 1;
   12.18 +  }
   12.19 +
   12.20  
   12.21    void SoplexLp::_eraseCol(int i) {
   12.22      soplex->removeCol(i);
    13.1 --- a/lemon/soplex.h	Fri Oct 02 17:03:43 2009 +0200
    13.2 +++ b/lemon/soplex.h	Sun Oct 04 00:28:42 2009 +0200
    13.3 @@ -84,6 +84,7 @@
    13.4  
    13.5      virtual int _addCol();
    13.6      virtual int _addRow();
    13.7 +    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    13.8  
    13.9      virtual void _eraseCol(int i);
   13.10      virtual void _eraseRow(int i);