deba@2316: /* -*- C++ -*- deba@2316: * deba@2316: * This file is a part of LEMON, a generic C++ optimization library deba@2316: * alpar@2553: * Copyright (C) 2003-2008 deba@2316: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2316: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2316: * deba@2316: * Permission to use, modify and distribute this software is granted deba@2316: * provided that this copyright notice appears in all copies. For deba@2316: * precise terms see the accompanying LICENSE file. deba@2316: * deba@2316: * This software is provided "AS IS" with no warranty of any kind, deba@2316: * express or implied, and with no claim as to its suitability for any deba@2316: * purpose. deba@2316: * deba@2316: */ deba@2316: deba@2316: #ifndef LEMON_LP_UTILS_H deba@2316: #define LEMON_LP_UTILS_H deba@2316: deba@2316: #include deba@2316: deba@2316: #include deba@2363: #include deba@2316: deba@2368: #include deba@2368: #include deba@2368: deba@2368: deba@2316: namespace lemon { deba@2316: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief The map for the result of the lp variables. deba@2368: /// deba@2368: /// The map for the result of the lp variables. deba@2368: class LpResultMap { deba@2368: public: deba@2368: typedef LpSolverBase::Col Key; deba@2368: typedef LpSolverBase::Value Value; deba@2368: deba@2368: /// \brief Constructor deba@2368: /// deba@2368: /// Constructor deba@2368: LpResultMap(const LpSolverBase& _lp) : lp(_lp) {} deba@2368: LpSolverBase::Value operator[](const LpSolverBase::Col col) const { deba@2368: return lp.primal(col); deba@2368: } deba@2368: private: deba@2368: const LpSolverBase& lp; deba@2368: }; deba@2368: deba@2370: /// \ingroup lp_utils deba@2370: /// deba@2370: /// \brief Returns an \ref LpResultMap class deba@2370: /// deba@2370: /// This function just returns an \ref LpResultMap class. deba@2370: /// \relates LpResultMap deba@2370: LpResultMap lpResultMap(const LpSolverBase& lp) { deba@2370: return LpResultMap(lp); deba@2370: } deba@2370: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief The map for the name of the lp variables. deba@2368: /// deba@2368: /// The map for the name of the lp variables. deba@2368: class LpColNameMap { deba@2368: public: deba@2368: typedef LpSolverBase::Col Key; deba@2368: typedef std::string Value; deba@2368: deba@2368: /// \brief Constructor deba@2368: /// deba@2368: /// Constructor deba@2368: LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {} deba@2368: std::string operator[](const LpSolverBase::Col col) const { deba@2368: return lp.colName(col); deba@2368: } deba@2368: private: deba@2368: const LpSolverBase& lp; deba@2368: }; deba@2368: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Writeable map for the name of the lp variables. deba@2368: /// deba@2368: /// Writeable map for the name of the lp variables. deba@2368: class LpColNameWriteMap { deba@2368: public: deba@2368: typedef LpSolverBase::Col Key; deba@2368: typedef std::string Value; deba@2368: deba@2368: /// \brief Constructor deba@2368: /// deba@2368: /// Constructor deba@2368: LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {} deba@2368: std::string operator[](const LpSolverBase::Col col) const { deba@2368: return lp.colName(col); deba@2368: } deba@2368: void set(const LpSolverBase::Col col, const std::string& name) { deba@2368: lp.colName(col, name); deba@2368: } deba@2368: private: deba@2368: LpSolverBase& lp; deba@2368: }; deba@2368: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Returns an \ref LpColNameMap class deba@2368: /// deba@2368: /// This function just returns an \ref LpColNameMap class. deba@2368: /// \relates LpColNameMap deba@2368: LpColNameMap lpColNameMap(const LpSolverBase& lp) { deba@2368: return LpColNameMap(lp); deba@2368: } deba@2368: deba@2368: LpColNameWriteMap lpColNameMap(LpSolverBase& lp) { deba@2368: return LpColNameWriteMap(lp); deba@2368: } deba@2368: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Lp variable item reader for Lemon IO deba@2368: /// deba@2368: /// This class is an Lp variable item reader for Lemon IO. It makes deba@2368: /// possible to store lp variables in lemon file. The usage of this deba@2368: /// class is very simple: deba@2368: /// deba@2368: ///\code deba@2368: /// Graph graph; deba@2368: /// Lp lp; deba@2368: /// Graph::EdgeMap var(graph); deba@2368: /// deba@2368: /// GraphReader reader(cin, graph); deba@2368: /// reader.readEdgeMap("lpvar", var, LpColReader(lp)); deba@2368: /// reader.run(); deba@2368: ///\endcode deba@2368: /// deba@2368: /// If there is already a variable with the same name in the lp then deba@2368: /// it will be used for the return value. If there is no such variable deba@2368: /// then it will be constructed. The file could contain \c '-' as value deba@2368: /// which means that no lp variable associated to the current item and deba@2368: /// in this case INVALID will be returned. deba@2368: class LpColReader { deba@2368: public: deba@2368: deba@2368: /// \brief The value type of reader. deba@2368: /// deba@2368: /// The value type of reader. deba@2368: typedef LpSolverBase::Col Value; deba@2368: deba@2368: /// \brief Constructor for the reader. deba@2368: /// deba@2368: /// Constructor for the reader. deba@2368: LpColReader(LpSolverBase& _lp) : lp(_lp) {} deba@2368: deba@2368: /// \brief Reads an lp variable from the given stream. deba@2368: /// deba@2368: /// Reads an lp variable string from the given stream. deba@2368: void read(std::istream& is, LpSolverBase::Col& col) const { deba@2368: char x; deba@2368: is >> std::ws; deba@2368: if (!is.get(x)) deba@2368: throw DataFormatError("Wrong Lp Column format!"); deba@2368: if (varFirstChar(x)) { deba@2368: std::string var; deba@2368: var += x; deba@2368: deba@2368: while (is.get(x) && varChar(x)) { deba@2368: var += x; deba@2368: } deba@2368: if (!is) { deba@2368: is.clear(); deba@2368: } else { deba@2368: is.putback(x); deba@2368: } deba@2368: col = lp.colByName(var); deba@2368: if (col == INVALID) { deba@2368: col = lp.addCol(); deba@2368: lp.colName(col, var); deba@2368: } deba@2368: } else if (x == '-') { deba@2368: col = INVALID; deba@2368: is >> std::ws; deba@2368: } else { deba@2368: std::cerr << x << std::endl; deba@2368: throw DataFormatError("Wrong Lp Column format"); deba@2368: } deba@2368: } deba@2368: deba@2368: private: deba@2368: deba@2368: static bool varFirstChar(char c) { deba@2368: return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); deba@2368: } deba@2368: deba@2368: static bool varChar(char c) { deba@2368: return (c >= '0' && c <= '9') || deba@2368: (c >= 'a' && c <= 'z') || deba@2368: (c >= 'A' && c <= 'Z') || deba@2368: c == '[' || c == ']'; deba@2368: } deba@2368: deba@2368: LpSolverBase& lp; deba@2368: deba@2368: }; deba@2368: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Lp variable item writer for Lemon IO deba@2368: /// deba@2368: /// This class is an Lp variable item writer for Lemon IO. It makes deba@2368: /// possible to store lp variables in lemon file. The usage of this deba@2368: /// class is very simple: deba@2368: /// deba@2368: ///\code deba@2368: /// Graph graph; deba@2368: /// Lp lp; deba@2368: /// Graph::EdgeMap var(graph); deba@2368: /// deba@2368: /// GraphWriter writer(cin, graph); deba@2368: /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp)); deba@2368: /// writer.run(); deba@2368: ///\endcode deba@2368: /// deba@2368: /// If there is no name associated to the current item then the name deba@2368: /// will automatically constructed. If the value is INVALID then it deba@2368: /// will write an \c '-' value to the file. deba@2368: class LpColWriter { deba@2368: public: deba@2368: deba@2368: /// \brief The value type of writer. deba@2368: /// deba@2368: /// The value type of writer. deba@2368: typedef LpSolverBase::Col Value; deba@2368: deba@2368: /// \brief Constructor for the writer. deba@2368: /// deba@2368: /// Constructor for the writer. deba@2368: LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {} deba@2368: deba@2368: /// \brief Writes an lp variable to the given stream. deba@2368: /// deba@2368: /// Writes an lp variable to the given stream. deba@2368: void write(std::ostream& os, const LpSolverBase::Col& col) const { deba@2368: if (col != INVALID) { deba@2368: std::string name = lp.colName(col); deba@2368: if (name.empty()) { deba@2368: std::ostringstream ls; deba@2368: ls << "x" << num; deba@2368: ++num; deba@2368: while (lp.colByName(ls.str()) != INVALID) { deba@2368: ls.str(std::string()); deba@2368: ls << "x" << num; deba@2368: ++num; deba@2368: } deba@2368: const_cast(lp).colName(col, ls.str()); deba@2368: os << ls.str(); deba@2368: } else { deba@2368: os << name; deba@2368: } deba@2368: } else { deba@2368: os << "-"; deba@2368: } deba@2368: } deba@2368: deba@2368: private: deba@2368: deba@2368: const LpSolverBase& lp; deba@2368: mutable int num; deba@2368: deba@2368: }; deba@2368: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Lp section reader for lemon IO deba@2368: /// deba@2368: /// This section reader provides an easy way to read an Lp problem deba@2368: /// from a file. The lemon lp section format contains three parts. deba@2368: /// deba@2368: ///\code deba@2368: /// @lp deba@2368: /// constraints deba@2368: /// 7 == x1 - 1 * x2 deba@2368: /// 2 * x1 + x3 / 2 <= 7 deba@2368: /// x2 + -3 * x3 >= 8 deba@2368: /// 3 <= x2 - 2 * x1 <= 8 deba@2368: /// bounds deba@2368: /// x1 >= 3 deba@2368: /// 2 <= x2 <= 5 deba@2368: /// 0 <= x3 <= 8 deba@2368: /// objective deba@2368: /// min x1 + 2 * x2 - x3 deba@2368: ///\endcode deba@2368: /// deba@2368: /// The first part gives the constraints to the lp. The constraints deba@2368: /// could be equality, lower bound, upper bound or range for an deba@2368: /// expression or equality, less or more for two expressions. deba@2368: /// deba@2368: /// The second part gives the bounds for the variables. The bounds deba@2368: /// could be the same as for the single expression so equality, deba@2368: /// lower bound, upper bound or range. deba@2368: /// deba@2368: /// The third part is the objective function, it should start with deba@2368: /// \c min or \c max and then a valid linear expression. deba@2368: /// deba@2368: /// The reader constructs automatically the variable for a name if deba@2368: /// there is not already a variable with the same name. deba@2368: /// deba@2368: /// The basic way to read an LP problem is made by the next code: deba@2368: ///\code deba@2368: /// Lp lp; deba@2368: /// deba@2368: /// LemonReader reader(filename_or_istream); deba@2368: /// LpReader lpreader(reader, lp); deba@2368: /// deba@2368: /// reader.run(); deba@2368: ///\endcode deba@2368: /// deba@2368: /// Of course instead of \c LemonReader you can give a \c deba@2368: /// GraphReader to the LpReader constructor. Also useful that you deba@2368: /// can mix lp problems and graphs in the same file. deba@2316: class LpReader : public LemonReader::SectionReader { deba@2316: typedef LemonReader::SectionReader Parent; deba@2316: public: deba@2316: deba@2316: deba@2316: /// \brief Constructor. deba@2316: /// deba@2368: /// Constructor for LpReader. It creates the LpReader and attachs deba@2316: /// it into the given LemonReader. The lp reader will add deba@2316: /// variables, constraints and objective function to the deba@2316: /// given lp solver. deba@2316: LpReader(LemonReader& _reader, LpSolverBase& _lp, deba@2316: const std::string& _name = std::string()) deba@2316: : Parent(_reader), lp(_lp), name(_name) {} deba@2316: deba@2316: deba@2316: /// \brief Destructor. deba@2316: /// deba@2368: /// Destructor for LpReader. deba@2316: virtual ~LpReader() {} deba@2316: deba@2316: private: deba@2316: LpReader(const LpReader&); deba@2316: void operator=(const LpReader&); deba@2316: deba@2316: protected: deba@2316: deba@2316: /// \brief Gives back true when the SectionReader can process deba@2316: /// the section with the given header line. deba@2316: /// deba@2316: /// It gives back true when the header line starts with \c \@lp, deba@2316: /// and the header line's name and the nodeset's name are the same. deba@2316: virtual bool header(const std::string& line) { deba@2316: std::istringstream ls(line); deba@2316: std::string command; deba@2316: std::string id; deba@2316: ls >> command >> id; deba@2316: return command == "@lp" && name == id; deba@2316: } deba@2316: deba@2316: private: deba@2316: deba@2368: enum Part { deba@2364: CONSTRAINTS, BOUNDS, OBJECTIVE deba@2364: }; deba@2364: deba@2316: enum Relation { deba@2316: LE, EQ, GE deba@2316: }; deba@2316: deba@2364: std::istream& readConstraint(std::istream& is) { deba@2364: LpSolverBase::Constr c; deba@2316: char x; deba@2316: LpSolverBase::Expr e1, e2; deba@2316: Relation op1; deba@2316: is >> std::ws; deba@2316: readExpression(is, e1); deba@2316: is >> std::ws; deba@2316: readRelation(is, op1); deba@2316: is >> std::ws; deba@2316: readExpression(is, e2); deba@2364: is >> std::ws; deba@2316: if (!is.get(x)) { deba@2316: if (op1 == LE) { deba@2364: if (e1.size() == 0) { deba@2364: c = e2 >= e1; deba@2364: } else { deba@2364: c = e1 <= e2; deba@2364: } deba@2316: c = e1 <= e2; deba@2316: } else if (op1 == GE) { deba@2364: if (e1.size() == 0) { deba@2364: c = e2 <= e1; deba@2364: } else { deba@2364: c = e1 >= e2; deba@2364: } deba@2316: } else { deba@2364: if (e1.size() == 0) { deba@2364: c = e2 == e1; deba@2364: } else { deba@2364: c = e1 == e2; deba@2364: } deba@2316: } deba@2316: } else { deba@2316: is.putback(x); deba@2316: LpSolverBase::Expr e3; deba@2316: Relation op2; deba@2316: readRelation(is, op2); deba@2316: is >> std::ws; deba@2316: readExpression(is, e3); deba@2316: if (!e1.empty() || !e3.empty()) { deba@2316: throw DataFormatError("Wrong range format"); deba@2316: } deba@2316: if (op2 != op1 || op1 == EQ) { deba@2316: throw DataFormatError("Wrong range format"); deba@2316: } deba@2316: if (op1 == LE) { deba@2316: c = e1.constComp() <= e2 <= e3.constComp(); deba@2316: } else { deba@2316: c = e1.constComp() >= e2 >= e3.constComp(); deba@2316: } deba@2364: is >> std::ws; deba@2364: if (is.get(x)) { deba@2364: throw DataFormatError("Wrong variable bounds format"); deba@2364: } deba@2316: } deba@2364: lp.addRow(c); deba@2364: return is; deba@2364: } deba@2364: deba@2364: std::istream& readObjective(std::istream& is) { deba@2364: is >> std::ws; deba@2364: std::string sense; deba@2364: is >> sense; deba@2364: if (sense != "min" && sense != "max") { deba@2364: throw DataFormatError("Wrong objective function format"); deba@2364: } deba@2364: LpSolverBase::Expr expr; deba@2364: is >> std::ws; deba@2364: readExpression(is, expr); deba@2369: lp.obj(expr); deba@2364: if (sense == "min") { deba@2364: lp.min(); deba@2364: } else { deba@2364: lp.max(); deba@2364: } deba@2364: return is; deba@2364: } deba@2364: deba@2364: std::istream& readBounds(std::istream& is) { deba@2364: LpSolverBase::Col c; deba@2364: char x; deba@2364: is >> std::ws; deba@2364: if (!is.get(x)) { deba@2364: throw DataFormatError("Wrong variable bounds format"); deba@2364: } deba@2364: if (varFirstChar(x)) { deba@2364: is.putback(x); deba@2364: readCol(is, c); deba@2364: is >> std::ws; deba@2364: Relation op1; deba@2364: readRelation(is, op1); deba@2364: double v; deba@2364: readNum(is, v); deba@2364: if (op1 == EQ) { deba@2364: lp.colLowerBound(c, v); deba@2364: lp.colUpperBound(c, v); deba@2364: } else if (op1 == LE) { deba@2364: lp.colUpperBound(c, v); deba@2364: } else { deba@2364: lp.colLowerBound(c, v); deba@2364: } deba@2364: is >> std::ws; deba@2364: if (is.get(x)) { deba@2364: throw DataFormatError("Wrong variable bounds format"); deba@2364: } deba@2364: } else { deba@2364: is.putback(x); deba@2364: double v; deba@2364: readNum(is, v); deba@2364: is >> std::ws; deba@2364: Relation op1; deba@2364: readRelation(is, op1); deba@2364: is >> std::ws; deba@2364: readCol(is, c); deba@2364: is >> std::ws; deba@2364: if (is.get(x)) { deba@2364: is.putback(x); deba@2364: is >> std::ws; deba@2364: Relation op2; deba@2364: readRelation(is, op2); deba@2364: double w; deba@2364: is >> std::ws; deba@2364: readNum(is, w); deba@2364: if (op2 != op1 || op1 == EQ) { deba@2364: throw DataFormatError("Wrong range format"); deba@2364: } deba@2364: if (op1 == LE) { deba@2364: lp.colLowerBound(c, v); deba@2364: lp.colUpperBound(c, w); deba@2364: } else { deba@2364: lp.colLowerBound(c, w); deba@2364: lp.colUpperBound(c, v); deba@2364: } deba@2368: is >> std::ws; deba@2364: if (is.get(x)) { deba@2364: throw DataFormatError("Wrong variable bounds format"); deba@2364: } deba@2364: } else { deba@2364: if (op1 == EQ) { deba@2364: lp.colLowerBound(c, v); deba@2364: lp.colUpperBound(c, v); deba@2364: } else if (op1 == LE) { deba@2364: lp.colLowerBound(c, v); deba@2364: } else { deba@2364: lp.colUpperBound(c, v); deba@2364: } deba@2364: } deba@2364: } deba@2364: return is; deba@2316: } deba@2316: deba@2316: std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) { deba@2316: LpSolverBase::Col c; deba@2316: double d; deba@2316: char x; deba@2316: readElement(is, c, d); deba@2316: if (c != INVALID) { deba@2316: e += d * c; deba@2316: } else { deba@2316: e += d; deba@2316: } deba@2316: is >> std::ws; deba@2316: while (is.get(x) && (x == '+' || x == '-')) { deba@2316: is >> std::ws; deba@2316: readElement(is, c, d); deba@2316: if (c != INVALID) { deba@2316: e += (x == '+' ? d : -d) * c; deba@2316: } else { deba@2316: e += (x == '+' ? d : -d); deba@2316: } deba@2316: is >> std::ws; deba@2316: } deba@2316: if (!is) { deba@2316: is.clear(); deba@2316: } else { deba@2316: is.putback(x); deba@2316: } deba@2316: return is; deba@2316: } deba@2316: deba@2316: std::istream& readElement(std::istream& is, deba@2316: LpSolverBase::Col& c, double& d) { deba@2316: d = 1.0; deba@2316: c = INVALID; deba@2316: char x, y; deba@2316: if (!is.get(x)) throw DataFormatError("Cannot find lp element"); deba@2316: if (x == '+' || x == '-') { deba@2316: is >> std::ws; deba@2316: d *= x == '-' ? -1 : 1; deba@2316: while (is.get(x) && (x == '+' || x == '-')) { deba@2316: d *= x == '-' ? -1 : 1; deba@2316: is >> std::ws; deba@2316: } deba@2316: if (!is) throw DataFormatError("Cannot find lp element"); deba@2316: } deba@2316: if (numFirstChar(x)) { deba@2316: is.putback(x); deba@2316: double e; deba@2316: readNum(is, e); deba@2316: d *= e; deba@2316: } else if (varFirstChar(x)) { deba@2316: is.putback(x); deba@2316: LpSolverBase::Col f; deba@2316: readCol(is, f); deba@2316: c = f; deba@2316: } else { deba@2316: throw DataFormatError("Invalid expression format"); deba@2316: } deba@2316: is >> std::ws; deba@2316: while (is.get(y) && (y == '*' || y == '/')) { deba@2316: is >> std::ws; deba@2316: if (!is.get(x)) throw DataFormatError("Cannot find lp element"); deba@2316: if (x == '+' || x == '-') { deba@2316: is >> std::ws; deba@2316: d *= x == '-' ? -1 : 1; deba@2316: while (is.get(x) && (x == '+' || x == '-')) { deba@2316: d *= x == '-' ? -1 : 1; deba@2316: is >> std::ws; deba@2316: } deba@2316: if (!is) throw DataFormatError("Cannot find lp element"); deba@2316: } deba@2316: if (numFirstChar(x)) { deba@2316: is.putback(x); deba@2316: double e; deba@2316: readNum(is, e); deba@2316: if (y == '*') { deba@2316: d *= e; deba@2316: } else { deba@2316: d /= e; deba@2316: } deba@2316: } else if (varFirstChar(x)) { deba@2316: is.putback(x); deba@2316: LpSolverBase::Col f; deba@2316: readCol(is, f); deba@2316: if (y == '*') { deba@2316: if (c == INVALID) { deba@2316: c = f; deba@2316: } else { deba@2316: throw DataFormatError("Quadratic element in expression"); deba@2316: } deba@2316: } else { deba@2316: throw DataFormatError("Division by variable"); deba@2316: } deba@2316: } else { deba@2316: throw DataFormatError("Invalid expression format"); deba@2316: } deba@2316: is >> std::ws; deba@2316: } deba@2316: if (!is) { deba@2316: is.clear(); deba@2316: } else { deba@2316: is.putback(y); deba@2316: } deba@2316: return is; deba@2316: } deba@2316: deba@2316: std::istream& readCol(std::istream& is, LpSolverBase::Col& c) { deba@2316: char x; deba@2316: std::string var; deba@2316: while (is.get(x) && varChar(x)) { deba@2316: var += x; deba@2316: } deba@2316: if (!is) { deba@2316: is.clear(); deba@2316: } else { deba@2316: is.putback(x); deba@2316: } deba@2368: c = lp.colByName(var); deba@2368: if (c == INVALID) { deba@2316: c = lp.addCol(); deba@2316: lp.colName(c, var); deba@2316: } deba@2316: return is; deba@2316: } deba@2316: deba@2316: std::istream& readNum(std::istream& is, double& d) { deba@2316: is >> d; deba@2316: if (!is) throw DataFormatError("Wrong number format"); deba@2316: return is; deba@2316: } deba@2316: deba@2316: std::istream& readRelation(std::istream& is, Relation& op) { deba@2316: char x, y; deba@2316: if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) { deba@2316: throw DataFormatError("Wrong relation operator"); deba@2316: } deba@2316: if (!is.get(y) || y != '=') { deba@2316: throw DataFormatError("Wrong relation operator"); deba@2316: } deba@2316: switch (x) { deba@2316: case '<': op = LE; deba@2316: break; deba@2316: case '=': op = EQ; deba@2316: break; deba@2316: case '>': op = GE; deba@2316: break; deba@2316: } deba@2316: return is; deba@2316: } deba@2316: deba@2316: static bool relationFirstChar(char c) { deba@2316: return c == '<' || c == '=' || c == '>'; deba@2316: } deba@2316: deba@2316: static bool varFirstChar(char c) { deba@2316: return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); deba@2316: } deba@2316: deba@2316: static bool numFirstChar(char c) { deba@2316: return (c >= '0' && c <= '9') || c == '.'; deba@2316: } deba@2368: deba@2316: static bool varChar(char c) { deba@2316: return (c >= '0' && c <= '9') || deba@2364: (c >= 'a' && c <= 'z') || deba@2364: (c >= 'A' && c <= 'Z') || deba@2364: c == '[' || c == ']'; deba@2316: } deba@2316: deba@2316: protected: deba@2316: deba@2316: /// \brief Reader function of the section. deba@2316: /// deba@2316: /// It reads the content of the section. deba@2316: virtual void read(std::istream& is) { deba@2316: std::string line; deba@2368: Part part = CONSTRAINTS; deba@2316: while (getline(is, line)) { deba@2316: std::istringstream ls(line); deba@2364: std::string type; deba@2364: ls >> type; deba@2364: if (type == "constraints") { deba@2368: part = CONSTRAINTS; deba@2368: ls >> std::ws; deba@2368: char x; deba@2368: if (ls.get(x)) deba@2368: throw DataFormatError("Wrong Lp format"); deba@2364: } else if (type == "bounds") { deba@2368: part = BOUNDS; deba@2368: ls >> std::ws; deba@2368: char x; deba@2368: if (ls.get(x)) deba@2368: throw DataFormatError("Wrong Lp format"); deba@2364: } else if (type == "objective") { deba@2368: part = OBJECTIVE; deba@2368: ls >> std::ws; deba@2368: char x; deba@2368: if (ls.get(x)) deba@2368: throw DataFormatError("Wrong Lp format"); deba@2316: } else { deba@2316: ls.str(line); deba@2368: switch (part) { deba@2364: case CONSTRAINTS: deba@2364: readConstraint(ls); deba@2364: break; deba@2364: case BOUNDS: deba@2364: readBounds(ls); deba@2364: break; deba@2364: case OBJECTIVE: deba@2364: readObjective(ls); deba@2364: break; deba@2364: } deba@2368: } deba@2316: } deba@2316: } deba@2316: deba@2316: virtual void missing() { deba@2316: ErrorMessage msg; deba@2316: msg << "Lp section not found in file: @lp " << name; deba@2316: throw IoParameterError(msg.message()); deba@2316: } deba@2316: deba@2316: private: deba@2316: deba@2316: deba@2316: LpSolverBase& lp; deba@2316: std::string name; deba@2316: }; deba@2316: deba@2363: deba@2370: /// \ingroup lp_utils deba@2368: /// deba@2368: /// \brief Lp section writer for lemon IO deba@2368: /// deba@2368: /// This section reader provides an easy way to write an Lp problem deba@2368: /// to a file. The lemon lp section format contains three parts. deba@2368: /// deba@2368: ///\code deba@2368: /// @lp deba@2368: /// constraints deba@2368: /// 7 == x1 - 1 * x2 deba@2368: /// 2 * x1 + x3 / 2 <= 7 deba@2368: /// x2 + -3 * x3 >= 8 deba@2368: /// 3 <= x2 - 2 * x1 <= 8 deba@2368: /// bounds deba@2368: /// x1 >= 3 deba@2368: /// 2 <= x2 <= 5 deba@2368: /// 0 <= x3 <= 8 deba@2368: /// objective deba@2368: /// min x1 + 2 * x2 - x3 deba@2368: ///\endcode deba@2368: /// deba@2368: /// The first part gives the constraints to the lp. The constraints deba@2368: /// could be equality, lower bound, upper bound or range for an deba@2368: /// expression or equality, less or more for two expressions. deba@2368: /// deba@2368: /// The second part gives the bounds for the variables. The bounds deba@2368: /// could be the same as for the single expression so equality, deba@2368: /// lower bound, upper bound or range. deba@2368: /// deba@2368: /// The third part is the objective function, it should start with deba@2368: /// \c min or \c max and then a valid linear expression. deba@2368: /// deba@2368: /// If an LP variable does not have name in the writer, then it will deba@2368: /// automatically created in the writer. This make a slight change deba@2368: /// in the \c const variable. deba@2368: /// deba@2368: /// The basic way to write an LP problem is made by the next code: deba@2368: ///\code deba@2368: /// Lp lp; deba@2368: /// deba@2368: /// LemonWriter writer(filename_or_ostream); deba@2368: /// LpWriter lpwriter(writer, lp); deba@2368: /// deba@2368: /// writer.run(); deba@2368: ///\endcode deba@2368: /// deba@2368: /// Of course instead of \c LemonWriter you can give a \c deba@2368: /// GraphWriter to the LpWriter constructor. Also useful that you deba@2368: /// can mix lp problems and graphs in the same file. deba@2364: class LpWriter : public LemonWriter::SectionWriter { deba@2364: typedef LemonWriter::SectionWriter Parent; deba@2364: public: deba@2363: deba@2363: deba@2364: /// \brief Constructor. deba@2364: /// deba@2364: /// Constructor for LpWriter. It creates the LpWriter and attach deba@2368: /// it into the given LemonWriter. deba@2368: LpWriter(LemonWriter& _writer, const LpSolverBase& _lp, deba@2364: const std::string& _name = std::string()) deba@2364: : Parent(_writer), lp(_lp), name(_name) {} deba@2363: deba@2363: deba@2364: /// \brief Destructor. deba@2364: /// deba@2368: /// Destructor for LpWriter. deba@2364: virtual ~LpWriter() {} deba@2363: deba@2364: private: deba@2364: LpWriter(const LpWriter&); deba@2364: void operator=(const LpWriter&); deba@2363: deba@2364: protected: deba@2363: deba@2364: /// \brief Gives back true when the SectionWriter can process deba@2364: /// the section with the given header line. deba@2364: /// deba@2364: /// It gives back the header line of the \c \@lp section. deba@2364: virtual std::string header() { deba@2364: std::ostringstream ls; deba@2364: ls << "@lp " << name; deba@2364: return ls.str(); deba@2364: } deba@2363: deba@2364: private: deba@2363: deba@2364: void createCols() { deba@2368: int num = 0; deba@2364: deba@2364: for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) { deba@2364: std::string name = lp.colName(it); deba@2368: if (name.empty()) { deba@2364: std::ostringstream ls; deba@2368: ls << "x" << num; deba@2364: ++num; deba@2368: while (lp.colByName(ls.str()) != INVALID) { deba@2368: ls.str(std::string()); deba@2368: ls << "x" << num; deba@2368: ++num; deba@2368: } deba@2368: const_cast(lp).colName(it, ls.str()); deba@2364: } deba@2364: } deba@2364: } deba@2364: deba@2364: void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) { deba@2364: bool first = true; deba@2364: for (LpSolverBase::Expr::const_iterator jt = e.begin(); deba@2364: jt != e.end(); ++jt) { deba@2364: if (jt->second < 0.0) { deba@2364: os << "- "; deba@2364: if (jt->second != -1.0) { deba@2364: os << -jt->second << " * "; deba@2364: } deba@2364: } else if (jt->second > 0.0) { deba@2364: if (!first) { deba@2364: os << "+ "; deba@2364: } deba@2364: if (jt->second != 1.0) { deba@2364: os << jt->second << " * "; deba@2364: } deba@2364: } deba@2364: first = false; deba@2368: os << lp.colName(jt->first) << " "; deba@2364: } deba@2364: if (e.constComp() < 0.0) { deba@2364: os << "- " << -e.constComp() << " "; deba@2364: } else if (e.constComp() > 0.0) { deba@2364: if (!first) { deba@2364: os << "+ "; deba@2364: } deba@2364: os << e.constComp() << " "; deba@2421: } deba@2421: if (e.begin() == e.end() && e.constComp() == 0.0) { deba@2421: os << "0 "; deba@2421: } deba@2364: } deba@2364: deba@2364: protected: deba@2364: deba@2364: /// \brief Writer function of the section. deba@2364: /// deba@2364: /// It writes the content of the section. deba@2364: virtual void write(std::ostream& os) { deba@2364: createCols(); deba@2364: deba@2364: os << "constraints" << std::endl; deba@2363: deba@2364: for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) { deba@2364: double lower, upper; deba@2364: lp.getRowBounds(it, lower, upper); deba@2364: if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) deba@2364: continue; deba@2364: os << " "; deba@2364: deba@2364: if (lower != upper) { deba@2364: if (lower != -LpSolverBase::INF) { deba@2364: os << lower << " <= "; deba@2364: } deba@2364: deba@2364: writeExpression(os, lp.row(it)); deba@2364: deba@2364: if (upper != LpSolverBase::INF) { deba@2364: os << "<= " << upper << " "; deba@2364: } deba@2364: } else { deba@2363: deba@2364: writeExpression(os, lp.row(it)); deba@2364: os << "== " << upper << " "; deba@2364: deba@2364: } deba@2363: deba@2364: os << std::endl; deba@2364: } deba@2363: deba@2364: os << "bounds" << std::endl; deba@2364: deba@2364: for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) { deba@2364: double lower = lp.colLowerBound(it); deba@2364: double upper = lp.colUpperBound(it); deba@2364: if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) deba@2364: continue; deba@2364: os << " "; deba@2363: deba@2364: if (lower != upper) { deba@2364: if (lower != -LpSolverBase::INF) { deba@2364: os << lower << " <= "; deba@2364: } deba@2364: deba@2368: os << lp.colName(it) << " "; deba@2364: deba@2364: if (upper != LpSolverBase::INF) { deba@2364: os << "<= " << upper << " "; deba@2364: } deba@2364: } else { deba@2368: os << lp.colName(it) << " == " << upper << " "; deba@2364: } deba@2364: os << std::endl; deba@2364: } deba@2363: deba@2364: os << "objective" << std::endl; deba@2364: os << " "; deba@2369: if (lp.isMin()) { deba@2364: os << "min "; deba@2364: } else { deba@2364: os << "max "; deba@2364: } deba@2364: writeExpression(os, lp.obj()); deba@2364: os << std::endl; deba@2364: } deba@2364: deba@2363: deba@2364: private: deba@2363: deba@2368: const LpSolverBase& lp; deba@2364: std::string name; deba@2364: }; deba@2363: deba@2316: } deba@2316: deba@2316: #endif