source: lemon-0.x/lemon/lp_utils.h @ 2363:2aabce558574

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_LP_UTILS_H
#define LEMON_LP_UTILS_H

#include <lemon/lp_base.h>

#include <lemon/lemon_reader.h>
#include <lemon/lemon_writer.h>

namespace lemon {

  class LpReader : public LemonReader::SectionReader {
    typedef LemonReader::SectionReader Parent;
  public:


    /// \brief Constructor.
    ///
    /// Constructor for LpReader. It creates the LpReader and attach
    /// it into the given LemonReader. The lp reader will add
    /// variables, constraints and objective function to the
    /// given lp solver.
    LpReader(LemonReader& _reader, LpSolverBase& _lp, 
             const std::string& _name = std::string())
      : Parent(_reader), lp(_lp), name(_name) {} 


    /// \brief Destructor.
    ///
    /// Destructor for NodeSetReader.
    virtual ~LpReader() {}

  private:
    LpReader(const LpReader&);
    void operator=(const LpReader&);
  
  protected:

    /// \brief Gives back true when the SectionReader can process 
    /// the section with the given header line.
    ///
    /// It gives back true when the header line starts with \c \@lp,
    /// and the header line's name and the nodeset's name are the same.
    virtual bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string id;
      ls >> command >> id;
      return command == "@lp" && name == id;
    }

  private:

    enum Relation {
      LE, EQ, GE
    };

    std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
      char x;
      LpSolverBase::Expr e1, e2;
      Relation op1;
      is >> std::ws;
      readExpression(is, e1);
      is >> std::ws;
      readRelation(is, op1);
      is >> std::ws;
      readExpression(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;
        readRelation(is, op2);
        is >> std::ws;
        readExpression(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::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
      LpSolverBase::Col c;
      double d;
      char x;
      readElement(is, c, d);
      if (c != INVALID) {
        e += d * c;
      } else {
        e += d;
      }
      is >> std::ws;
      while (is.get(x) && (x == '+' || x == '-')) {
        is >> std::ws;
        readElement(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::istream& readElement(std::istream& 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;
        readNum(is, e);
        d *= e;
      } else if (varFirstChar(x)) {
        is.putback(x);
        LpSolverBase::Col f;
        readCol(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;
          readNum(is, e);
          if (y == '*') {
            d *= e;
          } else {
            d /= e;
          }
        } else if (varFirstChar(x)) {
          is.putback(x);
          LpSolverBase::Col f;
          readCol(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::istream& readCol(std::istream& 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::istream& readNum(std::istream& is, double& d) {
      is >> d;
      if (!is) throw DataFormatError("Wrong number format");
      return is;
    }

    std::istream& readRelation(std::istream& 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 Reader function of the section.
    ///
    /// It reads the content of the section.
    virtual void read(std::istream& is) {
      std::string line;
      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();
          }
        } else {
          ls.str(line);
          LpSolverBase::Constr constr;
          ls >> std::ws;
          readConstraint(ls, constr);
          addConstraint(constr);
        }        
      }
    }
      
    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;
      
    LpSolverBase& lp;
    std::string name;
    ColMap cols;
  };


//   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;

      
//       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);
//         }        
//       }
//     }
      
//     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;
      
//     LpSolverBase& lp;
//     std::string name;
//     ColMap cols;
//   };

}

#endif