COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_utils.h @ 2363:2aabce558574

Last change on this file since 2363:2aabce558574 was 2363:2aabce558574, checked in by Balazs Dezso, 13 years ago

Changes on the LP interface

_FixId => LpId?

  • handling of not common ids soplex

LpGlpk? row and col erase bug fix

  • calling lpx_std_basis before simplex

LpSoplex?

  • added getter functions
  • better m4 file
  • integration to the tests
  • better handling of unsolved lps
File size: 18.8 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 Relation {
72      LE, EQ, GE
73    };
74
75    std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
76      char x;
77      LpSolverBase::Expr e1, e2;
78      Relation op1;
79      is >> std::ws;
80      readExpression(is, e1);
81      is >> std::ws;
82      readRelation(is, op1);
83      is >> std::ws;
84      readExpression(is, e2);
85      if (!is.get(x)) {
86        if (op1 == LE) {
87          c = e1 <= e2;
88        } else if (op1 == GE) {
89          c = e1 >= e2;
90        } else {
91          c = e1 == e2;
92        }
93      } else {
94        is.putback(x);
95        LpSolverBase::Expr e3;
96        Relation op2;
97        readRelation(is, op2);
98        is >> std::ws;
99        readExpression(is, e3);
100        if (!e1.empty() || !e3.empty()) {
101          throw DataFormatError("Wrong range format");
102        }
103        if (op2 != op1 || op1 == EQ) {
104          throw DataFormatError("Wrong range format");
105        }
106        if (op1 == LE) {
107          c = e1.constComp() <= e2 <= e3.constComp();
108        } else {
109          c = e1.constComp() >= e2 >= e3.constComp();
110        }
111      }
112    }
113
114    std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
115      LpSolverBase::Col c;
116      double d;
117      char x;
118      readElement(is, c, d);
119      if (c != INVALID) {
120        e += d * c;
121      } else {
122        e += d;
123      }
124      is >> std::ws;
125      while (is.get(x) && (x == '+' || x == '-')) {
126        is >> std::ws;
127        readElement(is, c, d);
128        if (c != INVALID) {
129          e += (x == '+' ? d : -d) * c;
130        } else {
131          e += (x == '+' ? d : -d);
132        }
133        is >> std::ws;
134      }
135      if (!is) {
136        is.clear();
137      } else {
138        is.putback(x);
139      }
140      return is;
141    }
142
143    std::istream& readElement(std::istream& is,
144                              LpSolverBase::Col& c, double& d) {
145      d = 1.0;
146      c = INVALID;
147      char x, y;
148      if (!is.get(x)) throw DataFormatError("Cannot find lp element");
149      if (x == '+' || x == '-') {
150        is >> std::ws;
151        d *= x == '-' ? -1 : 1;
152        while (is.get(x) && (x == '+' || x == '-')) {
153          d *= x == '-' ? -1 : 1;
154          is >> std::ws;
155        }
156        if (!is) throw DataFormatError("Cannot find lp element");
157      }
158      if (numFirstChar(x)) {
159        is.putback(x);
160        double e;
161        readNum(is, e);
162        d *= e;
163      } else if (varFirstChar(x)) {
164        is.putback(x);
165        LpSolverBase::Col f;
166        readCol(is, f);
167        c = f;
168      } else {
169        throw DataFormatError("Invalid expression format");         
170      }
171      is >> std::ws;
172      while (is.get(y) && (y == '*' || y == '/')) {
173        is >> std::ws;
174        if (!is.get(x)) throw DataFormatError("Cannot find lp element");
175        if (x == '+' || x == '-') {
176          is >> std::ws;
177          d *= x == '-' ? -1 : 1;
178          while (is.get(x) && (x == '+' || x == '-')) {
179            d *= x == '-' ? -1 : 1;
180            is >> std::ws;
181          }
182          if (!is) throw DataFormatError("Cannot find lp element");
183        }
184        if (numFirstChar(x)) {
185          is.putback(x);
186          double e;
187          readNum(is, e);
188          if (y == '*') {
189            d *= e;
190          } else {
191            d /= e;
192          }
193        } else if (varFirstChar(x)) {
194          is.putback(x);
195          LpSolverBase::Col f;
196          readCol(is, f);
197          if (y == '*') {
198            if (c == INVALID) {
199              c = f;
200            } else {
201              throw DataFormatError("Quadratic element in expression");
202            }
203          } else {
204            throw DataFormatError("Division by variable");
205          }
206        } else {
207          throw DataFormatError("Invalid expression format");         
208        }
209        is >> std::ws;
210      }
211      if (!is) {
212        is.clear();
213      } else {
214        is.putback(y);
215      }
216      return is;
217    }
218
219    std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
220      char x;
221      std::string var;
222      while (is.get(x) && varChar(x)) {
223        var += x;
224      }
225      if (!is) {
226        is.clear();
227      } else {
228        is.putback(x);
229      }
230      ColMap::const_iterator it = cols.find(var);
231      if (cols.find(var) != cols.end()) {
232        c = it->second;
233      } else {
234        c = lp.addCol();
235        cols.insert(std::make_pair(var, c));
236        lp.colName(c, var);
237      }
238      return is;
239    }
240
241    std::istream& readNum(std::istream& is, double& d) {
242      is >> d;
243      if (!is) throw DataFormatError("Wrong number format");
244      return is;
245    }
246
247    std::istream& readRelation(std::istream& is, Relation& op) {
248      char x, y;
249      if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
250        throw DataFormatError("Wrong relation operator");
251      }
252      if (!is.get(y) || y != '=') {
253        throw DataFormatError("Wrong relation operator");
254      }
255      switch (x) {
256      case '<': op = LE;
257        break;
258      case '=': op = EQ;
259        break;
260      case '>': op = GE;
261        break;
262      }
263      return is;
264    }
265
266    static bool relationFirstChar(char c) {
267      return c == '<' || c == '=' || c == '>';
268    }
269
270    static bool varFirstChar(char c) {
271      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
272    }
273
274    static bool numFirstChar(char c) {
275      return (c >= '0' && c <= '9') || c == '.';
276    }
277
278    static bool varChar(char c) {
279      return (c >= '0' && c <= '9') ||
280        (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
281    }
282
283
284    void addConstraint(const LpSolverBase::Constr& constr) {
285      if (constr.expr().size() != 1) {
286        lp.addRow(constr);
287      } else {
288        Lp::Expr e = constr.expr();
289        LpSolverBase::Col col = e.begin()->first;
290        double coeff = e.begin()->second;
291        double lb = LpSolverBase::NaN;
292        double ub = LpSolverBase::NaN;
293        if (coeff > 0) {
294          if (constr.upperBounded()) {
295            lb = (constr.lowerBound() - e.constComp()) / coeff;
296          }
297          if (constr.lowerBounded()) {
298            ub = (constr.upperBound() - e.constComp()) / coeff;
299          }
300        } else if (coeff < 0) {
301          if (constr.upperBounded()) {
302            lb = (constr.upperBound() - e.constComp()) / coeff;
303          }
304          if (constr.lowerBounded()) {
305            ub = (constr.lowerBound() - e.constComp()) / coeff;
306          }
307        } else {
308          lb = -LpSolverBase::INF;
309          ub = LpSolverBase::INF;
310        }
311        lp.colLowerBound(col, lb);
312        lp.colUpperBound(col, ub);
313      }
314    }
315   
316  protected:
317
318    /// \brief Reader function of the section.
319    ///
320    /// It reads the content of the section.
321    virtual void read(std::istream& is) {
322      std::string line;
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//   class LpWriter : public LemonWriter::SectionWriter {
364//     typedef LemonWriter::SectionWriter Parent;
365//   public:
366
367
368//     /// \brief Constructor.
369//     ///
370//     /// Constructor for LpWriter. It creates the LpWriter and attach
371//     /// it into the given LemonWriter. The lp writer will add
372//     /// variables, constraints and objective function to the
373//     /// given lp solver.
374//     LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
375//              const std::string& _name = std::string())
376//       : Parent(_writer), lp(_lp), name(_name) {}
377
378
379//     /// \brief Destructor.
380//     ///
381//     /// Destructor for NodeSetWriter.
382//     virtual ~LpWriter() {}
383
384//   private:
385//     LpWriter(const LpWriter&);
386//     void operator=(const LpWriter&);
387 
388//   protected:
389
390//     /// \brief Gives back true when the SectionWriter can process
391//     /// the section with the given header line.
392//     ///
393//     /// It gives back the header line of the \c \@lp section.
394//     virtual std::string header() {
395//       std::ostringstream ls(line);
396//       ls << "@lp " << name;
397//       return ls.str();
398//     }
399
400//   private:
401
402//     std::ostream& writeConstraint(std::ostream& is, LpSolverBase::Constr& c) {
403//       char x;
404
405     
406//       LpSolverBase::Expr e1, e2;
407//       Relation op1;
408//       is >> std::ws;
409//       writexpression(is, e1);
410//       is >> std::ws;
411//       writeRelation(is, op1);
412//       is >> std::ws;
413//       writexpression(is, e2);
414//       if (!is.get(x)) {
415//         if (op1 == LE) {
416//           c = e1 <= e2;
417//         } else if (op1 == GE) {
418//           c = e1 >= e2;
419//         } else {
420//           c = e1 == e2;
421//         }
422//       } else {
423//         is.putback(x);
424//         LpSolverBase::Expr e3;
425//         Relation op2;
426//         writeRelation(is, op2);
427//         is >> std::ws;
428//         writexpression(is, e3);
429//         if (!e1.empty() || !e3.empty()) {
430//           throw DataFormatError("Wrong range format");
431//         }
432//         if (op2 != op1 || op1 == EQ) {
433//           throw DataFormatError("Wrong range format");
434//         }
435//         if (op1 == LE) {
436//           c = e1.constComp() <= e2 <= e3.constComp();
437//         } else {
438//           c = e1.constComp() >= e2 >= e3.constComp();
439//         }
440//       }
441//     }
442
443//     std::ostream& writexpression(std::ostream& is, LpSolverBase::Expr& e) {
444//       LpSolverBase::Col c;
445//       double d;
446//       char x;
447//       writelement(is, c, d);
448//       if (c != INVALID) {
449//         e += d * c;
450//       } else {
451//         e += d;
452//       }
453//       is >> std::ws;
454//       while (is.get(x) && (x == '+' || x == '-')) {
455//         is >> std::ws;
456//         writelement(is, c, d);
457//         if (c != INVALID) {
458//           e += (x == '+' ? d : -d) * c;
459//         } else {
460//           e += (x == '+' ? d : -d);
461//         }
462//         is >> std::ws;
463//       }
464//       if (!is) {
465//         is.clear();
466//       } else {
467//         is.putback(x);
468//       }
469//       return is;
470//     }
471
472//     std::ostream& writelement(std::ostream& is,
473//                               LpSolverBase::Col& c, double& d) {
474//       d = 1.0;
475//       c = INVALID;
476//       char x, y;
477//       if (!is.get(x)) throw DataFormatError("Cannot find lp element");
478//       if (x == '+' || x == '-') {
479//         is >> std::ws;
480//         d *= x == '-' ? -1 : 1;
481//         while (is.get(x) && (x == '+' || x == '-')) {
482//           d *= x == '-' ? -1 : 1;
483//           is >> std::ws;
484//         }
485//         if (!is) throw DataFormatError("Cannot find lp element");
486//       }
487//       if (numFirstChar(x)) {
488//         is.putback(x);
489//         double e;
490//         writeNum(is, e);
491//         d *= e;
492//       } else if (varFirstChar(x)) {
493//         is.putback(x);
494//         LpSolverBase::Col f;
495//         writeCol(is, f);
496//         c = f;
497//       } else {
498//         throw DataFormatError("Invalid expression format");         
499//       }
500//       is >> std::ws;
501//       while (is.get(y) && (y == '*' || y == '/')) {
502//         is >> std::ws;
503//         if (!is.get(x)) throw DataFormatError("Cannot find lp element");
504//         if (x == '+' || x == '-') {
505//           is >> std::ws;
506//           d *= x == '-' ? -1 : 1;
507//           while (is.get(x) && (x == '+' || x == '-')) {
508//             d *= x == '-' ? -1 : 1;
509//             is >> std::ws;
510//           }
511//           if (!is) throw DataFormatError("Cannot find lp element");
512//         }
513//         if (numFirstChar(x)) {
514//           is.putback(x);
515//           double e;
516//           writeNum(is, e);
517//           if (y == '*') {
518//             d *= e;
519//           } else {
520//             d /= e;
521//           }
522//         } else if (varFirstChar(x)) {
523//           is.putback(x);
524//           LpSolverBase::Col f;
525//           writeCol(is, f);
526//           if (y == '*') {
527//             if (c == INVALID) {
528//               c = f;
529//             } else {
530//               throw DataFormatError("Quadratic element in expression");
531//             }
532//           } else {
533//             throw DataFormatError("Division by variable");
534//           }
535//         } else {
536//           throw DataFormatError("Invalid expression format");         
537//         }
538//         is >> std::ws;
539//       }
540//       if (!is) {
541//         is.clear();
542//       } else {
543//         is.putback(y);
544//       }
545//       return is;
546//     }
547
548//     std::ostream& writeCol(std::ostream& is, LpSolverBase::Col& c) {
549//       char x;
550//       std::string var;
551//       while (is.get(x) && varChar(x)) {
552//         var += x;
553//       }
554//       if (!is) {
555//         is.clear();
556//       } else {
557//         is.putback(x);
558//       }
559//       ColMap::const_iterator it = cols.find(var);
560//       if (cols.find(var) != cols.end()) {
561//         c = it->second;
562//       } else {
563//         c = lp.addCol();
564//         cols.insert(std::make_pair(var, c));
565//         lp.colName(c, var);
566//       }
567//       return is;
568//     }
569
570//     std::ostream& writeNum(std::ostream& is, double& d) {
571//       is >> d;
572//       if (!is) throw DataFormatError("Wrong number format");
573//       return is;
574//     }
575
576//     std::ostream& writeRelation(std::ostream& is, Relation& op) {
577//       char x, y;
578//       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
579//         throw DataFormatError("Wrong relation operator");
580//       }
581//       if (!is.get(y) || y != '=') {
582//         throw DataFormatError("Wrong relation operator");
583//       }
584//       switch (x) {
585//       case '<': op = LE;
586//         break;
587//       case '=': op = EQ;
588//         break;
589//       case '>': op = GE;
590//         break;
591//       }
592//       return is;
593//     }
594
595//     static bool relationFirstChar(char c) {
596//       return c == '<' || c == '=' || c == '>';
597//     }
598
599//     static bool varFirstChar(char c) {
600//       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
601//     }
602
603//     static bool numFirstChar(char c) {
604//       return (c >= '0' && c <= '9') || c == '.';
605//     }
606
607//     static bool varChar(char c) {
608//       return (c >= '0' && c <= '9') ||
609//         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
610//     }
611
612
613//     void addConstraint(const LpSolverBase::Constr& constr) {
614//       if (constr.expr().size() != 1) {
615//         lp.addRow(constr);
616//       } else {
617//         Lp::Expr e = constr.expr();
618//         LpSolverBase::Col col = e.begin()->first;
619//         double coeff = e.begin()->second;
620//         double lb = LpSolverBase::NaN;
621//         double ub = LpSolverBase::NaN;
622//         if (coeff > 0) {
623//           if (constr.upperBounded()) {
624//             lb = (constr.lowerBound() - e.constComp()) / coeff;
625//           }
626//           if (constr.lowerBounded()) {
627//             ub = (constr.upperBound() - e.constComp()) / coeff;
628//           }
629//         } else if (coeff < 0) {
630//           if (constr.upperBounded()) {
631//             lb = (constr.upperBound() - e.constComp()) / coeff;
632//           }
633//           if (constr.lowerBounded()) {
634//             ub = (constr.lowerBound() - e.constComp()) / coeff;
635//           }
636//         } else {
637//           lb = -LpSolverBase::INF;
638//           ub = LpSolverBase::INF;
639//         }
640//         lp.colLowerBound(col, lb);
641//         lp.colUpperBound(col, ub);
642//       }
643//     }
644   
645//   protected:
646
647//     /// \brief Writer function of the section.
648//     ///
649//     /// It writes the content of the section.
650//     virtual void write(std::ostream& is) {
651//       std::string line;
652//       std::map<std::string, LpSolverBase::Col> vars;
653//       while (getline(is, line)) {
654//         std::istringstream ls(line);
655//         std::string sense;
656//         ls >> sense;
657//         if (sense == "min" || sense == "max") {
658//           LpSolverBase::Expr expr;
659//           ls >> std::ws;
660//           writeExpression(ls, expr);
661//           lp.setObj(expr);
662//           if (sense == "min") {
663//             lp.min();
664//           } else {
665//             lp.max();
666//           }
667//         } else {
668//           ls.str(line);
669//           LpSolverBase::Constr constr;
670//           ls >> std::ws;
671//           writeConstraint(ls, constr);
672//           addConstraint(constr);
673//         }       
674//       }
675//     }
676     
677//     virtual void missing() {
678//       ErrorMessage msg;
679//       msg << "Lp section not found in file: @lp " << name;
680//       throw IoParameterError(msg.message());
681//     }
682
683//   private:
684
685//     typedef std::map<std::string, LpSolverBase::Col> ColMap;
686     
687//     LpSolverBase& lp;
688//     std::string name;
689//     ColMap cols;
690//   };
691
692}
693
694#endif
Note: See TracBrowser for help on using the repository browser.