lemon-0.x: comparison lemon/lp

equal deleted inserted replaced

--1:000000000000
+:08439fb2c27c
+/* -*- 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>
+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;
+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;
+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;
+};
+}
+#endif

changeset 2317	6d3ed14efb68
child 2363	2aabce558574