COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_utils.h @ 2316:c0fae4bbaa5c

Last change on this file since 2316:c0fae4bbaa5c was 2316:c0fae4bbaa5c, checked in by Balazs Dezso, 14 years ago

Lp section reader

File size: 9.4 KB
Line 
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 */
18
19#ifndef LEMON_LP_UTILS_H
20#define LEMON_LP_UTILS_H
21
22#include <lemon/lp_base.h>
23
24#include <lemon/lemon_reader.h>
25
26namespace lemon {
27
28  class LpReader : public LemonReader::SectionReader {
29    typedef LemonReader::SectionReader Parent;
30  public:
31
32
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) {}
42
43
44    /// \brief Destructor.
45    ///
46    /// Destructor for NodeSetReader.
47    virtual ~LpReader() {}
48
49  private:
50    LpReader(const LpReader&);
51    void operator=(const LpReader&);
52 
53  protected:
54
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    }
67
68  private:
69
70    enum Relation {
71      LE, EQ, GE
72    };
73
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    }
112
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    }
141
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    }
217
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    }
239
240    std::istream& readNum(std::istream& is, double& d) {
241      is >> d;
242      if (!is) throw DataFormatError("Wrong number format");
243      return is;
244    }
245
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    }
264
265    static bool relationFirstChar(char c) {
266      return c == '<' || c == '=' || c == '>';
267    }
268
269    static bool varFirstChar(char c) {
270      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
271    }
272
273    static bool numFirstChar(char c) {
274      return (c >= '0' && c <= '9') || c == '.';
275    }
276
277    static bool varChar(char c) {
278      return (c >= '0' && c <= '9') ||
279        (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
280    }
281
282
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    }
314   
315  protected:
316
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    }
346     
347    virtual void missing() {
348      ErrorMessage msg;
349      msg << "Lp section not found in file: @lp " << name;
350      throw IoParameterError(msg.message());
351    }
352
353  private:
354
355    typedef std::map<std::string, LpSolverBase::Col> ColMap;
356     
357    LpSolverBase& lp;
358    std::string name;
359    ColMap cols;
360  };
361
362}
363
364#endif
Note: See TracBrowser for help on using the repository browser.