Changeset 2364:3a5e67bd42d2 in lemon-0.x for lemon/lp_utils.h

Timestamp:

02/15/07 20:15:14 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Lp row and col getter function
lp section reader and writer for lemon IO

File:

• lemon/lp_utils.h (modified) (6 diffs)

lemon/lp_utils.h

@@ -69 +69 @@
   private:
 
+    enum SubSection {
+      CONSTRAINTS, BOUNDS, OBJECTIVE
+    };
+
     enum Relation {
       LE, EQ, GE
     };
 
-    std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
+    std::istream& readConstraint(std::istream& is) {
+      LpSolverBase::Constr c;
       char x;
       LpSolverBase::Expr e1, e2;
@@ -83 +88 @@
       is >> std::ws;
       readExpression(is, e2);
+      is >> std::ws;
       if (!is.get(x)) {
         if (op1 == LE) {
+          if (e1.size() == 0) {
+            c = e2 >= e1;
+          } else {
+            c = e1 <= e2;
+          }
           c = e1 <= e2;
         } else if (op1 == GE) {
-          c = e1 >= e2;
-        } else {
-          c = e1 == e2;
+          if (e1.size() == 0) {
+            c = e2 <= e1;
+          } else {
+            c = e1 >= e2;
+          }
+        } else {
+          if (e1.size() == 0) {
+            c = e2 == e1;
+          } else {
+            c = e1 == e2;
+          }
         }
       } else {
@@ -109 +128 @@
           c = e1.constComp() >= e2 >= e3.constComp();
         }
-      }
+        is >> std::ws;
+        if (is.get(x)) {
+          throw DataFormatError("Wrong variable bounds format");
+        }
+      }
+      lp.addRow(c);
+      return is;
+    }
+
+    std::istream& readObjective(std::istream& is) {
+      is >> std::ws;
+      std::string sense;
+      is >> sense;
+      if (sense != "min" && sense != "max") {
+        throw DataFormatError("Wrong objective function format");
+      }
+      LpSolverBase::Expr expr;
+      is >> std::ws;
+      readExpression(is, expr);
+      lp.setObj(expr);
+      if (sense == "min") {
+        lp.min();
+      } else {
+        lp.max();
+      }
+      return is;
+    }
+
+    std::istream& readBounds(std::istream& is) {
+      LpSolverBase::Col c;
+      char x;
+      is >> std::ws;
+      if (!is.get(x)) {
+        throw DataFormatError("Wrong variable bounds format");
+      }
+      if (varFirstChar(x)) {
+        is.putback(x);
+        readCol(is, c);
+        is >> std::ws;
+        Relation op1;
+        readRelation(is, op1);
+        double v;
+        readNum(is, v);
+        if (op1 == EQ) {
+          lp.colLowerBound(c, v);
+          lp.colUpperBound(c, v);
+        } else if (op1 == LE) {
+          lp.colUpperBound(c, v);
+        } else {
+          lp.colLowerBound(c, v);
+        }
+        is >> std::ws;
+        if (is.get(x)) {
+          throw DataFormatError("Wrong variable bounds format");
+        }
+      } else {
+        is.putback(x);
+        double v;
+        readNum(is, v);
+        is >> std::ws;
+        Relation op1;
+        readRelation(is, op1);
+        is >> std::ws;
+        readCol(is, c);
+        is >> std::ws;
+        if (is.get(x)) {
+          is.putback(x);
+          is >> std::ws;
+          Relation op2;
+          readRelation(is, op2);
+          double w;
+          is >> std::ws;
+          readNum(is, w);
+          if (op2 != op1 || op1 == EQ) {
+            throw DataFormatError("Wrong range format");
+          }
+          if (op1 == LE) {
+            lp.colLowerBound(c, v);
+            lp.colUpperBound(c, w);
+          } else {
+            lp.colLowerBound(c, w);
+            lp.colUpperBound(c, v);
+          }
+          if (is.get(x)) {
+            throw DataFormatError("Wrong variable bounds format");
+          }
+        } else {
+          if (op1 == EQ) {
+            lp.colLowerBound(c, v);
+            lp.colUpperBound(c, v);
+          } else if (op1 == LE) {
+            lp.colLowerBound(c, v);
+          } else {
+            lp.colUpperBound(c, v);
+          }
+        }
+      }
+      return is;
     }
 
@@ -278 +394 @@
     static bool varChar(char c) {
       return (c >= '0' && c <= '9') || 
-        (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
-    }
-
-
-    void addConstraint(const LpSolverBase::Constr& constr) {
-      if (constr.expr().size() != 1) {
-        lp.addRow(constr);
-      } else {
-        Lp::Expr e = constr.expr();
-        LpSolverBase::Col col = e.begin()->first;
-        double coeff = e.begin()->second;
-        double lb = LpSolverBase::NaN;
-        double ub = LpSolverBase::NaN;
-        if (coeff > 0) {
-          if (constr.upperBounded()) {
-            lb = (constr.lowerBound() - e.constComp()) / coeff;
-          }
-          if (constr.lowerBounded()) {
-            ub = (constr.upperBound() - e.constComp()) / coeff;
-          }
-        } else if (coeff < 0) {
-          if (constr.upperBounded()) {
-            lb = (constr.upperBound() - e.constComp()) / coeff;
-          }
-          if (constr.lowerBounded()) {
-            ub = (constr.lowerBound() - e.constComp()) / coeff;
-          }
-        } else {
-          lb = -LpSolverBase::INF;
-          ub = LpSolverBase::INF;
-        }
-        lp.colLowerBound(col, lb);
-        lp.colUpperBound(col, ub);
-      }
+        (c >= 'a' && c <= 'z') || 
+        (c >= 'A' && c <= 'Z') ||
+        c == '[' || c == ']';
     }
     
@@ -321 +406 @@
     virtual void read(std::istream& is) {
       std::string line;
+      SubSection sub = CONSTRAINTS;
       while (getline(is, line)) {
         std::istringstream ls(line);
-        std::string sense;
-        ls >> sense;
-        if (sense == "min" || sense == "max") {
-          LpSolverBase::Expr expr;
-          ls >> std::ws;
-          readExpression(ls, expr);
-          lp.setObj(expr);
-          if (sense == "min") {
-            lp.min();
-          } else {
-            lp.max();
-          }
+        std::string type;
+        ls >> type;
+        if (type == "constraints") {
+          sub = CONSTRAINTS;
+        } else if (type == "bounds") {
+          sub = BOUNDS;
+        } else if (type == "objective") {
+          sub = OBJECTIVE;
         } else {
           ls.str(line);
-          LpSolverBase::Constr constr;
-          ls >> std::ws;
-          readConstraint(ls, constr);
-          addConstraint(constr);
+          switch (sub) {
+          case CONSTRAINTS:
+            readConstraint(ls);
+            break;
+          case BOUNDS:
+            readBounds(ls);
+            break;
+          case OBJECTIVE:
+            readObjective(ls);
+            break;
+          }
         }        
       }
@@ -361 +450 @@
 
 
-//   class LpWriter : public LemonWriter::SectionWriter {
-//     typedef LemonWriter::SectionWriter Parent;
-//   public:
-
-
-//     /// \brief Constructor.
-//     ///
-//     /// Constructor for LpWriter. It creates the LpWriter and attach
-//     /// it into the given LemonWriter. The lp writer will add
-//     /// variables, constraints and objective function to the
-//     /// given lp solver.
-//     LpWriter(LemonWriter& _writer, LpSolverBase& _lp, 
-//              const std::string& _name = std::string())
-//       : Parent(_writer), lp(_lp), name(_name) {} 
-
-
-//     /// \brief Destructor.
-//     ///
-//     /// Destructor for NodeSetWriter.
-//     virtual ~LpWriter() {}
-
-//   private:
-//     LpWriter(const LpWriter&);
-//     void operator=(const LpWriter&);
+  class LpWriter : public LemonWriter::SectionWriter {
+    typedef LemonWriter::SectionWriter Parent;
+  public:
+
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for LpWriter. It creates the LpWriter and attach
+    /// it into the given LemonWriter. The lp writer will add
+    /// variables, constraints and objective function to the
+    /// given lp solver.
+    LpWriter(LemonWriter& _writer, LpSolverBase& _lp, 
+             const std::string& _name = std::string())
+      : Parent(_writer), lp(_lp), name(_name) {} 
+
+
+    /// \brief Destructor.
+    ///
+    /// Destructor for NodeSetWriter.
+    virtual ~LpWriter() {}
+
+  private:
+    LpWriter(const LpWriter&);
+    void operator=(const LpWriter&);
   
-//   protected:
-
-//     /// \brief Gives back true when the SectionWriter can process 
-//     /// the section with the given header line.
-//     ///
-//     /// It gives back the header line of the \c \@lp section.
-//     virtual std::string header() {
-//       std::ostringstream ls(line);
-//       ls << "@lp " << name;
-//       return ls.str();
-//     }
-
-//   private:
-
-//     std::ostream& writeConstraint(std::ostream& is, LpSolverBase::Constr& c) {
-//       char x;
-
+  protected:
+
+    /// \brief Gives back true when the SectionWriter can process 
+    /// the section with the given header line.
+    ///
+    /// It gives back the header line of the \c \@lp section.
+    virtual std::string header() {
+      std::ostringstream ls;
+      ls << "@lp " << name;
+      return ls.str();
+    }
+
+  private:
+
+    void createCols() {
+      int num = 1;
+
+      std::map<std::string, LpSolverBase::Col> inverse;
+
+      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
+        std::string name = lp.colName(it);
+        if (!name.empty() && inverse.find(name) == inverse.end()) {
+          cols.insert(std::make_pair(it, name));
+          inverse.insert(std::make_pair(name, it));
+        } else {
+          std::ostringstream ls;
+          ls << "var" << num;
+          ++num;
+          cols.insert(std::make_pair(it, ls.str()));
+          inverse.insert(std::make_pair(ls.str(), it));
+        }
+      }
+    }
+    
+    void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
+      bool first = true;
+      for (LpSolverBase::Expr::const_iterator jt = e.begin(); 
+           jt != e.end(); ++jt) {
+        if (jt->second < 0.0) {
+          os << "- ";
+          if (jt->second != -1.0) {
+            os << -jt->second << " * ";
+          }
+        } else if (jt->second > 0.0) {
+          if (!first) {
+            os << "+ ";
+          }
+          if (jt->second != 1.0) {
+            os << jt->second << " * ";
+          }          
+        }
+        first = false;
+        os << cols[jt->first] << " ";
+      }
+      if (e.constComp() < 0.0) {
+        os << "- " << -e.constComp() << " ";
+      } else if (e.constComp() > 0.0) {
+        if (!first) {
+          os << "+ ";
+        }
+        os << e.constComp() << " ";
+      } 
+    }
+
+  protected:
+
+    /// \brief Writer function of the section.
+    ///
+    /// It writes the content of the section.
+    virtual void write(std::ostream& os) {
+      createCols();
+
+      os << "constraints" << std::endl;
       
-//       LpSolverBase::Expr e1, e2;
-//       Relation op1;
-//       is >> std::ws;
-//       writexpression(is, e1);
-//       is >> std::ws;
-//       writeRelation(is, op1);
-//       is >> std::ws;
-//       writexpression(is, e2);
-//       if (!is.get(x)) {
-//         if (op1 == LE) {
-//           c = e1 <= e2;
-//         } else if (op1 == GE) {
-//           c = e1 >= e2;
-//         } else {
-//           c = e1 == e2;
-//         }
-//       } else {
-//         is.putback(x);
-//         LpSolverBase::Expr e3;
-//         Relation op2;
-//         writeRelation(is, op2);
-//         is >> std::ws;
-//         writexpression(is, e3);
-//         if (!e1.empty() || !e3.empty()) {
-//           throw DataFormatError("Wrong range format");
-//         }
-//         if (op2 != op1 || op1 == EQ) {
-//           throw DataFormatError("Wrong range format");
-//         }
-//         if (op1 == LE) {
-//           c = e1.constComp() <= e2 <= e3.constComp();
-//         } else {
-//           c = e1.constComp() >= e2 >= e3.constComp();
-//         }
-//       }
-//     }
-
-//     std::ostream& writexpression(std::ostream& is, LpSolverBase::Expr& e) {
-//       LpSolverBase::Col c;
-//       double d;
-//       char x;
-//       writelement(is, c, d);
-//       if (c != INVALID) {
-//         e += d * c;
-//       } else {
-//         e += d;
-//       }
-//       is >> std::ws;
-//       while (is.get(x) && (x == '+' || x == '-')) {
-//         is >> std::ws;
-//         writelement(is, c, d);
-//         if (c != INVALID) {
-//           e += (x == '+' ? d : -d) * c;
-//         } else {
-//           e += (x == '+' ? d : -d);
-//         }
-//         is >> std::ws;
-//       }
-//       if (!is) {
-//         is.clear();
-//       } else {
-//         is.putback(x);
-//       }
-//       return is;
-//     }
-
-//     std::ostream& writelement(std::ostream& is, 
-//                               LpSolverBase::Col& c, double& d) { 
-//       d = 1.0;
-//       c = INVALID;
-//       char x, y;
-//       if (!is.get(x)) throw DataFormatError("Cannot find lp element");
-//       if (x == '+' || x == '-') {
-//         is >> std::ws;
-//         d *= x == '-' ? -1 : 1;
-//         while (is.get(x) && (x == '+' || x == '-')) {
-//           d *= x == '-' ? -1 : 1;
-//           is >> std::ws;
-//         }
-//         if (!is) throw DataFormatError("Cannot find lp element");
-//       }
-//       if (numFirstChar(x)) {
-//         is.putback(x);
-//         double e;
-//         writeNum(is, e);
-//         d *= e;
-//       } else if (varFirstChar(x)) {
-//         is.putback(x);
-//         LpSolverBase::Col f;
-//         writeCol(is, f);
-//         c = f;
-//       } else {
-//         throw DataFormatError("Invalid expression format");          
-//       }
-//       is >> std::ws;
-//       while (is.get(y) && (y == '*' || y == '/')) {
-//         is >> std::ws;
-//         if (!is.get(x)) throw DataFormatError("Cannot find lp element");
-//         if (x == '+' || x == '-') {
-//           is >> std::ws;
-//           d *= x == '-' ? -1 : 1;
-//           while (is.get(x) && (x == '+' || x == '-')) {
-//             d *= x == '-' ? -1 : 1;
-//             is >> std::ws;
-//           }
-//           if (!is) throw DataFormatError("Cannot find lp element");
-//         }
-//         if (numFirstChar(x)) {
-//           is.putback(x);
-//           double e;
-//           writeNum(is, e);
-//           if (y == '*') {
-//             d *= e;
-//           } else {
-//             d /= e;
-//           }
-//         } else if (varFirstChar(x)) {
-//           is.putback(x);
-//           LpSolverBase::Col f;
-//           writeCol(is, f);
-//           if (y == '*') {
-//             if (c == INVALID) {
-//               c = f;
-//             } else {
-//               throw DataFormatError("Quadratic element in expression");
-//             }
-//           } else {
-//             throw DataFormatError("Division by variable");
-//           }
-//         } else {
-//           throw DataFormatError("Invalid expression format");          
-//         }
-//         is >> std::ws;
-//       }
-//       if (!is) {
-//         is.clear();
-//       } else {
-//         is.putback(y);
-//       }
-//       return is;
-//     }
-
-//     std::ostream& writeCol(std::ostream& is, LpSolverBase::Col& c) {
-//       char x;
-//       std::string var;
-//       while (is.get(x) && varChar(x)) {
-//         var += x;
-//       }
-//       if (!is) {
-//         is.clear();
-//       } else {
-//         is.putback(x);
-//       }
-//       ColMap::const_iterator it = cols.find(var);
-//       if (cols.find(var) != cols.end()) {
-//         c = it->second;
-//       } else {
-//         c = lp.addCol();
-//         cols.insert(std::make_pair(var, c));
-//         lp.colName(c, var);
-//       }
-//       return is;
-//     }
-
-//     std::ostream& writeNum(std::ostream& is, double& d) {
-//       is >> d;
-//       if (!is) throw DataFormatError("Wrong number format");
-//       return is;
-//     }
-
-//     std::ostream& writeRelation(std::ostream& is, Relation& op) {
-//       char x, y;
-//       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
-//         throw DataFormatError("Wrong relation operator");
-//       }
-//       if (!is.get(y) || y != '=') {
-//         throw DataFormatError("Wrong relation operator");
-//       }
-//       switch (x) {
-//       case '<': op = LE; 
-//         break;
-//       case '=': op = EQ; 
-//         break;
-//       case '>': op = GE; 
-//         break;
-//       }
-//       return is;
-//     }
-
-//     static bool relationFirstChar(char c) {
-//       return c == '<' || c == '=' || c == '>';
-//     }
-
-//     static bool varFirstChar(char c) {
-//       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
-//     }
-
-//     static bool numFirstChar(char c) {
-//       return (c >= '0' && c <= '9') || c == '.';
-//     }
-
-//     static bool varChar(char c) {
-//       return (c >= '0' && c <= '9') || 
-//         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
-//     }
-
-
-//     void addConstraint(const LpSolverBase::Constr& constr) {
-//       if (constr.expr().size() != 1) {
-//         lp.addRow(constr);
-//       } else {
-//         Lp::Expr e = constr.expr();
-//         LpSolverBase::Col col = e.begin()->first;
-//         double coeff = e.begin()->second;
-//         double lb = LpSolverBase::NaN;
-//         double ub = LpSolverBase::NaN;
-//         if (coeff > 0) {
-//           if (constr.upperBounded()) {
-//             lb = (constr.lowerBound() - e.constComp()) / coeff;
-//           }
-//           if (constr.lowerBounded()) {
-//             ub = (constr.upperBound() - e.constComp()) / coeff;
-//           }
-//         } else if (coeff < 0) {
-//           if (constr.upperBounded()) {
-//             lb = (constr.upperBound() - e.constComp()) / coeff;
-//           }
-//           if (constr.lowerBounded()) {
-//             ub = (constr.lowerBound() - e.constComp()) / coeff;
-//           }
-//         } else {
-//           lb = -LpSolverBase::INF;
-//           ub = LpSolverBase::INF;
-//         }
-//         lp.colLowerBound(col, lb);
-//         lp.colUpperBound(col, ub);
-//       }
-//     }
-    
-//   protected:
-
-//     /// \brief Writer function of the section.
-//     ///
-//     /// It writes the content of the section.
-//     virtual void write(std::ostream& is) {
-//       std::string line;
-//       std::map<std::string, LpSolverBase::Col> vars;
-//       while (getline(is, line)) {
-//         std::istringstream ls(line);
-//         std::string sense;
-//         ls >> sense;
-//         if (sense == "min" || sense == "max") {
-//           LpSolverBase::Expr expr;
-//           ls >> std::ws;
-//           writeExpression(ls, expr);
-//           lp.setObj(expr);
-//           if (sense == "min") {
-//             lp.min();
-//           } else {
-//             lp.max();
-//           }
-//         } else {
-//           ls.str(line);
-//           LpSolverBase::Constr constr;
-//           ls >> std::ws;
-//           writeConstraint(ls, constr);
-//           addConstraint(constr);
-//         }        
-//       }
-//     }
+      for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
+        double lower, upper;
+        lp.getRowBounds(it, lower, upper);
+        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
+          continue;
+        os << "   ";
+        
+        if (lower != upper) {
+          if (lower != -LpSolverBase::INF) {
+            os << lower << " <= ";
+          }
+          
+          writeExpression(os, lp.row(it));
+          
+          if (upper != LpSolverBase::INF) {
+            os << "<= " << upper << " ";
+          }
+        } else {
+
+          writeExpression(os, lp.row(it));
+          os << "== " << upper << " ";
+          
+        }
+
+        os << std::endl;
+      }
+
+      os << "bounds" << std::endl;
       
-//     virtual void missing() {
-//       ErrorMessage msg;
-//       msg << "Lp section not found in file: @lp " << name;
-//       throw IoParameterError(msg.message());
-//     }
-
-//   private:
-
-//     typedef std::map<std::string, LpSolverBase::Col> ColMap;
+      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
+        double lower = lp.colLowerBound(it);
+        double upper = lp.colUpperBound(it);
+        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) 
+          continue;
+        os << "   ";
+
+        if (lower != upper) {
+          if (lower != -LpSolverBase::INF) {
+            os << lower << " <= ";
+          }
+          
+          os << cols[it] << " ";
+          
+          if (upper != LpSolverBase::INF) {
+            os << "<= " << upper << " ";
+          }
+        } else {
+          os << cols[it] << " == " << upper << " ";
+        }
+        os << std::endl;
+      }
+
+      os << "objective" << std::endl;
+      os << "   ";
+      if (lp.is_min()) {
+        os << "min ";
+      } else {
+        os << "max ";
+      }
+      writeExpression(os, lp.obj());
+      os << std::endl;
+    }
       
-//     LpSolverBase& lp;
-//     std::string name;
-//     ColMap cols;
-//   };
+
+  private:
+
+    typedef std::map<LpSolverBase::Col, std::string> ColMap;
+      
+    LpSolverBase& lp;
+    std::string name;
+    ColMap cols;
+  };
 
 }