Changeset 1111:88ade201ffc6 in lemon-0.x for src/work/marci

Timestamp:

02/01/05 13:53:30 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

lower and upper bound handling functions for rows

Location:

src/work/marci/lp

Files:

• lp_solver_base.h (moved) (moved from src/work/marci/lp/lp_solver_wrapper_3.h) (17 diffs)
• lp_solver_wrapper_2.h (deleted)
• max_flow_expression.cc (modified) (4 diffs)

src/work/marci/lp/lp_solver_base.h

@@ -25 +25 @@
 #include <utility>
 
-//#include <sage_graph.h>
 //#include <lemon/list_graph.h>
-//#include <lemon/graph_wrapper.h>
 #include <lemon/invalid.h>
 #include <expression.h>
@@ -174 +172 @@
 
   /*! \e
-
-  \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
-  \todo LEKERDEZESEK!!!
-  \todo DOKSI!!!! Doxygen group!!!
-
-   */
+    \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
+    \todo LEKERDEZESEK!!!
+    \todo DOKSI!!!! Doxygen group!!!
+    The aim of this class is to give a general surface to different 
+    solvers, i.e. it makes possible to write algorithms using LP's, 
+    in which the solver can be changed to an other one easily.
+  */
   template <typename _Value>
   class LPSolverBase {
@@ -220 +219 @@
   protected:
     /// \e
+    virtual int _addCol() = 0;
+    /// \e
     virtual int _addRow() = 0;
     /// \e
-    virtual int _addCol() = 0;
+    virtual void _eraseCol(int i) = 0;
+    /// \e
+    virtual void _eraseRow(int i) = 0;
     /// \e
     virtual void _setRowCoeffs(int i, 
@@ -229 +232 @@
     virtual void _setColCoeffs(int i, 
                                const std::vector<std::pair<int, _Value> >& coeffs) = 0;
-    /// \e
-    virtual void _eraseCol(int i) = 0;
-    /// \e
-    virtual void _eraseRow(int i) = 0;
   public:
     /// \e
@@ -243 +242 @@
     virtual void _setColLowerBound(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) have to be given by an 
     /// extended number of type _Value, i.e. a finite number of type 
@@ -248 +252 @@
     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 
@@ -258 +257 @@
     virtual _Value _getColUpperBound(int i) = 0;
     /// \e
-    virtual void _setColBounds(int i, Bound bound, 
-                               _Value lo, _Value up) = 0; 
-    /// \e
-    virtual void _setRowBounds(int i, Bound bound, 
-                               _Value lo, _Value up) = 0; 
+    /// The lower bound of a linear expression (row) have to be given by an 
+    /// extended number of type _Value, i.e. a finite number of type 
+    /// _Value or -INF.
+    virtual void _setRowLowerBound(int i, _Value value) = 0;
+    /// \e
+    /// The lower bound of a linear expression (row) is an 
+    /// extended number of type _Value, i.e. a finite number of type 
+    /// _Value or -INF.
+    virtual _Value _getRowLowerBound(int i) = 0;
+    /// \e
+    /// The upper bound of a linear expression (row) have to be given by an 
+    /// extended number of type _Value, i.e. a finite number of type 
+    /// _Value or INF.
+    virtual void _setRowUpperBound(int i, _Value value) = 0;
+    /// \e
+    /// The upper bound of a linear expression (row) is an 
+    /// extended number of type _Value, i.e. a finite number of type 
+    /// _Value or INF.
+    virtual _Value _getRowUpperBound(int i) = 0;
     /// \e
     virtual void _setObjCoef(int i, _Value obj_coef) = 0;
@@ -271 +284 @@
 
   protected:
+    /// \e
     virtual _Value _getPrimal(int i) = 0;
 
@@ -276 +290 @@
 
   public:
+    /// \e
+    ColIt 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;
+      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
+        col_it=col_iter_map.push_back(i, VALID_CLASS);
+      }
+      return col_it;
+    }
     /// \e
     RowIt addRow() {
@@ -288 +315 @@
       }
       return row_it;
-    }
-    /// \e
-    ColIt 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;
-      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
-        col_it=col_iter_map.push_back(i, VALID_CLASS);
-      }
-      return col_it;
-    }
-    /// \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
@@ -349 +343 @@
     }
     /// \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 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);
-    }
-    /// \e
-    void setRowBounds(const RowIt& row_it, Bound bound, 
-                      _Value lo, _Value up) {
-      _setRowBounds(row_iter_map[row_it], bound, lo, up);
+    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
@@ -416 +436 @@
       }
     }
+
     //SOLVER FUNCTIONS
 
@@ -429 +450 @@
 
   public:
+
+    /// \e
     _Value getPrimal(const ColIt& col_it) {
       return _getPrimal(col_iter_map[col_it]);
@@ -467 +490 @@
 
 
-  /// \brief Wrappers for LP solvers
+  /// \brief Wrapper for GLPK solver
   /// 
-  /// This class implements a lemon wrapper for glpk.
-  /// Later other LP-solvers will be wrapped into lemon.
-  /// The aim of this class is to give a general surface to different 
-  /// solvers, i.e. it makes possible to write algorithms using LP's, 
-  /// in which the solver can be changed to an other one easily.
+  /// This class implements a lemon wrapper for GLPK.
   class LPGLPK : public LPSolverBase<double> {
   public:
@@ -595 +614 @@
           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:
@@ -670 +643 @@
       }
     }
+    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 _getColUpperBound(int i) {
       int b=lpx_get_col_type(lp, i);
@@ -685 +704 @@
       }
     }
-    virtual void _setColBounds(int i, Bound bound, 
-                               double lo, double up) {
-      switch (bound) {
-      case FREE:
-        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
-        break;
-      case LOWER:
-        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
-        break;
-      case UPPER:
-        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
-        break;
-      case DOUBLE:
-        lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
-        break;
-      case FIXED:
-        lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
-        break;
-      }
-    } 
-    virtual void _setRowBounds(int i, Bound bound, 
-                               double lo, double up) {
-      switch (bound) {
-      case FREE:
-        lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
-        break;
-      case LOWER:
-        lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
-        break;
-      case UPPER:
-        lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
-        break;
-      case DOUBLE:
-        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
-        break;
-      case FIXED:
-        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
-        break;
-      }
-    } 
-  protected:
+    virtual void _setRowLowerBound(int i, double lo) {
+      if (lo==INF) {
+        //FIXME error
+      }
+      int b=lpx_get_row_type(lp, i);
+      double up=lpx_get_row_ub(lp, i);  
+      if (lo==-INF) {
+        switch (b) {
+        case LPX_FR:
+        case LPX_LO:
+          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
+          break;
+        case LPX_UP:
+          break;
+        case LPX_DB:
+        case LPX_FX:
+          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+          break;
+        default: ;
+          //FIXME error
+        }
+      } else {
+        switch (b) {
+        case LPX_FR:
+        case LPX_LO:
+          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
+          break;
+        case LPX_UP:      
+        case LPX_DB:
+        case LPX_FX:
+          if (lo==up) 
+            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+          else 
+            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+          break;
+        default: ;
+          //FIXME error
+        }
+      }
+    }
+    virtual double _getRowLowerBound(int i) {
+      int b=lpx_get_row_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+        return -INF;
+      case LPX_LO:
+        return lpx_get_row_lb(lp, i);
+      case LPX_UP:
+        return -INF;
+      case LPX_DB:
+      case LPX_FX:
+        return lpx_get_row_lb(lp, i);
+      default: ;
+        //FIXME error
+        return 0.0;
+      }
+    }
+    virtual void _setRowUpperBound(int i, double up) {
+      if (up==-INF) {
+        //FIXME error
+      }
+      int b=lpx_get_row_type(lp, i);
+      double lo=lpx_get_row_lb(lp, i);
+      if (up==INF) {
+        switch (b) {
+        case LPX_FR:
+        case LPX_LO:
+          break;
+        case LPX_UP:
+          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
+          break;
+        case LPX_DB:
+        case LPX_FX:
+          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
+          break;
+        default: ;
+          //FIXME error
+        }
+      } else {
+        switch (b) {
+        case LPX_FR:
+          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+        case LPX_LO:
+          if (lo==up) 
+            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+          else
+            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+          break;
+        case LPX_UP:
+          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
+          break;
+        case LPX_DB:
+        case LPX_FX:
+          if (lo==up) 
+            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
+          else 
+            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
+          break;
+        default: ;
+          //FIXME error
+        }
+      }
+    }
+    virtual double _getRowUpperBound(int i) {
+      int b=lpx_get_row_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_row_ub(lp, i);
+      default: ;
+        //FIXME error
+        return 0.0;
+      }
+    }
     /// \e
     virtual double _getObjCoef(int i) { 

src/work/marci/lp/max_flow_expression.cc

@@ -7 +7 @@
 #include <lemon/dimacs.h>
 #include <lemon/time_measure.h>
-#include <lp_solver_wrapper_3.h>
+#include <lp_solver_base.h>
 
 using std::cout;
@@ -52 +52 @@
   PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
 
-  // capacity function
+  // nonnegativity of flow and capacity function
   for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
     ColIt col_it=lp.addCol();
@@ -59 +59 @@
     // 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_it, 0);
   }
   
@@ -73 +73 @@
       lp.setObjCoeffs(expr);      
     }
-    // flow conservation
+    // flow conservation constraints
     if ((n!=s) && (n!=t)) {
       RowIt row_it=lp.addRow();
       lp.setRowCoeffs(row_it, expr);
-      lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
+      lp.setRowLowerBound(row_it, 0.0);
+      lp.setRowUpperBound(row_it, 0.0);
     }
   }