lemon-0.x: lemon/lp_utils.h@0aaa7ada5395

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_LP_UTILS_H

    20 #define LEMON_LP_UTILS_H

    22 #include <lemon/lp_base.h>

    24 #include <lemon/lemon_reader.h>

    26 namespace lemon {

    28   class LpReader : public LemonReader::SectionReader {

    29     typedef LemonReader::SectionReader Parent;

    30   public:

    33     /// \brief Constructor.

    34     ///

    35     /// Constructor for LpReader. It creates the LpReader and attach

    36     /// it into the given LemonReader. The lp reader will add

    37     /// variables, constraints and objective function to the

    38     /// given lp solver.

    39     LpReader(LemonReader& _reader, LpSolverBase& _lp,

    40              const std::string& _name = std::string())

    41       : Parent(_reader), lp(_lp), name(_name) {}

    44     /// \brief Destructor.

    45     ///

    46     /// Destructor for NodeSetReader.

    47     virtual ~LpReader() {}

    49   private:

    50     LpReader(const LpReader&);

    51     void operator=(const LpReader&);

    53   protected:

    55     /// \brief Gives back true when the SectionReader can process

    56     /// the section with the given header line.

    57     ///

    58     /// It gives back true when the header line starts with \c \@lp,

    59     /// and the header line's name and the nodeset's name are the same.

    60     virtual bool header(const std::string& line) {

    61       std::istringstream ls(line);

    62       std::string command;

    63       std::string id;

    64       ls >> command >> id;

    65       return command == "@lp" && name == id;

    66     }

    68   private:

    70     enum Relation {

    71       LE, EQ, GE

    72     };

    74     std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {

    75       char x;

    76       LpSolverBase::Expr e1, e2;

    77       Relation op1;

    78       is >> std::ws;

    79       readExpression(is, e1);

    80       is >> std::ws;

    81       readRelation(is, op1);

    82       is >> std::ws;

    83       readExpression(is, e2);

    84       if (!is.get(x)) {

    85         if (op1 == LE) {

    86           c = e1 <= e2;

    87         } else if (op1 == GE) {

    88           c = e1 >= e2;

    89         } else {

    90           c = e1 == e2;

    91         }

    92       } else {

    93         is.putback(x);

    94         LpSolverBase::Expr e3;

    95         Relation op2;

    96         readRelation(is, op2);

    97         is >> std::ws;

    98         readExpression(is, e3);

    99         if (!e1.empty() || !e3.empty()) {

   100           throw DataFormatError("Wrong range format");

   101         }

   102         if (op2 != op1 || op1 == EQ) {

   103           throw DataFormatError("Wrong range format");

   104         }

   105         if (op1 == LE) {

   106           c = e1.constComp() <= e2 <= e3.constComp();

   107         } else {

   108           c = e1.constComp() >= e2 >= e3.constComp();

   109         }

   110       }

   111     }

   113     std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {

   114       LpSolverBase::Col c;

   115       double d;

   116       char x;

   117       readElement(is, c, d);

   118       if (c != INVALID) {

   119         e += d * c;

   120       } else {

   121         e += d;

   122       }

   123       is >> std::ws;

   124       while (is.get(x) && (x == '+' || x == '-')) {

   125         is >> std::ws;

   126         readElement(is, c, d);

   127         if (c != INVALID) {

   128           e += (x == '+' ? d : -d) * c;

   129         } else {

   130           e += (x == '+' ? d : -d);

   131         }

   132         is >> std::ws;

   133       }

   134       if (!is) {

   135         is.clear();

   136       } else {

   137         is.putback(x);

   138       }

   139       return is;

   140     }

   142     std::istream& readElement(std::istream& is,

   143                               LpSolverBase::Col& c, double& d) {

   144       d = 1.0;

   145       c = INVALID;

   146       char x, y;

   147       if (!is.get(x)) throw DataFormatError("Cannot find lp element");

   148       if (x == '+' || x == '-') {

   149         is >> std::ws;

   150         d *= x == '-' ? -1 : 1;

   151         while (is.get(x) && (x == '+' || x == '-')) {

   152           d *= x == '-' ? -1 : 1;

   153           is >> std::ws;

   154         }

   155         if (!is) throw DataFormatError("Cannot find lp element");

   156       }

   157       if (numFirstChar(x)) {

   158         is.putback(x);

   159         double e;

   160         readNum(is, e);

   161         d *= e;

   162       } else if (varFirstChar(x)) {

   163         is.putback(x);

   164         LpSolverBase::Col f;

   165         readCol(is, f);

   166         c = f;

   167       } else {

   168         throw DataFormatError("Invalid expression format");

   169       }

   170       is >> std::ws;

   171       while (is.get(y) && (y == '*' || y == '/')) {

   172         is >> std::ws;

   173         if (!is.get(x)) throw DataFormatError("Cannot find lp element");

   174         if (x == '+' || x == '-') {

   175           is >> std::ws;

   176           d *= x == '-' ? -1 : 1;

   177           while (is.get(x) && (x == '+' || x == '-')) {

   178             d *= x == '-' ? -1 : 1;

   179             is >> std::ws;

   180           }

   181           if (!is) throw DataFormatError("Cannot find lp element");

   182         }

   183         if (numFirstChar(x)) {

   184           is.putback(x);

   185           double e;

   186           readNum(is, e);

   187           if (y == '*') {

   188             d *= e;

   189           } else {

   190             d /= e;

   191           }

   192         } else if (varFirstChar(x)) {

   193           is.putback(x);

   194           LpSolverBase::Col f;

   195           readCol(is, f);

   196           if (y == '*') {

   197             if (c == INVALID) {

   198               c = f;

   199             } else {

   200               throw DataFormatError("Quadratic element in expression");

   201             }

   202           } else {

   203             throw DataFormatError("Division by variable");

   204           }

   205         } else {

   206           throw DataFormatError("Invalid expression format");

   207         }

   208         is >> std::ws;

   209       }

   210       if (!is) {

   211         is.clear();

   212       } else {

   213         is.putback(y);

   214       }

   215       return is;

   216     }

   218     std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {

   219       char x;

   220       std::string var;

   221       while (is.get(x) && varChar(x)) {

   222         var += x;

   223       }

   224       if (!is) {

   225         is.clear();

   226       } else {

   227         is.putback(x);

   228       }

   229       ColMap::const_iterator it = cols.find(var);

   230       if (cols.find(var) != cols.end()) {

   231         c = it->second;

   232       } else {

   233         c = lp.addCol();

   234         cols.insert(std::make_pair(var, c));

   235         lp.colName(c, var);

   236       }

   237       return is;

   238     }

   240     std::istream& readNum(std::istream& is, double& d) {

   241       is >> d;

   242       if (!is) throw DataFormatError("Wrong number format");

   243       return is;

   244     }

   246     std::istream& readRelation(std::istream& is, Relation& op) {

   247       char x, y;

   248       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {

   249         throw DataFormatError("Wrong relation operator");

   250       }

   251       if (!is.get(y) || y != '=') {

   252         throw DataFormatError("Wrong relation operator");

   253       }

   254       switch (x) {

   255       case '<': op = LE;

   256         break;

   257       case '=': op = EQ;

   258         break;

   259       case '>': op = GE;

   260         break;

   261       }

   262       return is;

   263     }

   265     static bool relationFirstChar(char c) {

   266       return c == '<' || c == '=' || c == '>';

   267     }

   269     static bool varFirstChar(char c) {

   270       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

   271     }

   273     static bool numFirstChar(char c) {

   274       return (c >= '0' && c <= '9') || c == '.';

   275     }

   277     static bool varChar(char c) {

   278       return (c >= '0' && c <= '9') ||

   279         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

   280     }

   283     void addConstraint(const LpSolverBase::Constr& constr) {

   284       if (constr.expr().size() != 1) {

   285         lp.addRow(constr);

   286       } else {

   287         Lp::Expr e = constr.expr();

   288         LpSolverBase::Col col = e.begin()->first;

   289         double coeff = e.begin()->second;

   290         double lb = LpSolverBase::NaN;

   291         double ub = LpSolverBase::NaN;

   292         if (coeff > 0) {

   293           if (constr.upperBounded()) {

   294             lb = (constr.lowerBound() - e.constComp()) / coeff;

   295           }

   296           if (constr.lowerBounded()) {

   297             ub = (constr.upperBound() - e.constComp()) / coeff;

   298           }

   299         } else if (coeff < 0) {

   300           if (constr.upperBounded()) {

   301             lb = (constr.upperBound() - e.constComp()) / coeff;

   302           }

   303           if (constr.lowerBounded()) {

   304             ub = (constr.lowerBound() - e.constComp()) / coeff;

   305           }

   306         } else {

   307           lb = -LpSolverBase::INF;

   308           ub = LpSolverBase::INF;

   309         }

   310         lp.colLowerBound(col, lb);

   311         lp.colUpperBound(col, ub);

   312       }

   313     }

   315   protected:

   317     /// \brief Reader function of the section.

   318     ///

   319     /// It reads the content of the section.

   320     virtual void read(std::istream& is) {

   321       std::string line;

   322       std::map<std::string, LpSolverBase::Col> vars;

   323       while (getline(is, line)) {

   324         std::istringstream ls(line);

   325         std::string sense;

   326         ls >> sense;

   327         if (sense == "min" || sense == "max") {

   328           LpSolverBase::Expr expr;

   329           ls >> std::ws;

   330           readExpression(ls, expr);

   331           lp.setObj(expr);

   332           if (sense == "min") {

   333             lp.min();

   334           } else {

   335             lp.max();

   336           }

   337         } else {

   338           ls.str(line);

   339           LpSolverBase::Constr constr;

   340           ls >> std::ws;

   341           readConstraint(ls, constr);

   342           addConstraint(constr);

   343         }

   344       }

   345     }

   347     virtual void missing() {

   348       ErrorMessage msg;

   349       msg << "Lp section not found in file: @lp " << name;

   350       throw IoParameterError(msg.message());

   351     }

   353   private:

   355     typedef std::map<std::string, LpSolverBase::Col> ColMap;

   357     LpSolverBase& lp;

   358     std::string name;

   359     ColMap cols;

   360   };

   362 }

   364 #endif

author	alpar
	Fri, 19 Jan 2007 17:27:22 +0000
changeset 2347	0aaa7ada5395
child 2363	2aabce558574
permissions	-rw-r--r--