COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_utils.h @ 2364:3a5e67bd42d2

Last change on this file since 2364:3a5e67bd42d2 was 2364:3a5e67bd42d2, checked in by Balazs Dezso, 13 years ago

Lp row and col getter function
lp section reader and writer for lemon IO

File size: 15.7 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#include <lemon/lemon_writer.h>
26
27namespace lemon {
28
29  class LpReader : public LemonReader::SectionReader {
30    typedef LemonReader::SectionReader Parent;
31  public:
32
33
34    /// \brief Constructor.
35    ///
36    /// Constructor for LpReader. It creates the LpReader and attach
37    /// it into the given LemonReader. The lp reader will add
38    /// variables, constraints and objective function to the
39    /// given lp solver.
40    LpReader(LemonReader& _reader, LpSolverBase& _lp,
41             const std::string& _name = std::string())
42      : Parent(_reader), lp(_lp), name(_name) {}
43
44
45    /// \brief Destructor.
46    ///
47    /// Destructor for NodeSetReader.
48    virtual ~LpReader() {}
49
50  private:
51    LpReader(const LpReader&);
52    void operator=(const LpReader&);
53 
54  protected:
55
56    /// \brief Gives back true when the SectionReader can process
57    /// the section with the given header line.
58    ///
59    /// It gives back true when the header line starts with \c \@lp,
60    /// and the header line's name and the nodeset's name are the same.
61    virtual bool header(const std::string& line) {
62      std::istringstream ls(line);
63      std::string command;
64      std::string id;
65      ls >> command >> id;
66      return command == "@lp" && name == id;
67    }
68
69  private:
70
71    enum SubSection {
72      CONSTRAINTS, BOUNDS, OBJECTIVE
73    };
74
75    enum Relation {
76      LE, EQ, GE
77    };
78
79    std::istream& readConstraint(std::istream& is) {
80      LpSolverBase::Constr c;
81      char x;
82      LpSolverBase::Expr e1, e2;
83      Relation op1;
84      is >> std::ws;
85      readExpression(is, e1);
86      is >> std::ws;
87      readRelation(is, op1);
88      is >> std::ws;
89      readExpression(is, e2);
90      is >> std::ws;
91      if (!is.get(x)) {
92        if (op1 == LE) {
93          if (e1.size() == 0) {
94            c = e2 >= e1;
95          } else {
96            c = e1 <= e2;
97          }
98          c = e1 <= e2;
99        } else if (op1 == GE) {
100          if (e1.size() == 0) {
101            c = e2 <= e1;
102          } else {
103            c = e1 >= e2;
104          }
105        } else {
106          if (e1.size() == 0) {
107            c = e2 == e1;
108          } else {
109            c = e1 == e2;
110          }
111        }
112      } else {
113        is.putback(x);
114        LpSolverBase::Expr e3;
115        Relation op2;
116        readRelation(is, op2);
117        is >> std::ws;
118        readExpression(is, e3);
119        if (!e1.empty() || !e3.empty()) {
120          throw DataFormatError("Wrong range format");
121        }
122        if (op2 != op1 || op1 == EQ) {
123          throw DataFormatError("Wrong range format");
124        }
125        if (op1 == LE) {
126          c = e1.constComp() <= e2 <= e3.constComp();
127        } else {
128          c = e1.constComp() >= e2 >= e3.constComp();
129        }
130        is >> std::ws;
131        if (is.get(x)) {
132          throw DataFormatError("Wrong variable bounds format");
133        }
134      }
135      lp.addRow(c);
136      return is;
137    }
138
139    std::istream& readObjective(std::istream& is) {
140      is >> std::ws;
141      std::string sense;
142      is >> sense;
143      if (sense != "min" && sense != "max") {
144        throw DataFormatError("Wrong objective function format");
145      }
146      LpSolverBase::Expr expr;
147      is >> std::ws;
148      readExpression(is, expr);
149      lp.setObj(expr);
150      if (sense == "min") {
151        lp.min();
152      } else {
153        lp.max();
154      }
155      return is;
156    }
157
158    std::istream& readBounds(std::istream& is) {
159      LpSolverBase::Col c;
160      char x;
161      is >> std::ws;
162      if (!is.get(x)) {
163        throw DataFormatError("Wrong variable bounds format");
164      }
165      if (varFirstChar(x)) {
166        is.putback(x);
167        readCol(is, c);
168        is >> std::ws;
169        Relation op1;
170        readRelation(is, op1);
171        double v;
172        readNum(is, v);
173        if (op1 == EQ) {
174          lp.colLowerBound(c, v);
175          lp.colUpperBound(c, v);
176        } else if (op1 == LE) {
177          lp.colUpperBound(c, v);
178        } else {
179          lp.colLowerBound(c, v);
180        }
181        is >> std::ws;
182        if (is.get(x)) {
183          throw DataFormatError("Wrong variable bounds format");
184        }
185      } else {
186        is.putback(x);
187        double v;
188        readNum(is, v);
189        is >> std::ws;
190        Relation op1;
191        readRelation(is, op1);
192        is >> std::ws;
193        readCol(is, c);
194        is >> std::ws;
195        if (is.get(x)) {
196          is.putback(x);
197          is >> std::ws;
198          Relation op2;
199          readRelation(is, op2);
200          double w;
201          is >> std::ws;
202          readNum(is, w);
203          if (op2 != op1 || op1 == EQ) {
204            throw DataFormatError("Wrong range format");
205          }
206          if (op1 == LE) {
207            lp.colLowerBound(c, v);
208            lp.colUpperBound(c, w);
209          } else {
210            lp.colLowerBound(c, w);
211            lp.colUpperBound(c, v);
212          }
213          if (is.get(x)) {
214            throw DataFormatError("Wrong variable bounds format");
215          }
216        } else {
217          if (op1 == EQ) {
218            lp.colLowerBound(c, v);
219            lp.colUpperBound(c, v);
220          } else if (op1 == LE) {
221            lp.colLowerBound(c, v);
222          } else {
223            lp.colUpperBound(c, v);
224          }
225        }
226      }
227      return is;
228    }
229
230    std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
231      LpSolverBase::Col c;
232      double d;
233      char x;
234      readElement(is, c, d);
235      if (c != INVALID) {
236        e += d * c;
237      } else {
238        e += d;
239      }
240      is >> std::ws;
241      while (is.get(x) && (x == '+' || x == '-')) {
242        is >> std::ws;
243        readElement(is, c, d);
244        if (c != INVALID) {
245          e += (x == '+' ? d : -d) * c;
246        } else {
247          e += (x == '+' ? d : -d);
248        }
249        is >> std::ws;
250      }
251      if (!is) {
252        is.clear();
253      } else {
254        is.putback(x);
255      }
256      return is;
257    }
258
259    std::istream& readElement(std::istream& is,
260                              LpSolverBase::Col& c, double& d) {
261      d = 1.0;
262      c = INVALID;
263      char x, y;
264      if (!is.get(x)) throw DataFormatError("Cannot find lp element");
265      if (x == '+' || x == '-') {
266        is >> std::ws;
267        d *= x == '-' ? -1 : 1;
268        while (is.get(x) && (x == '+' || x == '-')) {
269          d *= x == '-' ? -1 : 1;
270          is >> std::ws;
271        }
272        if (!is) throw DataFormatError("Cannot find lp element");
273      }
274      if (numFirstChar(x)) {
275        is.putback(x);
276        double e;
277        readNum(is, e);
278        d *= e;
279      } else if (varFirstChar(x)) {
280        is.putback(x);
281        LpSolverBase::Col f;
282        readCol(is, f);
283        c = f;
284      } else {
285        throw DataFormatError("Invalid expression format");         
286      }
287      is >> std::ws;
288      while (is.get(y) && (y == '*' || y == '/')) {
289        is >> std::ws;
290        if (!is.get(x)) throw DataFormatError("Cannot find lp element");
291        if (x == '+' || x == '-') {
292          is >> std::ws;
293          d *= x == '-' ? -1 : 1;
294          while (is.get(x) && (x == '+' || x == '-')) {
295            d *= x == '-' ? -1 : 1;
296            is >> std::ws;
297          }
298          if (!is) throw DataFormatError("Cannot find lp element");
299        }
300        if (numFirstChar(x)) {
301          is.putback(x);
302          double e;
303          readNum(is, e);
304          if (y == '*') {
305            d *= e;
306          } else {
307            d /= e;
308          }
309        } else if (varFirstChar(x)) {
310          is.putback(x);
311          LpSolverBase::Col f;
312          readCol(is, f);
313          if (y == '*') {
314            if (c == INVALID) {
315              c = f;
316            } else {
317              throw DataFormatError("Quadratic element in expression");
318            }
319          } else {
320            throw DataFormatError("Division by variable");
321          }
322        } else {
323          throw DataFormatError("Invalid expression format");         
324        }
325        is >> std::ws;
326      }
327      if (!is) {
328        is.clear();
329      } else {
330        is.putback(y);
331      }
332      return is;
333    }
334
335    std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
336      char x;
337      std::string var;
338      while (is.get(x) && varChar(x)) {
339        var += x;
340      }
341      if (!is) {
342        is.clear();
343      } else {
344        is.putback(x);
345      }
346      ColMap::const_iterator it = cols.find(var);
347      if (cols.find(var) != cols.end()) {
348        c = it->second;
349      } else {
350        c = lp.addCol();
351        cols.insert(std::make_pair(var, c));
352        lp.colName(c, var);
353      }
354      return is;
355    }
356
357    std::istream& readNum(std::istream& is, double& d) {
358      is >> d;
359      if (!is) throw DataFormatError("Wrong number format");
360      return is;
361    }
362
363    std::istream& readRelation(std::istream& is, Relation& op) {
364      char x, y;
365      if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
366        throw DataFormatError("Wrong relation operator");
367      }
368      if (!is.get(y) || y != '=') {
369        throw DataFormatError("Wrong relation operator");
370      }
371      switch (x) {
372      case '<': op = LE;
373        break;
374      case '=': op = EQ;
375        break;
376      case '>': op = GE;
377        break;
378      }
379      return is;
380    }
381
382    static bool relationFirstChar(char c) {
383      return c == '<' || c == '=' || c == '>';
384    }
385
386    static bool varFirstChar(char c) {
387      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
388    }
389
390    static bool numFirstChar(char c) {
391      return (c >= '0' && c <= '9') || c == '.';
392    }
393
394    static bool varChar(char c) {
395      return (c >= '0' && c <= '9') ||
396        (c >= 'a' && c <= 'z') ||
397        (c >= 'A' && c <= 'Z') ||
398        c == '[' || c == ']';
399    }
400   
401  protected:
402
403    /// \brief Reader function of the section.
404    ///
405    /// It reads the content of the section.
406    virtual void read(std::istream& is) {
407      std::string line;
408      SubSection sub = CONSTRAINTS;
409      while (getline(is, line)) {
410        std::istringstream ls(line);
411        std::string type;
412        ls >> type;
413        if (type == "constraints") {
414          sub = CONSTRAINTS;
415        } else if (type == "bounds") {
416          sub = BOUNDS;
417        } else if (type == "objective") {
418          sub = OBJECTIVE;
419        } else {
420          ls.str(line);
421          switch (sub) {
422          case CONSTRAINTS:
423            readConstraint(ls);
424            break;
425          case BOUNDS:
426            readBounds(ls);
427            break;
428          case OBJECTIVE:
429            readObjective(ls);
430            break;
431          }
432        }       
433      }
434    }
435     
436    virtual void missing() {
437      ErrorMessage msg;
438      msg << "Lp section not found in file: @lp " << name;
439      throw IoParameterError(msg.message());
440    }
441
442  private:
443
444    typedef std::map<std::string, LpSolverBase::Col> ColMap;
445     
446    LpSolverBase& lp;
447    std::string name;
448    ColMap cols;
449  };
450
451
452  class LpWriter : public LemonWriter::SectionWriter {
453    typedef LemonWriter::SectionWriter Parent;
454  public:
455
456
457    /// \brief Constructor.
458    ///
459    /// Constructor for LpWriter. It creates the LpWriter and attach
460    /// it into the given LemonWriter. The lp writer will add
461    /// variables, constraints and objective function to the
462    /// given lp solver.
463    LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
464             const std::string& _name = std::string())
465      : Parent(_writer), lp(_lp), name(_name) {}
466
467
468    /// \brief Destructor.
469    ///
470    /// Destructor for NodeSetWriter.
471    virtual ~LpWriter() {}
472
473  private:
474    LpWriter(const LpWriter&);
475    void operator=(const LpWriter&);
476 
477  protected:
478
479    /// \brief Gives back true when the SectionWriter can process
480    /// the section with the given header line.
481    ///
482    /// It gives back the header line of the \c \@lp section.
483    virtual std::string header() {
484      std::ostringstream ls;
485      ls << "@lp " << name;
486      return ls.str();
487    }
488
489  private:
490
491    void createCols() {
492      int num = 1;
493
494      std::map<std::string, LpSolverBase::Col> inverse;
495
496      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
497        std::string name = lp.colName(it);
498        if (!name.empty() && inverse.find(name) == inverse.end()) {
499          cols.insert(std::make_pair(it, name));
500          inverse.insert(std::make_pair(name, it));
501        } else {
502          std::ostringstream ls;
503          ls << "var" << num;
504          ++num;
505          cols.insert(std::make_pair(it, ls.str()));
506          inverse.insert(std::make_pair(ls.str(), it));
507        }
508      }
509    }
510   
511    void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
512      bool first = true;
513      for (LpSolverBase::Expr::const_iterator jt = e.begin();
514           jt != e.end(); ++jt) {
515        if (jt->second < 0.0) {
516          os << "- ";
517          if (jt->second != -1.0) {
518            os << -jt->second << " * ";
519          }
520        } else if (jt->second > 0.0) {
521          if (!first) {
522            os << "+ ";
523          }
524          if (jt->second != 1.0) {
525            os << jt->second << " * ";
526          }         
527        }
528        first = false;
529        os << cols[jt->first] << " ";
530      }
531      if (e.constComp() < 0.0) {
532        os << "- " << -e.constComp() << " ";
533      } else if (e.constComp() > 0.0) {
534        if (!first) {
535          os << "+ ";
536        }
537        os << e.constComp() << " ";
538      }
539    }
540
541  protected:
542
543    /// \brief Writer function of the section.
544    ///
545    /// It writes the content of the section.
546    virtual void write(std::ostream& os) {
547      createCols();
548
549      os << "constraints" << std::endl;
550     
551      for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
552        double lower, upper;
553        lp.getRowBounds(it, lower, upper);
554        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
555          continue;
556        os << "   ";
557       
558        if (lower != upper) {
559          if (lower != -LpSolverBase::INF) {
560            os << lower << " <= ";
561          }
562         
563          writeExpression(os, lp.row(it));
564         
565          if (upper != LpSolverBase::INF) {
566            os << "<= " << upper << " ";
567          }
568        } else {
569
570          writeExpression(os, lp.row(it));
571          os << "== " << upper << " ";
572         
573        }
574
575        os << std::endl;
576      }
577
578      os << "bounds" << std::endl;
579     
580      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
581        double lower = lp.colLowerBound(it);
582        double upper = lp.colUpperBound(it);
583        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
584          continue;
585        os << "   ";
586
587        if (lower != upper) {
588          if (lower != -LpSolverBase::INF) {
589            os << lower << " <= ";
590          }
591         
592          os << cols[it] << " ";
593         
594          if (upper != LpSolverBase::INF) {
595            os << "<= " << upper << " ";
596          }
597        } else {
598          os << cols[it] << " == " << upper << " ";
599        }
600        os << std::endl;
601      }
602
603      os << "objective" << std::endl;
604      os << "   ";
605      if (lp.is_min()) {
606        os << "min ";
607      } else {
608        os << "max ";
609      }
610      writeExpression(os, lp.obj());
611      os << std::endl;
612    }
613     
614
615  private:
616
617    typedef std::map<LpSolverBase::Col, std::string> ColMap;
618     
619    LpSolverBase& lp;
620    std::string name;
621    ColMap cols;
622  };
623
624}
625
626#endif
Note: See TracBrowser for help on using the repository browser.