Changeset 2312:07e46cbb7d85 in lemon-0.x

Timestamp:

11/29/06 16:01:13 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3088

Message:

modified _setColCoeff and _setRowCoeff parameters
const simplify() for expressions

Location:

lemon

Files:

• lp.h (modified) (2 diffs)
• lp_base.h (modified) (35 diffs)
• lp_cplex.cc (modified) (1 diff)
• lp_cplex.h (modified) (1 diff)
• lp_glpk.cc (modified) (2 diffs)
• lp_glpk.h (modified) (1 diff)
• lp_skeleton.cc (modified) (1 diff)
• lp_skeleton.h (modified) (1 diff)

lemon/lp.h

@@ -29 +29 @@
 #include <lemon/lp_cplex.h>
 #include <lemon/mip_cplex.h>
+#elif HAVE_SOPLEX
+#include <lemon/lp_soplex.h>
 #endif
 
@@ -77 +79 @@
   typedef MipCplex Mip;
   const char default_solver_name[]="CPLEX";
+#elif HAVE_SOPLEX
+#define DEFAULT_LP SOPLEX
+  typedef LpSoplex Lp;
+  const char default_solver_name[]="SOPLEX";
 #endif
 #endif

lemon/lp_base.h

@@ -33 +33 @@
 ///\ingroup gen_opt_group
 namespace lemon {
-  
+
+
   ///Internal data structure to convert floating id's to fix one's
     
@@ -110 +111 @@
     int firstIndex() {return _first_index;}
   };
-    
+
   ///Common base class for LP solvers
   
@@ -129 +130 @@
       ///has been proved.
       SOLVED = 0,
-      ///Any other case (including the case when some user specified limit has been exceeded)
+      ///Any other case (including the case when some user specified
+      ///limit has been exceeded)
       UNSOLVED = 1
     };
@@ -222 +224 @@
       }
     };
+
+    static int id(const Col& col) { return col.id; }
+ 
       
     ///Refer to a row of the LP.
@@ -246 +251 @@
       bool operator==(Row c) const  {return id==c.id;}
       bool operator!=(Row c) const  {return id!=c.id;} 
-   };
+    };
+
+    static int id(const Row& row) { return row.id; }
+
+  protected:
+
+    int _lpId(const Col& col) const {
+      return cols.floatingId(id(col));
+    }
+
+    int _lpId(const Row& row) const {
+      return rows.floatingId(id(row));
+    }
+
+
+  public:
     
     ///Linear expression of variables and a constant component
@@ -337 +357 @@
       }
 
+      void simplify() const {
+        const_cast<Expr*>(this)->simplify();
+      }
+
       ///Removes the coefficients closer to zero than \c tolerance.
       void simplify(double &tolerance) {
@@ -416 +440 @@
       typedef Expr::Value Value;
       
-//       static const Value INF;
-//       static const Value NaN;
-
     protected:
       Expr _expr;
@@ -554 +575 @@
       }
 
+      void simplify() const {
+        const_cast<DualExpr*>(this)->simplify();
+      }
+
       ///Removes the coefficients closer to zero than \c tolerance.
       void simplify(double &tolerance) {
@@ -564 +589 @@
       }
 
-
       ///Sets all coefficients to 0.
       void clear() {
@@ -597 +621 @@
     
 
+  private:
+
+    template <typename _Base>
+    class MappedIterator {
+    public:
+
+      typedef _Base Base;
+
+      typedef typename Base::iterator_category iterator_category;
+      typedef typename Base::difference_type difference_type;
+      typedef const std::pair<int, Value> value_type;
+      typedef value_type reference;
+      class pointer {
+      public:
+        pointer(value_type& _value) : value(_value) {}
+        value_type* operator->() { return &value; }
+      private:
+        value_type value;
+      };
+
+      MappedIterator(const Base& _base, const LpSolverBase& _lp) 
+        : base(_base), lp(_lp) {}
+
+      reference operator*() {
+        return std::make_pair(lp._lpId(base->first), base->second);
+      }
+
+      pointer operator->() {
+        return pointer(operator*());
+      }
+
+      MappedIterator& operator++() {
+        ++base;
+        return *this;
+      }
+
+      MappedIterator& operator++(int) {
+        MappedIterator tmp(*this);
+        ++base;
+        return tmp;
+      }
+
+      bool operator==(const MappedIterator& it) const {
+        return base == it.base;
+      }
+
+      bool operator!=(const MappedIterator& it) const {
+        return base != it.base;
+      }
+
+    private:
+      Base base;
+      const LpSolverBase& lp;
+    };
+
   protected:
+
+    /// STL compatible iterator for lp col
+    typedef MappedIterator<Expr::const_iterator> LpRowIterator;
+    /// STL compatible iterator for lp row
+    typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
 
     //Abstract virtual functions
     virtual LpSolverBase &_newLp() = 0;
     virtual LpSolverBase &_copyLp(){
-      ///\todo This should be implemented here, too,  when we have problem retrieving routines. It can be overriden.
+      ///\todo This should be implemented here, too, when we have
+      ///problem retrieving routines. It can be overriden.
 
       //Starting:
@@ -614 +699 @@
     virtual void _eraseCol(int col) = 0;
     virtual void _eraseRow(int row) = 0;
-    virtual void _getColName(int col,       std::string & name) = 0;
+    virtual void _getColName(int col, std::string & name) = 0;
     virtual void _setColName(int col, const std::string & name) = 0;
-    virtual void _setRowCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values ) = 0;
-    virtual void _setColCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values ) = 0;
+    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
+    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
     virtual void _setCoeff(int row, int col, Value value) = 0;
     virtual void _setColLowerBound(int i, Value value) = 0;
@@ -632 +711 @@
     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
     virtual void _clearObj()=0;
-//     virtual void _setObj(int length,
-//                          int  const * indices, 
-//                          Value  const * values ) = 0;
+
     virtual SolveExitStatus _solve() = 0;
     virtual Value _getPrimal(int i) = 0;
@@ -653 +730 @@
     //Constant component of the objective function
     Value obj_const_comp;
-    
-
-
-    
+        
   public:
 
@@ -745 +819 @@
     ///a better one.
     void col(Col c,const DualExpr &e) {
-      std::vector<int> indices;
-      std::vector<Value> values;
-      indices.push_back(0);
-      values.push_back(0);
-      for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
-        if((*i).second!=0) {
-          indices.push_back(rows.floatingId((*i).first.id));
-          values.push_back((*i).second);
-        }
-      _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
-                    &indices[0],&values[0]);
+      e.simplify();
+      _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this), 
+                    LpColIterator(e.end(), *this));
     }
 
@@ -850 +916 @@
     ///added or not.
     void row(Row r, Value l,const Expr &e, Value u) {
-      std::vector<int> indices;
-      std::vector<Value> values;
-      indices.push_back(0);
-      values.push_back(0);
-      for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
-        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
-          indices.push_back(cols.floatingId((*i).first.id));
-          values.push_back((*i).second);
-        }
-      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
-                    &indices[0],&values[0]);
-//       _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
-//       _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
-       _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
+      e.simplify();
+      _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
+                    LpRowIterator(e.end(), *this));
+//       _setRowLowerBound(_lpId(r),l-e.constComp());
+//       _setRowUpperBound(_lpId(r),u-e.constComp());
+       _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
     }
 
@@ -871 +929 @@
     ///\param c is a linear expression (see \ref Constr)
     void row(Row r, const Constr &c) {
-      row(r,
-             c.lowerBounded()?c.lowerBound():-INF,
-             c.expr(),
-             c.upperBounded()?c.upperBound():INF);
+      row(r, c.lowerBounded()?c.lowerBound():-INF,
+          c.expr(), c.upperBounded()?c.upperBound():INF);
     }
 
@@ -905 +961 @@
     ///\todo Please check this
     void eraseCol(Col c) {
-      _eraseCol(cols.floatingId(c.id));
+      _eraseCol(_lpId(c));
       cols.erase(c.id);
     }
@@ -913 +969 @@
     ///\todo Please check this
     void eraseRow(Row r) {
-      _eraseRow(rows.floatingId(r.id));
+      _eraseRow(_lpId(r));
       rows.erase(r.id);
     }
@@ -923 +979 @@
     std::string colName(Col c){
       std::string name;
-      _getColName(cols.floatingId(c.id), name);
+      _getColName(_lpId(c), name);
       return name;
     }
@@ -931 +987 @@
     ///\param c is the coresponding coloumn 
     ///\param name The name to be given
-    void colName(Col c, const std::string & name){
-      _setColName(cols.floatingId(c.id), name);
+    void colName(Col c, const std::string& name){
+      _setColName(_lpId(c), name);
     }
     
@@ -942 +998 @@
 
     void coeff(Row r, Col c, Value val){
-      _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
+      _setCoeff(_lpId(r),_lpId(c), val);
     }
 
@@ -951 +1007 @@
     /// Value or -\ref INF.
     void colLowerBound(Col c, Value value) {
-      _setColLowerBound(cols.floatingId(c.id),value);
+      _setColLowerBound(_lpId(c),value);
     }
     
@@ -997 +1053 @@
     /// Value or \ref INF.
     void colUpperBound(Col c, Value value) {
-      _setColUpperBound(cols.floatingId(c.id),value);
+      _setColUpperBound(_lpId(c),value);
     };
 
@@ -1044 +1100 @@
     /// Value, -\ref INF or \ref INF.
     void colBounds(Col c, Value lower, Value upper) {
-      _setColLowerBound(cols.floatingId(c.id),lower);
-      _setColUpperBound(cols.floatingId(c.id),upper);
+      _setColLowerBound(_lpId(c),lower);
+      _setColUpperBound(_lpId(c),upper);
     }
     
@@ -1092 +1148 @@
 //     /// Value or -\ref INF.
 //     void rowLowerBound(Row r, Value value) {
-//       _setRowLowerBound(rows.floatingId(r.id),value);
+//       _setRowLowerBound(_lpId(r),value);
 //     };
 //     /// Set the upper bound of a row (i.e a constraint)
@@ -1100 +1156 @@
 //     /// Value or \ref INF.
 //     void rowUpperBound(Row r, Value value) {
-//       _setRowUpperBound(rows.floatingId(r.id),value);
+//       _setRowUpperBound(_lpId(r),value);
 //     };
 
@@ -1110 +1166 @@
     /// Value, -\ref INF or \ref INF.
     void rowBounds(Row c, Value lower, Value upper) {
-      _setRowBounds(rows.floatingId(c.id),lower, upper);
-      // _setRowUpperBound(rows.floatingId(c.id),upper);
+      _setRowBounds(_lpId(c),lower, upper);
+      // _setRowUpperBound(_lpId(c),upper);
     }
     
     ///Set an element of the objective function
-    void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
+    void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
     ///Set the objective function
     
@@ -1171 +1227 @@
 
     ///\e
-    Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
+    Value primal(Col c) { return _getPrimal(_lpId(c)); }
 
     ///\e
-    Value dual(Row r) { return _getDual(rows.floatingId(r.id)); }
+    Value dual(Row r) { return _getDual(_lpId(r)); }
 
     ///\e
-    bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); }
+    bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); }
 
     ///\e
@@ -1214 +1270 @@
     ///Sets the type of the given coloumn to the given type.
     void colType(Col c, ColTypes col_type) {
-      _colType(cols.floatingId(c.id),col_type);
+      _colType(_lpId(c),col_type);
     }
 
@@ -1221 +1277 @@
     ///Gives back the type of the column.
     ColTypes colType(Col c){
-      return _colType(cols.floatingId(c.id));
+      return _colType(_lpId(c));
     }
 
@@ -1441 +1497 @@
   ///
   inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1452 +1508 @@
   ///
   inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1463 +1519 @@
   ///
   inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::Value &b) 
+                                          const LpSolverBase::Value &b) 
   {
     LpSolverBase::DualExpr tmp(a);
@@ -1475 +1531 @@
   ///
   inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
-                                      const LpSolverBase::DualExpr &b) 
+                                          const LpSolverBase::DualExpr &b) 
   {
     LpSolverBase::DualExpr tmp(b);
@@ -1486 +1542 @@
   ///
   inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
-                                      const LpSolverBase::Value &b) 
+                                          const LpSolverBase::Value &b) 
   {
     LpSolverBase::DualExpr tmp(a);

lemon/lp_cplex.cc

@@ -110 +110 @@
   
   ///\warning Data at index 0 is ignored in the arrays.
-  void LpCplex::_setRowCoeffs(int i, 
-                              int length,
-                              int  const * indices, 
-                              Value  const * values )
-  {
-    int rowlist[length+1];
-    int* p=rowlist;
-    for (int k=1;k<=length;++k){
-      rowlist[k]=i;
-    }
-    status = CPXchgcoeflist(env, lp, 
-                            length, 
-                            p+1, 
-                            const_cast<int * >(indices+1), 
-                            const_cast<Value * >(values+1));
-  }
-  
-  void LpCplex::_setColCoeffs(int i, 
-                              int length,
-                              int  const * indices, 
-                              Value  const * values)
-  {
-    int collist[length+1];
-    int* p=collist;
-    for (int k=1;k<=length;++k){
-      collist[k]=i;
-    }
-    status = CPXchgcoeflist(env, lp, 
-                            length, 
-                            const_cast<int * >(indices+1), 
-                            p+1, 
-                            const_cast<Value * >(values+1));
+  void LpCplex::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
+  {
+    std::vector<int> indices;
+    std::vector<int> rowlist;
+    std::vector<Value> values;
+
+    for(LpRowIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+      rowlist.push_back(i);
+    }
+
+    status = CPXchgcoeflist(env, lp, values.size(), 
+                            &rowlist[0], &indices[0], &values[0]); 
+  }
+  
+  void LpCplex::_setColCoeffs(int i, LpColIterator b, LpColIterator e)
+  {
+    std::vector<int> indices;
+    std::vector<int> collist;
+    std::vector<Value> values;
+
+    for(LpColIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+      collist.push_back(i);
+    }
+
+    status = CPXchgcoeflist(env, lp, values.size(), 
+                            &indices[0], &collist[0], &values[0]); 
   }
   

lemon/lp_cplex.h

@@ -62 +62 @@
     virtual void _getColName(int col,       std::string & name);
     virtual void _setColName(int col, const std::string & name);
-    virtual void _setRowCoeffs(int i, 
-                               int length,
-                               const int   * indices, 
-                               const Value   * values );
-    virtual void _setColCoeffs(int i, 
-                               int length,
-                               const int   * indices, 
-                               const Value   * values);
+    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
+    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     virtual void _setCoeff(int row, int col, Value value);
     virtual void _setColLowerBound(int i, Value value);

lemon/lp_glpk.cc

@@ -117 +117 @@
   }
   
-  void LpGlpk::_setRowCoeffs(int i, 
-                             int length,
-                             const int   * indices, 
-                             const Value   * values )
-  {
-    lpx_set_mat_row(lp, i, length,
-                    const_cast<int * >(indices) ,
-                    const_cast<Value * >(values));
-  }
-  
-  void LpGlpk::_setColCoeffs(int i, 
-                             int length,
-                             const int   * indices, 
-                             const Value   * values)
-  {
-    lpx_set_mat_col(lp, i, length,
-                    const_cast<int * >(indices),
-                    const_cast<Value * >(values));
+  void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) 
+  {
+    std::vector<int> indices;
+    std::vector<Value> values;
+
+    indices.push_back(0);
+    values.push_back(0);
+
+    for(LpRowIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
+  }
+  
+  void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
+
+    std::vector<int> indices;
+    std::vector<Value> values;
+
+    indices.push_back(0);
+    values.push_back(0);
+
+    for(LpColIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+    }
+    
+    lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
   }
 
@@ -140 +152 @@
   void LpGlpk::_setCoeff(int row, int col, Value value) 
   {
-    ///FIXME Of course this is not efficient at all, but GLPK knows not more.
-    // First approach: get one row, apply changes and set it again
-    //(one idea to improve this: maybe it is better to do this with 1 coloumn)
+
+    if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
+
+      int length=lpx_get_mat_row(lp, row, 0, 0);
+      
+      std::vector<int> indices(length + 2);
+      std::vector<Value> values(length + 2);
+      
+      lpx_get_mat_row(lp, row, &indices[0], &values[0]);
+      
+      //The following code does not suppose that the elements of the
+      //array indices are sorted
+      bool found=false;
+      for (int i = 1; i <= length; ++i) {
+        if (indices[i]==col){
+          found=true;
+          values[i]=value;
+          break;
+        }
+      }
+      if (!found){
+        ++length;
+        indices[length]=col;
+        values[length]=value;
+      }
     
-    int mem_length=2+lpx_get_num_cols(lp);
-    int* indices = new int[mem_length];
-    Value* values = new Value[mem_length];
+      lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
+
+    } else {
+
+      int length=lpx_get_mat_col(lp, col, 0, 0);
+      
+      std::vector<int> indices(length + 2);
+      std::vector<Value> values(length + 2);
+      
+      lpx_get_mat_col(lp, col, &indices[0], &values[0]);
+      
+      //The following code does not suppose that the elements of the
+      //array indices are sorted
+      bool found=false;
+      for (int i = 1; i <= length; ++i) {
+        if (indices[i]==col){
+          found=true;
+          values[i]=value;
+          break;
+        }
+      }
+      if (!found){
+        ++length;
+        indices[length]=row;
+        values[length]=value;
+      }
     
-
-    int length=lpx_get_mat_row(lp, row, indices, values);
-
-    //The following code does not suppose that the elements of the array indices are sorted
-    int i=1;
-    bool found=false;
-    while (i <= length && !found){
-      if (indices[i]==col){
-        found = true;
-        values[i]=value;
-      }
-      ++i;
-    }
-    if (!found){
-      ++length;
-      indices[length]=col;
-      values[length]=value;
-    }
-    
-    lpx_set_mat_row(lp, row, length, indices, values);
-    delete [] indices;
-    delete [] values;
-    
+      lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
+    }
   }
 

lemon/lp_glpk.h

@@ -57 +57 @@
     virtual void _getColName(int col,       std::string & name);
     virtual void _setColName(int col, const std::string & name);
-    virtual void _setRowCoeffs(int i, 
-                               int length,
-                               const int   * indices, 
-                               const Value   * values );
-    virtual void _setColCoeffs(int i, 
-                               int length,
-                               const int   * indices, 
-                               const Value   * values);
+    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
+    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     virtual void _setCoeff(int row, int col, Value value);
     virtual void _setColLowerBound(int i, Value value);

lemon/lp_skeleton.cc

@@ -59 +59 @@
   
   
-  void LpSkeleton::_setRowCoeffs(int, 
-                                 int,
-                                 int  const *, 
-                                 Value  const *)
-  {
+  void LpSkeleton::_setRowCoeffs(int, LpRowIterator, LpRowIterator) {
   }
   
-  void LpSkeleton::_setColCoeffs(int, 
-                                 int,
-                                 int  const *, 
-                                 Value  const *)
-  {
+  void LpSkeleton::_setColCoeffs(int, LpColIterator, LpColIterator) {
   }
 

lemon/lp_skeleton.h

@@ -44 +44 @@
     virtual void _eraseRow(int i);
     /// \e
-    virtual void _getColName(int col,       std::string & name);
+    virtual void _getColName(int col, std::string & name);
     /// \e
     virtual void _setColName(int col, const std::string & name);
 
     /// \e
-
-    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
-    ///
-    virtual void _setRowCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values );
+    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
     /// \e
-
-    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
-    ///
-    virtual void _setColCoeffs(int i, 
-                               int length,
-                               int  const * indices, 
-                               Value  const * values );
+    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     
     /// Set one element of the coefficient matrix