Changeset 1110:ba28dfbea5f2 in lemon-0.x

Timestamp:

01/31/05 18:00:12 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

new functions for changing lower and upper bounds of variables

Location:

src/work/marci/lp

Files:

• lp_solver_wrapper_3.h (modified) (5 diffs)
• max_flow_expression.cc (modified) (3 diffs)

src/work/marci/lp/lp_solver_wrapper_3.h

@@ -238 +238 @@
   protected:
     /// \e
+    /// The lower bound of a variable (column) have to be given by an 
+    /// extended number of type _Value, i.e. a finite number of type 
+    /// _Value or -INF.
+    virtual void _setColLowerBound(int i, _Value value) = 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 
+    /// _Value or INF.
+    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 
+    /// _Value or INF.
+    virtual _Value _getColUpperBound(int i) = 0;
+    /// \e
     virtual void _setColBounds(int i, Bound bound, 
                                _Value lo, _Value up) = 0; 
@@ -258 +278 @@
     /// \e
     RowIt addRow() {
-      int i=_addRow(); 
+      int i=_addRow();
       RowIt row_it;
       row_iter_map.first(row_it, INVALID_CLASS);
@@ -329 +349 @@
     }
     /// \e
+    void setColLowerBound(ColIt col_it, _Value lo) {
+      _setColLowerBound(col_iter_map[col_it], lo);
+    }
+    /// \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) {
@@ -473 +509 @@
     /// \e
     int _addCol() { 
-      return lpx_add_cols(lp, 1);
+      int i=lpx_add_cols(lp, 1);
+      _setColLowerBound(i, -INF);
+      _setColUpperBound(i, INF);
+      return i;
     }
     /// \e
     int _addRow() { 
-      return lpx_add_rows(lp, 1);
+      int i=lpx_add_rows(lp, 1);
+      return i;
     }
     /// \e
@@ -527 +567 @@
       lpx_del_rows(lp, 1, rows);
     }
+    virtual void _setColLowerBound(int i, double lo) {
+      if (lo==INF) {
+        //FIXME error
+      }
+      int b=lpx_get_col_type(lp, i);
+      double up=lpx_get_col_ub(lp, i);  
+      if (lo==-INF) {
+        switch (b) {
+        case LPX_FR:
+        case LPX_LO:
+          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
+          break;
+        case LPX_UP:
+          break;
+        case LPX_DB:
+        case LPX_FX:
+          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
+          break;
+        default: ;
+          //FIXME error
+        }
+      } else {
+        switch (b) {
+        case LPX_FR:
+        case LPX_LO:
+          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
+          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:
+          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 _getColLowerBound(int i) {
+      int b=lpx_get_col_type(lp, i);
+      switch (b) {
+      case LPX_FR:
+        return -INF;
+      case LPX_LO:
+        return lpx_get_col_lb(lp, i);
+      case LPX_UP:
+        return -INF;
+      case LPX_DB:
+      case LPX_FX:
+        return lpx_get_col_lb(lp, i);
+      default: ;
+        //FIXME error
+        return 0.0;
+      }
+    }
+    virtual double _getColUpperBound(int i) {
+      int b=lpx_get_col_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_col_ub(lp, i);
+      default: ;
+        //FIXME error
+        return 0.0;
+      }
+    }
     virtual void _setColBounds(int i, Bound bound, 
                                double lo, double up) {

src/work/marci/lp/max_flow_expression.cc

@@ -50 +50 @@
   typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
   EdgeIndexMap edge_index_map(g);
-  PrimalMap<Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
+  PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
 
   // capacity function
@@ -56 +56 @@
     ColIt col_it=lp.addCol();
     edge_index_map.set(e, col_it);
-    if (cap[e]==0)
-      lp.setColBounds(col_it, LPSolver::FIXED, 0, cap[e]);
-    else 
-      lp.setColBounds(col_it, LPSolver::DOUBLE, 0, cap[e]);
+    // interesting property in GLPK:
+    // if you change the order of the following two lines, the 
+    // two runs of GLPK are extremely different
+      lp.setColUpperBound(col_it, cap[e]);
+      lp.setColLowerBound(col_it, 0);
   }
   
@@ -80 +81 @@
   }
   lp.solveSimplex();
-  //std::cout << lp.colNum() << std::endl;
-  //std::cout << lp.rowNum() << std::endl;
-  //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
-  for (Graph::EdgeIt e(g); e!=INVALID; ++e) 
-    flow.set(e, lp_flow[e]);
+  cout << "elapsed time: " << ts << endl;
 }