1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/lp_utils.h Wed Nov 29 17:35:31 2006 +0000
1.3 @@ -0,0 +1,364 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_LP_UTILS_H
1.23 +#define LEMON_LP_UTILS_H
1.24 +
1.25 +#include <lemon/lp_base.h>
1.26 +
1.27 +#include <lemon/lemon_reader.h>
1.28 +
1.29 +namespace lemon {
1.30 +
1.31 + class LpReader : public LemonReader::SectionReader {
1.32 + typedef LemonReader::SectionReader Parent;
1.33 + public:
1.34 +
1.35 +
1.36 + /// \brief Constructor.
1.37 + ///
1.38 + /// Constructor for LpReader. It creates the LpReader and attach
1.39 + /// it into the given LemonReader. The lp reader will add
1.40 + /// variables, constraints and objective function to the
1.41 + /// given lp solver.
1.42 + LpReader(LemonReader& _reader, LpSolverBase& _lp,
1.43 + const std::string& _name = std::string())
1.44 + : Parent(_reader), lp(_lp), name(_name) {}
1.45 +
1.46 +
1.47 + /// \brief Destructor.
1.48 + ///
1.49 + /// Destructor for NodeSetReader.
1.50 + virtual ~LpReader() {}
1.51 +
1.52 + private:
1.53 + LpReader(const LpReader&);
1.54 + void operator=(const LpReader&);
1.55 +
1.56 + protected:
1.57 +
1.58 + /// \brief Gives back true when the SectionReader can process
1.59 + /// the section with the given header line.
1.60 + ///
1.61 + /// It gives back true when the header line starts with \c \@lp,
1.62 + /// and the header line's name and the nodeset's name are the same.
1.63 + virtual bool header(const std::string& line) {
1.64 + std::istringstream ls(line);
1.65 + std::string command;
1.66 + std::string id;
1.67 + ls >> command >> id;
1.68 + return command == "@lp" && name == id;
1.69 + }
1.70 +
1.71 + private:
1.72 +
1.73 + enum Relation {
1.74 + LE, EQ, GE
1.75 + };
1.76 +
1.77 + std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
1.78 + char x;
1.79 + LpSolverBase::Expr e1, e2;
1.80 + Relation op1;
1.81 + is >> std::ws;
1.82 + readExpression(is, e1);
1.83 + is >> std::ws;
1.84 + readRelation(is, op1);
1.85 + is >> std::ws;
1.86 + readExpression(is, e2);
1.87 + if (!is.get(x)) {
1.88 + if (op1 == LE) {
1.89 + c = e1 <= e2;
1.90 + } else if (op1 == GE) {
1.91 + c = e1 >= e2;
1.92 + } else {
1.93 + c = e1 == e2;
1.94 + }
1.95 + } else {
1.96 + is.putback(x);
1.97 + LpSolverBase::Expr e3;
1.98 + Relation op2;
1.99 + readRelation(is, op2);
1.100 + is >> std::ws;
1.101 + readExpression(is, e3);
1.102 + if (!e1.empty() || !e3.empty()) {
1.103 + throw DataFormatError("Wrong range format");
1.104 + }
1.105 + if (op2 != op1 || op1 == EQ) {
1.106 + throw DataFormatError("Wrong range format");
1.107 + }
1.108 + if (op1 == LE) {
1.109 + c = e1.constComp() <= e2 <= e3.constComp();
1.110 + } else {
1.111 + c = e1.constComp() >= e2 >= e3.constComp();
1.112 + }
1.113 + }
1.114 + }
1.115 +
1.116 + std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
1.117 + LpSolverBase::Col c;
1.118 + double d;
1.119 + char x;
1.120 + readElement(is, c, d);
1.121 + if (c != INVALID) {
1.122 + e += d * c;
1.123 + } else {
1.124 + e += d;
1.125 + }
1.126 + is >> std::ws;
1.127 + while (is.get(x) && (x == '+' || x == '-')) {
1.128 + is >> std::ws;
1.129 + readElement(is, c, d);
1.130 + if (c != INVALID) {
1.131 + e += (x == '+' ? d : -d) * c;
1.132 + } else {
1.133 + e += (x == '+' ? d : -d);
1.134 + }
1.135 + is >> std::ws;
1.136 + }
1.137 + if (!is) {
1.138 + is.clear();
1.139 + } else {
1.140 + is.putback(x);
1.141 + }
1.142 + return is;
1.143 + }
1.144 +
1.145 + std::istream& readElement(std::istream& is,
1.146 + LpSolverBase::Col& c, double& d) {
1.147 + d = 1.0;
1.148 + c = INVALID;
1.149 + char x, y;
1.150 + if (!is.get(x)) throw DataFormatError("Cannot find lp element");
1.151 + if (x == '+' || x == '-') {
1.152 + is >> std::ws;
1.153 + d *= x == '-' ? -1 : 1;
1.154 + while (is.get(x) && (x == '+' || x == '-')) {
1.155 + d *= x == '-' ? -1 : 1;
1.156 + is >> std::ws;
1.157 + }
1.158 + if (!is) throw DataFormatError("Cannot find lp element");
1.159 + }
1.160 + if (numFirstChar(x)) {
1.161 + is.putback(x);
1.162 + double e;
1.163 + readNum(is, e);
1.164 + d *= e;
1.165 + } else if (varFirstChar(x)) {
1.166 + is.putback(x);
1.167 + LpSolverBase::Col f;
1.168 + readCol(is, f);
1.169 + c = f;
1.170 + } else {
1.171 + throw DataFormatError("Invalid expression format");
1.172 + }
1.173 + is >> std::ws;
1.174 + while (is.get(y) && (y == '*' || y == '/')) {
1.175 + is >> std::ws;
1.176 + if (!is.get(x)) throw DataFormatError("Cannot find lp element");
1.177 + if (x == '+' || x == '-') {
1.178 + is >> std::ws;
1.179 + d *= x == '-' ? -1 : 1;
1.180 + while (is.get(x) && (x == '+' || x == '-')) {
1.181 + d *= x == '-' ? -1 : 1;
1.182 + is >> std::ws;
1.183 + }
1.184 + if (!is) throw DataFormatError("Cannot find lp element");
1.185 + }
1.186 + if (numFirstChar(x)) {
1.187 + is.putback(x);
1.188 + double e;
1.189 + readNum(is, e);
1.190 + if (y == '*') {
1.191 + d *= e;
1.192 + } else {
1.193 + d /= e;
1.194 + }
1.195 + } else if (varFirstChar(x)) {
1.196 + is.putback(x);
1.197 + LpSolverBase::Col f;
1.198 + readCol(is, f);
1.199 + if (y == '*') {
1.200 + if (c == INVALID) {
1.201 + c = f;
1.202 + } else {
1.203 + throw DataFormatError("Quadratic element in expression");
1.204 + }
1.205 + } else {
1.206 + throw DataFormatError("Division by variable");
1.207 + }
1.208 + } else {
1.209 + throw DataFormatError("Invalid expression format");
1.210 + }
1.211 + is >> std::ws;
1.212 + }
1.213 + if (!is) {
1.214 + is.clear();
1.215 + } else {
1.216 + is.putback(y);
1.217 + }
1.218 + return is;
1.219 + }
1.220 +
1.221 + std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
1.222 + char x;
1.223 + std::string var;
1.224 + while (is.get(x) && varChar(x)) {
1.225 + var += x;
1.226 + }
1.227 + if (!is) {
1.228 + is.clear();
1.229 + } else {
1.230 + is.putback(x);
1.231 + }
1.232 + ColMap::const_iterator it = cols.find(var);
1.233 + if (cols.find(var) != cols.end()) {
1.234 + c = it->second;
1.235 + } else {
1.236 + c = lp.addCol();
1.237 + cols.insert(std::make_pair(var, c));
1.238 + lp.colName(c, var);
1.239 + }
1.240 + return is;
1.241 + }
1.242 +
1.243 + std::istream& readNum(std::istream& is, double& d) {
1.244 + is >> d;
1.245 + if (!is) throw DataFormatError("Wrong number format");
1.246 + return is;
1.247 + }
1.248 +
1.249 + std::istream& readRelation(std::istream& is, Relation& op) {
1.250 + char x, y;
1.251 + if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
1.252 + throw DataFormatError("Wrong relation operator");
1.253 + }
1.254 + if (!is.get(y) || y != '=') {
1.255 + throw DataFormatError("Wrong relation operator");
1.256 + }
1.257 + switch (x) {
1.258 + case '<': op = LE;
1.259 + break;
1.260 + case '=': op = EQ;
1.261 + break;
1.262 + case '>': op = GE;
1.263 + break;
1.264 + }
1.265 + return is;
1.266 + }
1.267 +
1.268 + static bool relationFirstChar(char c) {
1.269 + return c == '<' || c == '=' || c == '>';
1.270 + }
1.271 +
1.272 + static bool varFirstChar(char c) {
1.273 + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
1.274 + }
1.275 +
1.276 + static bool numFirstChar(char c) {
1.277 + return (c >= '0' && c <= '9') || c == '.';
1.278 + }
1.279 +
1.280 + static bool varChar(char c) {
1.281 + return (c >= '0' && c <= '9') ||
1.282 + (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
1.283 + }
1.284 +
1.285 +
1.286 + void addConstraint(const LpSolverBase::Constr& constr) {
1.287 + if (constr.expr().size() != 1) {
1.288 + lp.addRow(constr);
1.289 + } else {
1.290 + Lp::Expr e = constr.expr();
1.291 + LpSolverBase::Col col = e.begin()->first;
1.292 + double coeff = e.begin()->second;
1.293 + double lb = LpSolverBase::NaN;
1.294 + double ub = LpSolverBase::NaN;
1.295 + if (coeff > 0) {
1.296 + if (constr.upperBounded()) {
1.297 + lb = (constr.lowerBound() - e.constComp()) / coeff;
1.298 + }
1.299 + if (constr.lowerBounded()) {
1.300 + ub = (constr.upperBound() - e.constComp()) / coeff;
1.301 + }
1.302 + } else if (coeff < 0) {
1.303 + if (constr.upperBounded()) {
1.304 + lb = (constr.upperBound() - e.constComp()) / coeff;
1.305 + }
1.306 + if (constr.lowerBounded()) {
1.307 + ub = (constr.lowerBound() - e.constComp()) / coeff;
1.308 + }
1.309 + } else {
1.310 + lb = -LpSolverBase::INF;
1.311 + ub = LpSolverBase::INF;
1.312 + }
1.313 + lp.colLowerBound(col, lb);
1.314 + lp.colUpperBound(col, ub);
1.315 + }
1.316 + }
1.317 +
1.318 + protected:
1.319 +
1.320 + /// \brief Reader function of the section.
1.321 + ///
1.322 + /// It reads the content of the section.
1.323 + virtual void read(std::istream& is) {
1.324 + std::string line;
1.325 + std::map<std::string, LpSolverBase::Col> vars;
1.326 + while (getline(is, line)) {
1.327 + std::istringstream ls(line);
1.328 + std::string sense;
1.329 + ls >> sense;
1.330 + if (sense == "min" || sense == "max") {
1.331 + LpSolverBase::Expr expr;
1.332 + ls >> std::ws;
1.333 + readExpression(ls, expr);
1.334 + lp.setObj(expr);
1.335 + if (sense == "min") {
1.336 + lp.min();
1.337 + } else {
1.338 + lp.max();
1.339 + }
1.340 + } else {
1.341 + ls.str(line);
1.342 + LpSolverBase::Constr constr;
1.343 + ls >> std::ws;
1.344 + readConstraint(ls, constr);
1.345 + addConstraint(constr);
1.346 + }
1.347 + }
1.348 + }
1.349 +
1.350 + virtual void missing() {
1.351 + ErrorMessage msg;
1.352 + msg << "Lp section not found in file: @lp " << name;
1.353 + throw IoParameterError(msg.message());
1.354 + }
1.355 +
1.356 + private:
1.357 +
1.358 + typedef std::map<std::string, LpSolverBase::Col> ColMap;
1.359 +
1.360 + LpSolverBase& lp;
1.361 + std::string name;
1.362 + ColMap cols;
1.363 + };
1.364 +
1.365 +}
1.366 +
1.367 +#endif