COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_utils.h @ 2401:7f20ec638bc2

Last change on this file since 2401:7f20ec638bc2 was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

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