COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_utils.h

Last change on this file was 2578:979a0b389f84, checked in by Akos Ladanyi, 12 years ago

Put the definitions of global functions into a .cc file.

File size: 24.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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
27#include <map>
28#include <set>
29
30
31namespace lemon {
32
33  /// \ingroup lp_utils
34  ///
35  /// \brief The map for the result of the lp variables.
36  ///
37  /// The map for the result of the lp variables.
38  class LpResultMap {
39  public:
40    typedef LpSolverBase::Col Key;
41    typedef LpSolverBase::Value Value;
42
43    /// \brief Constructor
44    ///
45    /// Constructor
46    LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
47    LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
48      return lp.primal(col);
49    }
50  private:
51    const LpSolverBase& lp;
52  };
53
54  /// \ingroup lp_utils
55  ///
56  /// \brief Returns an \ref LpResultMap class
57  ///
58  /// This function just returns an \ref LpResultMap class.
59  /// \relates LpResultMap
60  LpResultMap lpResultMap(const LpSolverBase& lp);
61
62  /// \ingroup lp_utils
63  ///
64  /// \brief The map for the name of the lp variables.
65  ///
66  /// The map for the name of the lp variables.
67  class LpColNameMap {
68  public:
69    typedef LpSolverBase::Col Key;
70    typedef std::string Value;
71
72    /// \brief Constructor
73    ///
74    /// Constructor
75    LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
76    std::string operator[](const LpSolverBase::Col col) const {
77      return lp.colName(col);
78    }
79  private:
80    const LpSolverBase& lp;
81  };
82
83  /// \ingroup lp_utils
84  ///
85  /// \brief Writeable map for the name of the lp variables.
86  ///
87  /// Writeable map for the name of the lp variables.
88  class LpColNameWriteMap {
89  public:
90    typedef LpSolverBase::Col Key;
91    typedef std::string Value;
92
93    /// \brief Constructor
94    ///
95    /// Constructor
96    LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
97    std::string operator[](const LpSolverBase::Col col) const {
98      return lp.colName(col);
99    }
100    void set(const LpSolverBase::Col col, const std::string& name) {
101      lp.colName(col, name);
102    }
103  private:
104    LpSolverBase& lp;
105  };
106
107  /// \ingroup lp_utils
108  ///
109  /// \brief Returns an \ref LpColNameMap class
110  ///
111  /// This function just returns an \ref LpColNameMap class.
112  /// \relates LpColNameMap
113  LpColNameMap lpColNameMap(const LpSolverBase& lp);
114
115  LpColNameWriteMap lpColNameMap(LpSolverBase& lp);
116
117  /// \ingroup lp_utils
118  ///
119  /// \brief Lp variable item reader for Lemon IO
120  ///
121  /// This class is an Lp variable item reader for Lemon IO. It makes
122  /// possible to store lp variables in lemon file. The usage of this
123  /// class is very simple:
124  ///
125  ///\code
126  /// Graph graph;
127  /// Lp lp;
128  /// Graph::EdgeMap<Lp::Col> var(graph);
129  ///
130  /// GraphReader<Graph> reader(cin, graph);
131  /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
132  /// reader.run();
133  ///\endcode
134  ///
135  /// If there is already a variable with the same name in the lp then
136  /// it will be used for the return value. If there is no such variable
137  /// then it will be constructed. The file could contain \c '-' as value
138  /// which means that no lp variable associated to the current item and
139  /// in this case INVALID will be returned.
140  class LpColReader {
141  public:
142
143    /// \brief The value type of reader.
144    ///
145    /// The value type of reader.
146    typedef LpSolverBase::Col Value;
147
148    /// \brief Constructor for the reader.
149    ///
150    /// Constructor for the reader.
151    LpColReader(LpSolverBase& _lp) : lp(_lp) {}
152
153    /// \brief Reads an lp variable from the given stream.
154    ///
155    /// Reads an lp variable string from the given stream.
156    void read(std::istream& is, LpSolverBase::Col& col) const {
157      char x;
158      is >> std::ws;
159      if (!is.get(x))
160        throw DataFormatError("Wrong Lp Column format!");
161      if (varFirstChar(x)) {
162        std::string var;
163        var += x;
164       
165        while (is.get(x) && varChar(x)) {
166          var += x;
167        }
168        if (!is) {
169          is.clear();
170        } else {
171          is.putback(x);
172        }
173        col = lp.colByName(var);
174        if (col == INVALID) {
175          col = lp.addCol();
176          lp.colName(col, var);
177        }
178      } else if (x == '-') {
179        col = INVALID;
180        is >> std::ws;
181      } else {
182        std::cerr << x << std::endl;
183        throw DataFormatError("Wrong Lp Column format");
184      }
185    }
186
187  private:
188
189    static bool varFirstChar(char c) {
190      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
191    }
192
193    static bool varChar(char c) {
194      return (c >= '0' && c <= '9') ||
195        (c >= 'a' && c <= 'z') ||
196        (c >= 'A' && c <= 'Z') ||
197        c == '[' || c == ']';
198    }
199   
200    LpSolverBase& lp;
201
202  };
203
204  /// \ingroup lp_utils
205  ///
206  /// \brief Lp variable item writer for Lemon IO
207  ///
208  /// This class is an Lp variable item writer for Lemon IO. It makes
209  /// possible to store lp variables in lemon file. The usage of this
210  /// class is very simple:
211  ///
212  ///\code
213  /// Graph graph;
214  /// Lp lp;
215  /// Graph::EdgeMap<Lp::Col> var(graph);
216  ///
217  /// GraphWriter<Graph> writer(cin, graph);
218  /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
219  /// writer.run();
220  ///\endcode
221  ///
222  /// If there is no name associated to the current item then the name
223  /// will automatically constructed. If the value is INVALID then it
224  /// will write an \c '-' value to the file.
225  class LpColWriter {
226  public:
227
228    /// \brief The value type of writer.
229    ///
230    /// The value type of writer.
231    typedef LpSolverBase::Col Value;
232
233    /// \brief Constructor for the writer.
234    ///
235    /// Constructor for the writer.
236    LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
237
238    /// \brief Writes an lp variable to the given stream.
239    ///
240    /// Writes an lp variable to the given stream.
241    void write(std::ostream& os, const LpSolverBase::Col& col) const {
242      if (col != INVALID) {
243        std::string name = lp.colName(col);
244        if (name.empty()) {
245          std::ostringstream ls;
246          ls << "x" << num;
247          ++num;
248          while (lp.colByName(ls.str()) != INVALID) {
249            ls.str(std::string());
250            ls << "x" << num;
251            ++num;
252          }
253          const_cast<LpSolverBase&>(lp).colName(col, ls.str());
254          os << ls.str();
255        } else {
256          os << name;
257        }
258      } else {
259        os << "-";
260      }
261    }
262
263  private:
264
265    const LpSolverBase& lp;
266    mutable int num;
267
268  };
269
270  /// \ingroup lp_utils
271  ///
272  /// \brief Lp section reader for lemon IO
273  ///
274  /// This section reader provides an easy way to read an Lp problem
275  /// from a file. The lemon lp section format contains three parts.
276  ///
277  ///\code
278  /// @lp
279  /// constraints
280  ///   7 == x1 - 1 * x2
281  ///   2 * x1 + x3 / 2 <= 7
282  ///   x2 + -3 * x3 >= 8
283  ///   3 <= x2 - 2 * x1 <= 8
284  /// bounds
285  ///   x1 >= 3
286  ///   2 <= x2 <= 5
287  ///   0 <= x3 <= 8
288  /// objective
289  ///   min x1 + 2 * x2 - x3
290  ///\endcode
291  ///
292  /// The first part gives the constraints to the lp. The constraints
293  /// could be equality, lower bound, upper bound or range for an
294  /// expression or equality, less or more for two expressions.
295  ///
296  /// The second part gives the bounds for the variables. The bounds
297  /// could be the same as for the single expression so equality,
298  /// lower bound, upper bound or range.
299  ///
300  /// The third part is the objective function, it should start with
301  /// \c min or \c max and then a valid linear expression.
302  ///
303  /// The reader constructs automatically the variable for a name if
304  /// there is not already a variable with the same name.
305  ///
306  /// The basic way to read an LP problem is made by the next code:
307  ///\code
308  /// Lp lp;
309  ///
310  /// LemonReader reader(filename_or_istream);
311  /// LpReader lpreader(reader, lp);
312  ///
313  /// reader.run();
314  ///\endcode
315  ///
316  /// Of course instead of \c LemonReader you can give a \c
317  /// GraphReader to the LpReader constructor. Also useful that you
318  /// can mix lp problems and graphs in the same file.
319  class LpReader : public LemonReader::SectionReader {
320    typedef LemonReader::SectionReader Parent;
321  public:
322
323
324    /// \brief Constructor.
325    ///
326    /// Constructor for LpReader. It creates the LpReader and attachs
327    /// it into the given LemonReader. The lp reader will add
328    /// variables, constraints and objective function to the
329    /// given lp solver.
330    LpReader(LemonReader& _reader, LpSolverBase& _lp,
331             const std::string& _name = std::string())
332      : Parent(_reader), lp(_lp), name(_name) {}
333
334
335    /// \brief Destructor.
336    ///
337    /// Destructor for LpReader.
338    virtual ~LpReader() {}
339
340  private:
341    LpReader(const LpReader&);
342    void operator=(const LpReader&);
343 
344  protected:
345
346    /// \brief Gives back true when the SectionReader can process
347    /// the section with the given header line.
348    ///
349    /// It gives back true when the header line starts with \c \@lp,
350    /// and the header line's name and the nodeset's name are the same.
351    virtual bool header(const std::string& line) {
352      std::istringstream ls(line);
353      std::string command;
354      std::string id;
355      ls >> command >> id;
356      return command == "@lp" && name == id;
357    }
358
359  private:
360
361    enum Part {
362      CONSTRAINTS, BOUNDS, OBJECTIVE
363    };
364
365    enum Relation {
366      LE, EQ, GE
367    };
368
369    std::istream& readConstraint(std::istream& is) {
370      LpSolverBase::Constr c;
371      char x;
372      LpSolverBase::Expr e1, e2;
373      Relation op1;
374      is >> std::ws;
375      readExpression(is, e1);
376      is >> std::ws;
377      readRelation(is, op1);
378      is >> std::ws;
379      readExpression(is, e2);
380      is >> std::ws;
381      if (!is.get(x)) {
382        if (op1 == LE) {
383          if (e1.size() == 0) {
384            c = e2 >= e1;
385          } else {
386            c = e1 <= e2;
387          }
388          c = e1 <= e2;
389        } else if (op1 == GE) {
390          if (e1.size() == 0) {
391            c = e2 <= e1;
392          } else {
393            c = e1 >= e2;
394          }
395        } else {
396          if (e1.size() == 0) {
397            c = e2 == e1;
398          } else {
399            c = e1 == e2;
400          }
401        }
402      } else {
403        is.putback(x);
404        LpSolverBase::Expr e3;
405        Relation op2;
406        readRelation(is, op2);
407        is >> std::ws;
408        readExpression(is, e3);
409        if (!e1.empty() || !e3.empty()) {
410          throw DataFormatError("Wrong range format");
411        }
412        if (op2 != op1 || op1 == EQ) {
413          throw DataFormatError("Wrong range format");
414        }
415        if (op1 == LE) {
416          c = e1.constComp() <= e2 <= e3.constComp();
417        } else {
418          c = e1.constComp() >= e2 >= e3.constComp();
419        }
420        is >> std::ws;
421        if (is.get(x)) {
422          throw DataFormatError("Wrong variable bounds format");
423        }
424      }
425      lp.addRow(c);
426      return is;
427    }
428
429    std::istream& readObjective(std::istream& is) {
430      is >> std::ws;
431      std::string sense;
432      is >> sense;
433      if (sense != "min" && sense != "max") {
434        throw DataFormatError("Wrong objective function format");
435      }
436      LpSolverBase::Expr expr;
437      is >> std::ws;
438      readExpression(is, expr);
439      lp.obj(expr);
440      if (sense == "min") {
441        lp.min();
442      } else {
443        lp.max();
444      }
445      return is;
446    }
447
448    std::istream& readBounds(std::istream& is) {
449      LpSolverBase::Col c;
450      char x;
451      is >> std::ws;
452      if (!is.get(x)) {
453        throw DataFormatError("Wrong variable bounds format");
454      }
455      if (varFirstChar(x)) {
456        is.putback(x);
457        readCol(is, c);
458        is >> std::ws;
459        Relation op1;
460        readRelation(is, op1);
461        double v;
462        readNum(is, v);
463        if (op1 == EQ) {
464          lp.colLowerBound(c, v);
465          lp.colUpperBound(c, v);
466        } else if (op1 == LE) {
467          lp.colUpperBound(c, v);
468        } else {
469          lp.colLowerBound(c, v);
470        }
471        is >> std::ws;
472        if (is.get(x)) {
473          throw DataFormatError("Wrong variable bounds format");
474        }
475      } else {
476        is.putback(x);
477        double v;
478        readNum(is, v);
479        is >> std::ws;
480        Relation op1;
481        readRelation(is, op1);
482        is >> std::ws;
483        readCol(is, c);
484        is >> std::ws;
485        if (is.get(x)) {
486          is.putback(x);
487          is >> std::ws;
488          Relation op2;
489          readRelation(is, op2);
490          double w;
491          is >> std::ws;
492          readNum(is, w);
493          if (op2 != op1 || op1 == EQ) {
494            throw DataFormatError("Wrong range format");
495          }
496          if (op1 == LE) {
497            lp.colLowerBound(c, v);
498            lp.colUpperBound(c, w);
499          } else {
500            lp.colLowerBound(c, w);
501            lp.colUpperBound(c, v);
502          }
503          is >> std::ws;
504          if (is.get(x)) {
505            throw DataFormatError("Wrong variable bounds format");
506          }
507        } else {
508          if (op1 == EQ) {
509            lp.colLowerBound(c, v);
510            lp.colUpperBound(c, v);
511          } else if (op1 == LE) {
512            lp.colLowerBound(c, v);
513          } else {
514            lp.colUpperBound(c, v);
515          }
516        }
517      }
518      return is;
519    }
520
521    std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
522      LpSolverBase::Col c;
523      double d;
524      char x;
525      readElement(is, c, d);
526      if (c != INVALID) {
527        e += d * c;
528      } else {
529        e += d;
530      }
531      is >> std::ws;
532      while (is.get(x) && (x == '+' || x == '-')) {
533        is >> std::ws;
534        readElement(is, c, d);
535        if (c != INVALID) {
536          e += (x == '+' ? d : -d) * c;
537        } else {
538          e += (x == '+' ? d : -d);
539        }
540        is >> std::ws;
541      }
542      if (!is) {
543        is.clear();
544      } else {
545        is.putback(x);
546      }
547      return is;
548    }
549
550    std::istream& readElement(std::istream& is,
551                              LpSolverBase::Col& c, double& d) {
552      d = 1.0;
553      c = INVALID;
554      char x, y;
555      if (!is.get(x)) throw DataFormatError("Cannot find lp element");
556      if (x == '+' || x == '-') {
557        is >> std::ws;
558        d *= x == '-' ? -1 : 1;
559        while (is.get(x) && (x == '+' || x == '-')) {
560          d *= x == '-' ? -1 : 1;
561          is >> std::ws;
562        }
563        if (!is) throw DataFormatError("Cannot find lp element");
564      }
565      if (numFirstChar(x)) {
566        is.putback(x);
567        double e;
568        readNum(is, e);
569        d *= e;
570      } else if (varFirstChar(x)) {
571        is.putback(x);
572        LpSolverBase::Col f;
573        readCol(is, f);
574        c = f;
575      } else {
576        throw DataFormatError("Invalid expression format");         
577      }
578      is >> std::ws;
579      while (is.get(y) && (y == '*' || y == '/')) {
580        is >> std::ws;
581        if (!is.get(x)) throw DataFormatError("Cannot find lp element");
582        if (x == '+' || x == '-') {
583          is >> std::ws;
584          d *= x == '-' ? -1 : 1;
585          while (is.get(x) && (x == '+' || x == '-')) {
586            d *= x == '-' ? -1 : 1;
587            is >> std::ws;
588          }
589          if (!is) throw DataFormatError("Cannot find lp element");
590        }
591        if (numFirstChar(x)) {
592          is.putback(x);
593          double e;
594          readNum(is, e);
595          if (y == '*') {
596            d *= e;
597          } else {
598            d /= e;
599          }
600        } else if (varFirstChar(x)) {
601          is.putback(x);
602          LpSolverBase::Col f;
603          readCol(is, f);
604          if (y == '*') {
605            if (c == INVALID) {
606              c = f;
607            } else {
608              throw DataFormatError("Quadratic element in expression");
609            }
610          } else {
611            throw DataFormatError("Division by variable");
612          }
613        } else {
614          throw DataFormatError("Invalid expression format");         
615        }
616        is >> std::ws;
617      }
618      if (!is) {
619        is.clear();
620      } else {
621        is.putback(y);
622      }
623      return is;
624    }
625
626    std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
627      char x;
628      std::string var;
629      while (is.get(x) && varChar(x)) {
630        var += x;
631      }
632      if (!is) {
633        is.clear();
634      } else {
635        is.putback(x);
636      }
637      c = lp.colByName(var);
638      if (c == INVALID) {
639        c = lp.addCol();
640        lp.colName(c, var);
641      }
642      return is;
643    }
644
645    std::istream& readNum(std::istream& is, double& d) {
646      is >> d;
647      if (!is) throw DataFormatError("Wrong number format");
648      return is;
649    }
650
651    std::istream& readRelation(std::istream& is, Relation& op) {
652      char x, y;
653      if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
654        throw DataFormatError("Wrong relation operator");
655      }
656      if (!is.get(y) || y != '=') {
657        throw DataFormatError("Wrong relation operator");
658      }
659      switch (x) {
660      case '<': op = LE;
661        break;
662      case '=': op = EQ;
663        break;
664      case '>': op = GE;
665        break;
666      }
667      return is;
668    }
669
670    static bool relationFirstChar(char c) {
671      return c == '<' || c == '=' || c == '>';
672    }
673
674    static bool varFirstChar(char c) {
675      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
676    }
677
678    static bool numFirstChar(char c) {
679      return (c >= '0' && c <= '9') || c == '.';
680    }
681   
682    static bool varChar(char c) {
683      return (c >= '0' && c <= '9') ||
684        (c >= 'a' && c <= 'z') ||
685        (c >= 'A' && c <= 'Z') ||
686        c == '[' || c == ']';
687    }
688   
689  protected:
690
691    /// \brief Reader function of the section.
692    ///
693    /// It reads the content of the section.
694    virtual void read(std::istream& is) {
695      std::string line;
696      Part part = CONSTRAINTS;
697      while (getline(is, line)) {
698        std::istringstream ls(line);
699        std::string type;
700        ls >> type;
701        if (type == "constraints") {
702          part = CONSTRAINTS;
703          ls >> std::ws;
704          char x;
705          if (ls.get(x))
706            throw DataFormatError("Wrong Lp format");
707        } else if (type == "bounds") {
708          part = BOUNDS;
709          ls >> std::ws;
710          char x;
711          if (ls.get(x))
712            throw DataFormatError("Wrong Lp format");
713        } else if (type == "objective") {
714          part = OBJECTIVE;
715          ls >> std::ws;
716          char x;
717          if (ls.get(x))
718            throw DataFormatError("Wrong Lp format");
719        } else {
720          ls.str(line);
721          switch (part) {
722          case CONSTRAINTS:
723            readConstraint(ls);
724            break;
725          case BOUNDS:
726            readBounds(ls);
727            break;
728          case OBJECTIVE:
729            readObjective(ls);
730            break;
731          }
732        }
733      }
734    }
735     
736    virtual void missing() {
737      ErrorMessage msg;
738      msg << "Lp section not found in file: @lp " << name;
739      throw IoParameterError(msg.message());
740    }
741
742  private:
743
744     
745    LpSolverBase& lp;
746    std::string name;
747  };
748
749
750  /// \ingroup lp_utils
751  ///
752  /// \brief Lp section writer for lemon IO
753  ///
754  /// This section reader provides an easy way to write an Lp problem
755  /// to a file. The lemon lp section format contains three parts.
756  ///
757  ///\code
758  /// @lp
759  /// constraints
760  ///   7 == x1 - 1 * x2
761  ///   2 * x1 + x3 / 2 <= 7
762  ///   x2 + -3 * x3 >= 8
763  ///   3 <= x2 - 2 * x1 <= 8
764  /// bounds
765  ///   x1 >= 3
766  ///   2 <= x2 <= 5
767  ///   0 <= x3 <= 8
768  /// objective
769  ///   min x1 + 2 * x2 - x3
770  ///\endcode
771  ///
772  /// The first part gives the constraints to the lp. The constraints
773  /// could be equality, lower bound, upper bound or range for an
774  /// expression or equality, less or more for two expressions.
775  ///
776  /// The second part gives the bounds for the variables. The bounds
777  /// could be the same as for the single expression so equality,
778  /// lower bound, upper bound or range.
779  ///
780  /// The third part is the objective function, it should start with
781  /// \c min or \c max and then a valid linear expression.
782  ///
783  /// If an LP variable does not have name in the writer, then it will
784  /// automatically created in the writer. This make a slight change
785  /// in the \c const variable.
786  ///
787  /// The basic way to write an LP problem is made by the next code:
788  ///\code
789  /// Lp lp;
790  ///
791  /// LemonWriter writer(filename_or_ostream);
792  /// LpWriter lpwriter(writer, lp);
793  ///
794  /// writer.run();
795  ///\endcode
796  ///
797  /// Of course instead of \c LemonWriter you can give a \c
798  /// GraphWriter to the LpWriter constructor. Also useful that you
799  /// can mix lp problems and graphs in the same file.
800  class LpWriter : public LemonWriter::SectionWriter {
801    typedef LemonWriter::SectionWriter Parent;
802  public:
803
804
805    /// \brief Constructor.
806    ///
807    /// Constructor for LpWriter. It creates the LpWriter and attach
808    /// it into the given LemonWriter.
809    LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
810             const std::string& _name = std::string())
811      : Parent(_writer), lp(_lp), name(_name) {}
812
813
814    /// \brief Destructor.
815    ///
816    /// Destructor for LpWriter.
817    virtual ~LpWriter() {}
818
819  private:
820    LpWriter(const LpWriter&);
821    void operator=(const LpWriter&);
822 
823  protected:
824
825    /// \brief Gives back true when the SectionWriter can process
826    /// the section with the given header line.
827    ///
828    /// It gives back the header line of the \c \@lp section.
829    virtual std::string header() {
830      std::ostringstream ls;
831      ls << "@lp " << name;
832      return ls.str();
833    }
834
835  private:
836
837    void createCols() {
838      int num = 0;
839
840      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
841        std::string name = lp.colName(it);
842        if (name.empty()) {
843          std::ostringstream ls;
844          ls << "x" << num;
845          ++num;
846          while (lp.colByName(ls.str()) != INVALID) {
847            ls.str(std::string());
848            ls << "x" << num;
849            ++num;
850          }
851          const_cast<LpSolverBase&>(lp).colName(it, ls.str());
852        }
853      }
854    }
855   
856    void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
857      bool first = true;
858      for (LpSolverBase::Expr::const_iterator jt = e.begin();
859           jt != e.end(); ++jt) {
860        if (jt->second < 0.0) {
861          os << "- ";
862          if (jt->second != -1.0) {
863            os << -jt->second << " * ";
864          }
865        } else if (jt->second > 0.0) {
866          if (!first) {
867            os << "+ ";
868          }
869          if (jt->second != 1.0) {
870            os << jt->second << " * ";
871          }         
872        }
873        first = false;
874        os << lp.colName(jt->first) << " ";
875      }
876      if (e.constComp() < 0.0) {
877        os << "- " << -e.constComp() << " ";
878      } else if (e.constComp() > 0.0) {
879        if (!first) {
880          os << "+ ";
881        }
882        os << e.constComp() << " ";
883      }
884      if (e.begin() == e.end() && e.constComp() == 0.0) {
885        os << "0 ";
886      }
887    }
888
889  protected:
890
891    /// \brief Writer function of the section.
892    ///
893    /// It writes the content of the section.
894    virtual void write(std::ostream& os) {
895      createCols();
896
897      os << "constraints" << std::endl;
898     
899      for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
900        double lower, upper;
901        lp.getRowBounds(it, lower, upper);
902        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
903          continue;
904        os << "   ";
905       
906        if (lower != upper) {
907          if (lower != -LpSolverBase::INF) {
908            os << lower << " <= ";
909          }
910         
911          writeExpression(os, lp.row(it));
912         
913          if (upper != LpSolverBase::INF) {
914            os << "<= " << upper << " ";
915          }
916        } else {
917
918          writeExpression(os, lp.row(it));
919          os << "== " << upper << " ";
920         
921        }
922
923        os << std::endl;
924      }
925
926      os << "bounds" << std::endl;
927     
928      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
929        double lower = lp.colLowerBound(it);
930        double upper = lp.colUpperBound(it);
931        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
932          continue;
933        os << "   ";
934
935        if (lower != upper) {
936          if (lower != -LpSolverBase::INF) {
937            os << lower << " <= ";
938          }
939         
940          os << lp.colName(it) << " ";
941         
942          if (upper != LpSolverBase::INF) {
943            os << "<= " << upper << " ";
944          }
945        } else {
946          os << lp.colName(it) << " == " << upper << " ";
947        }
948        os << std::endl;
949      }
950
951      os << "objective" << std::endl;
952      os << "   ";
953      if (lp.isMin()) {
954        os << "min ";
955      } else {
956        os << "max ";
957      }
958      writeExpression(os, lp.obj());
959      os << std::endl;
960    }
961     
962
963  private:
964
965    const LpSolverBase& lp;
966    std::string name;
967  };
968
969}
970
971#endif
Note: See TracBrowser for help on using the repository browser.