Changeset 1144:1cfabf245433 in lemon-0.x for src/work/marci/lp

Timestamp:

02/10/05 19:53:30 (19 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

trying to add constraints of kind 1 <= x[2]+x[3] <= 4

Location:

src/work/marci/lp

Files:

• expression.h (modified) (2 diffs)
• lp_solver_base.h (modified) (14 diffs)
• max_flow_expression.cc (modified) (3 diffs)

src/work/marci/lp/expression.h

@@ -5 +5 @@
 #include <iostream>
 #include <map>
+#include <limits>
 
 namespace lemon {
@@ -120 +121 @@
     return os;
   }
+
+  template <typename _Col, typename _Value>
+  class LConstr {
+    //  protected:
+  public:
+    Expr<_Col, _Value> expr;
+    _Value lo;
+  public:
+    LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) : 
+      expr(_expr), lo(_lo) { }
+  };
+  
+  template <typename _Col, typename _Value>
+  LConstr<_Col, _Value> 
+  operator<=(_Value lo, const Expr<_Col, _Value>& expr) {
+    return LConstr<_Col, _Value>(expr, lo);
+  }
+
+  template <typename _Col, typename _Value>
+  class UConstr {
+    //  protected:
+  public:
+    Expr<_Col, _Value> expr;
+    _Value up;
+  public:
+    UConstr(const Expr<_Col, _Value>& _expr, _Value _up) : 
+      expr(_expr), up(_up) { }
+  };
+
+  template <typename _Col, typename _Value>
+  UConstr<_Col, _Value> 
+  operator<=(const Expr<_Col, _Value>& expr, _Value up) {
+    return UConstr<_Col, _Value>(expr, up);
+  }
+
+  template <typename _Col, typename _Value>
+  class Constr {
+    //  protected:
+  public:
+    Expr<_Col, _Value> expr;
+    _Value lo, up;
+  public:
+    Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) : 
+      expr(_expr), lo(_lo), up(_up) { }
+    Constr(const LConstr<_Col, _Value>& _lconstr) : 
+      expr(_lconstr.expr), 
+      lo(_lconstr.lo), 
+      up(std::numeric_limits<_Value>::infinity()) { }
+    Constr(const UConstr<_Col, _Value>& _uconstr) : 
+      expr(_uconstr.expr), 
+      lo(-std::numeric_limits<_Value>::infinity()), 
+      up(_uconstr.up) { }
+  };
+
+  template <typename _Col, typename _Value>
+  Constr<_Col, _Value> 
+  operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {
+    return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);
+  }
+
+  template <typename _Col, typename _Value>
+  Constr<_Col, _Value> 
+  operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {
+    return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);
+  }
+
+  template <typename _Col, typename _Value>
+  Constr<_Col, _Value> 
+  operator==(const Expr<_Col, _Value>& expr, _Value value) {
+    return Constr<_Col, _Value>(expr, value, value);
+  }
   
 } //namespace lemon

src/work/marci/lp/lp_solver_base.h

@@ -194 +194 @@
     typedef _Value Value;
     /// \e
-    typedef IterablePartition<int>::ClassIt RowIt;
-    /// \e
-    typedef IterablePartition<int>::ClassIt ColIt;
+    typedef IterablePartition<int>::ClassIt Row;
+    /// \e
+    typedef IterablePartition<int>::ClassIt Col;
   public:
     /// \e
@@ -203 +203 @@
     IterablePartition<int> col_iter_map;
     /// \e
-    std::vector<RowIt> int_row_map;
-    /// \e
-    std::vector<ColIt> int_col_map;
+    std::vector<Row> int_row_map;
+    /// \e
+    std::vector<Col> int_col_map;
     /// \e
     const int VALID_CLASS;
@@ -272 +272 @@
     /// \e
     virtual void printDualStatus(int i) = 0;
-    /// Returns the status of the slack variable assigned to row \c row_it.
-    virtual int getRowStat(const RowIt& row_it) = 0;
+    /// Returns the status of the slack variable assigned to row \c row.
+    virtual int getRowStat(const Row& row) = 0;
     /// \e
     virtual void printRowStatus(int i) = 0;
-    /// Returns the status of the variable assigned to column \c col_it.
-    virtual int getColStat(const ColIt& col_it) = 0;
+    /// Returns the status of the variable assigned to column \c col.
+    virtual int getColStat(const Col& col) = 0;
     /// \e
     virtual void printColStatus(int i) = 0;
@@ -376 +376 @@
 
     /// \e
-    ColIt addCol() {
+    Col addCol() {
       int i=_addCol();  
-      ColIt col_it;
-      col_iter_map.first(col_it, INVALID_CLASS);
-      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
-        col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
-        col_iter_map[col_it]=i;
+      Col col;
+      col_iter_map.first(col, INVALID_CLASS);
+      if (col_iter_map.valid(col)) { //van hasznalhato hely
+        col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
+        col_iter_map[col]=i;
       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
-        col_it=col_iter_map.push_back(i, VALID_CLASS);
-      }
-      int_col_map.push_back(col_it);
-      return col_it;
-    }
-    /// \e
-    RowIt addRow() {
+        col=col_iter_map.push_back(i, VALID_CLASS);
+      }
+      int_col_map.push_back(col);
+      return col;
+    }
+    /// \e
+    Row 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
-        row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
-        row_iter_map[row_it]=i;
+      Row row;
+      row_iter_map.first(row, INVALID_CLASS);
+      if (row_iter_map.valid(row)) { //van hasznalhato hely
+        row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
+        row_iter_map[row]=i;
       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
-        row_it=row_iter_map.push_back(i, VALID_CLASS);
-      }
-      int_row_map.push_back(row_it);
-      return row_it;
-    }
-    /// \e
-    void eraseCol(const ColIt& col_it) {
-      col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
+        row=row_iter_map.push_back(i, VALID_CLASS);
+      }
+      int_row_map.push_back(row);
+      return row;
+    }
+    /// \e
+    void eraseCol(const Col& col) {
+      col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
       int cols[2];
-      cols[1]=col_iter_map[col_it];
+      cols[1]=col_iter_map[col];
       _eraseCol(cols[1]);
-      col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
-      ColIt it;
+      col_iter_map[col]=0; //glpk specifikus, de kell ez??
+      Col it;
       for (col_iter_map.first(it, VALID_CLASS); 
            col_iter_map.valid(it); col_iter_map.next(it)) {
@@ -418 +418 @@
     }
     /// \e
-    void eraseRow(const RowIt& row_it) {
-      row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
+    void eraseRow(const Row& row) {
+      row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
       int rows[2];
-      rows[1]=row_iter_map[row_it];
+      rows[1]=row_iter_map[row];
       _eraseRow(rows[1]);
-      row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
-      RowIt it;
+      row_iter_map[row]=0; //glpk specifikus, de kell ez??
+      Row it;
       for (row_iter_map.first(it, VALID_CLASS); 
            row_iter_map.valid(it); row_iter_map.next(it)) {
@@ -432 +432 @@
     }
     /// \e
-    template <typename Begin, typename End>
-    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
-      std::vector<std::pair<int, double> > coeffs;
-      for ( ; begin!=end; ++begin) {
-        coeffs.push_back(std::
-                         make_pair(col_iter_map[begin->first], begin->second));
-      }
-      _setRowCoeffs(row_iter_map[row_it], coeffs);
-    }
-    /// \e
-    template <typename Begin, typename End>
-    void setColCoeffs(ColIt col_it, Begin begin, End end) {
-      std::vector<std::pair<int, double> > coeffs;
-      for ( ; begin!=end; ++begin) {
-        coeffs.push_back(std::
-                         make_pair(row_iter_map[begin->first], begin->second));
-      }
-      _setColCoeffs(col_iter_map[col_it], coeffs);
-    }
-    /// \e
-    void setColLowerBound(ColIt col_it, _Value lo) {
-      _setColLowerBound(col_iter_map[col_it], lo);
-    }
-    /// \e
-    _Value getColLowerBound(ColIt col_it) {
-      return _getColLowerBound(col_iter_map[col_it]);
-    }
-    /// \e
-    void setColUpperBound(ColIt col_it, _Value up) {
-      _setColUpperBound(col_iter_map[col_it], up);
-    }
-    /// \e
-    _Value getColUpperBound(ColIt col_it) {      
-      return _getColUpperBound(col_iter_map[col_it]);
-    }
-    /// \e
-    void setRowLowerBound(RowIt row_it, _Value lo) {
-      _setRowLowerBound(row_iter_map[row_it], lo);
-    }
-    /// \e
-    _Value getRowLowerBound(RowIt row_it) {
-      return _getRowLowerBound(row_iter_map[row_it]);
-    }
-    /// \e
-    void setRowUpperBound(RowIt row_it, _Value up) {
-      _setRowUpperBound(row_iter_map[row_it], up);
-    }
-    /// \e
-    _Value getRowUpperBound(RowIt row_it) {      
-      return _getRowUpperBound(row_iter_map[row_it]);
-    }
-    /// \e
-    void setObjCoef(const ColIt& col_it, _Value obj_coef) {
-      _setObjCoef(col_iter_map[col_it], obj_coef);
-    }
-    /// \e
-    _Value getObjCoef(const ColIt& col_it) {
-      return _getObjCoef(col_iter_map[col_it]);
+    void setColLowerBound(Col col, _Value lo) {
+      _setColLowerBound(col_iter_map[col], lo);
+    }
+    /// \e
+    _Value getColLowerBound(Col col) {
+      return _getColLowerBound(col_iter_map[col]);
+    }
+    /// \e
+    void setColUpperBound(Col col, _Value up) {
+      _setColUpperBound(col_iter_map[col], up);
+    }
+    /// \e
+    _Value getColUpperBound(Col col) {      
+      return _getColUpperBound(col_iter_map[col]);
+    }
+    /// \e
+    void setRowLowerBound(Row row, _Value lo) {
+      _setRowLowerBound(row_iter_map[row], lo);
+    }
+    /// \e
+    _Value getRowLowerBound(Row row) {
+      return _getRowLowerBound(row_iter_map[row]);
+    }
+    /// \e
+    void setRowUpperBound(Row row, _Value up) {
+      _setRowUpperBound(row_iter_map[row], up);
+    }
+    /// \e
+    _Value getRowUpperBound(Row row) {      
+      return _getRowUpperBound(row_iter_map[row]);
+    }
+    /// \e
+    void setObjCoef(const Col& col, _Value obj_coef) {
+      _setObjCoef(col_iter_map[col], obj_coef);
+    }
+    /// \e
+    _Value getObjCoef(const Col& col) {
+      return _getObjCoef(col_iter_map[col]);
     }
 
@@ -495 +475 @@
 
     /// \e
-    _Value getPrimal(const ColIt& col_it) {
-      return _getPrimal(col_iter_map[col_it]);
+    _Value getPrimal(const Col& col) {
+      return _getPrimal(col_iter_map[col]);
     }    
 
@@ -509 +489 @@
 
     /// \e
-    typedef Expr<ColIt, _Value> Expression;
-    /// \e
-    typedef Expr<RowIt, _Value> DualExpression;
+    typedef Expr<Col, _Value> Expression;
+    /// \e
+    typedef Expr<Row, _Value> DualExpression;
+    /// \e
+    typedef Constr<Col, _Value> Constraint;
 
     //MATRIX MANIPULATING FUNCTIONS
 
     /// \e
-    void setRowCoeffs(RowIt row_it, const Expression& expr) {
+    void setRowCoeffs(Row row, const Expression& expr) {
       std::vector<std::pair<int, _Value> > row_coeffs;
       for(typename Expression::Data::const_iterator i=expr.data.begin(); 
@@ -523 +505 @@
                              (col_iter_map[(*i).first], (*i).second));
       }
-      _setRowCoeffs(row_iter_map[row_it], row_coeffs);
+      _setRowCoeffs(row_iter_map[row], row_coeffs);
+    }
+    /// \e 
+    void setRow(Row row, const Constraint& constr) {
+      setRowCoeffs(row, constr.expr);
+      setRowLowerBound(row, constr.lo);
+      setRowUpperBound(row, constr.up);
+    }
+    /// \e 
+    Row addRow(const Constraint& constr) {
+      Row row=addRow();
+      setRowCoeffs(row, constr.expr);
+      setRowLowerBound(row, constr.lo);
+      setRowUpperBound(row, constr.up);
+      return row;
     }
     /// \e
     /// This routine modifies \c expr by only adding to it.
-    void getRowCoeffs(RowIt row_it, Expression& expr) {
+    void getRowCoeffs(Row row, Expression& expr) {
       std::vector<std::pair<int, _Value> > row_coeffs;
-      _getRowCoeffs(row_iter_map[row_it], row_coeffs);
+      _getRowCoeffs(row_iter_map[row], row_coeffs);
       for(typename std::vector<std::pair<int, _Value> >::const_iterator 
             i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
@@ -536 +532 @@
     }
     /// \e
-    void setColCoeffs(ColIt col_it, const DualExpression& expr) {
+    void setColCoeffs(Col col, const DualExpression& expr) {
       std::vector<std::pair<int, _Value> > col_coeffs;
       for(typename DualExpression::Data::const_iterator i=expr.data.begin(); 
@@ -543 +539 @@
                              (row_iter_map[(*i).first], (*i).second));
       }
-      _setColCoeffs(col_iter_map[col_it], col_coeffs);
+      _setColCoeffs(col_iter_map[col], col_coeffs);
     }
     /// \e
     /// This routine modifies \c expr by only adding to it.
-    void getColCoeffs(ColIt col_it, DualExpression& expr) {
+    void getColCoeffs(Col col, DualExpression& expr) {
       std::vector<std::pair<int, _Value> > col_coeffs;
-      _getColCoeffs(col_iter_map[col_it], col_coeffs);
+      _getColCoeffs(col_iter_map[col], col_coeffs);
       for(typename std::vector<std::pair<int, _Value> >::const_iterator 
             i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
@@ -590 +586 @@
     LPGLPK() : Parent(), 
                         lp(lpx_create_prob()) {
-      int_row_map.push_back(RowIt());
-      int_col_map.push_back(ColIt());
+      int_row_map.push_back(Row());
+      int_col_map.push_back(Col());
       lpx_set_int_parm(lp, LPX_K_DUAL, 1);
     }
@@ -992 +988 @@
       }
     }
-    /// Returns the status of the slack variable assigned to row \c row_it.
-    int getRowStat(const RowIt& row_it) { 
-      return lpx_get_row_stat(lp, row_iter_map[row_it]); 
+    /// 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
@@ -1006 +1002 @@
       }
     }
-    /// Returns the status of the variable assigned to column \c col_it.
-    int getColStat(const ColIt& col_it) { 
-      return lpx_get_col_stat(lp, col_iter_map[col_it]); 
+    /// 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

src/work/marci/lp/max_flow_expression.cc

@@ -47 +47 @@
   LPSolver lp;
   lp.setMaximize();
-  typedef LPSolver::ColIt ColIt;
-  typedef LPSolver::RowIt RowIt;
-  typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
-  typedef Graph::NodeMap<RowIt> NodeIndexMap;
+  typedef LPSolver::Col Col;
+  typedef LPSolver::Row Row;
+  typedef Graph::EdgeMap<Col> EdgeIndexMap;
+  typedef Graph::NodeMap<Row> NodeIndexMap;
   EdgeIndexMap edge_index_map(g);
   NodeIndexMap node_index_map(g);
@@ -57 +57 @@
   // nonnegativity of flow and capacity function
   for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
-    ColIt col_it=lp.addCol();
-    edge_index_map.set(e, col_it);
+    Col col=lp.addCol();
+    edge_index_map.set(e, col);
     // interesting property in GLPK:
     // if you change the order of the following two lines, the 
     // two runs of GLPK are extremely different
-      lp.setColLowerBound(col_it, 0);
-      lp.setColUpperBound(col_it, cap[e]);
+      lp.setColLowerBound(col, 0);
+      lp.setColUpperBound(col, cap[e]);
   }
   
@@ -78 +78 @@
     // flow conservation constraints
     if ((n!=s) && (n!=t)) {
-      RowIt row_it=lp.addRow();
-      node_index_map.set(n, row_it);
-      lp.setRowCoeffs(row_it, expr);
-      lp.setRowLowerBound(row_it, 0.0);
-      lp.setRowUpperBound(row_it, 0.0);
-//       cout << expr << endl;
-//       {
-//      LPSolver::Expression expr;
-//      lp.getRowCoeffs(node_index_map[n], expr);       
-//      cout << expr << endl;
-//       }
+      node_index_map.set(n, lp.addRow(expr == 0.0));
     }
   }
   lp.solveSimplex();
-//   cout << "num of nodes: " << countNodes(g) << endl;
-//   cout << "num of edges: " << countEdges(g) << endl;
-//   cout << "num of rows: " << lp.rowNum() << endl;
-//   cout << "num of rows: " << lp.int_row_map.size() << endl;
-//   for (int i=0; i<lp.int_row_map.size(); ++i) {
-//     cout << lp.int_row_map[i] << " " << endl;
-//   }
-//   cout << "num of columns: " << lp.colNum() << endl;
-//   cout << "num of columns: " << lp.int_col_map.size() << endl;
-//   for (int i=0; i<lp.int_col_map.size(); ++i) {
-//     cout << lp.int_col_map[i] << " " << endl;
-//   }
   cout << "elapsed time: " << ts << endl;
-//   Graph::NodeIt n(g);
-//   ++n;
-//   for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
-//     cout << edge_index_map[e] << endl;
-//   }
-//   for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
-//     cout << edge_index_map[e] << endl;
-//   }
-//   LPSolver::DualExpression expr;
-//   lp.getRowCoeffs(node_index_map[n], expr);
-//   cout << expr << endl;
 }