COIN-OR::LEMON - Graph Library

Changeset 2368:6b2e8b734ae7 in lemon-0.x for lemon/lp_utils.h


Ignore:
Timestamp:
02/19/07 13:11:41 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3183
Message:

Bug fixes
Documentation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_utils.h

    r2364 r2368  
    2525#include <lemon/lemon_writer.h>
    2626
     27#include <map>
     28#include <set>
     29
     30
    2731namespace lemon {
    2832
     33  /// \ingroup gen_opt_tools
     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 gen_opt_tools
     55  ///
     56  /// \brief The map for the name of the lp variables.
     57  ///
     58  /// The map for the name of the lp variables.
     59  class LpColNameMap {
     60  public:
     61    typedef LpSolverBase::Col Key;
     62    typedef std::string Value;
     63
     64    /// \brief Constructor
     65    ///
     66    /// Constructor
     67    LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
     68    std::string operator[](const LpSolverBase::Col col) const {
     69      return lp.colName(col);
     70    }
     71  private:
     72    const LpSolverBase& lp;
     73  };
     74
     75  /// \ingroup gen_opt_tools
     76  ///
     77  /// \brief Writeable map for the name of the lp variables.
     78  ///
     79  /// Writeable map for the name of the lp variables.
     80  class LpColNameWriteMap {
     81  public:
     82    typedef LpSolverBase::Col Key;
     83    typedef std::string Value;
     84
     85    /// \brief Constructor
     86    ///
     87    /// Constructor
     88    LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
     89    std::string operator[](const LpSolverBase::Col col) const {
     90      return lp.colName(col);
     91    }
     92    void set(const LpSolverBase::Col col, const std::string& name) {
     93      lp.colName(col, name);
     94    }
     95  private:
     96    LpSolverBase& lp;
     97  };
     98
     99  /// \ingroup gen_opt_tools
     100  ///
     101  /// \brief Returns an \ref LpColNameMap class
     102  ///
     103  /// This function just returns an \ref LpColNameMap class.
     104  /// \relates LpColNameMap
     105  LpColNameMap lpColNameMap(const LpSolverBase& lp) {
     106    return LpColNameMap(lp);
     107  }
     108
     109  LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
     110    return LpColNameWriteMap(lp);
     111  }
     112
     113  /// \ingroup gen_opt_tools
     114  ///
     115  /// \brief Lp variable item reader for Lemon IO
     116  ///
     117  /// This class is an Lp variable item reader for Lemon IO. It makes
     118  /// possible to store lp variables in lemon file. The usage of this
     119  /// class is very simple:
     120  ///
     121  ///\code
     122  /// Graph graph;
     123  /// Lp lp;
     124  /// Graph::EdgeMap<Lp::Col> var(graph);
     125  ///
     126  /// GraphReader<Graph> reader(cin, graph);
     127  /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
     128  /// reader.run();
     129  ///\endcode
     130  ///
     131  /// If there is already a variable with the same name in the lp then
     132  /// it will be used for the return value. If there is no such variable
     133  /// then it will be constructed. The file could contain \c '-' as value
     134  /// which means that no lp variable associated to the current item and
     135  /// in this case INVALID will be returned.
     136  class LpColReader {
     137  public:
     138
     139    /// \brief The value type of reader.
     140    ///
     141    /// The value type of reader.
     142    typedef LpSolverBase::Col Value;
     143
     144    /// \brief Constructor for the reader.
     145    ///
     146    /// Constructor for the reader.
     147    LpColReader(LpSolverBase& _lp) : lp(_lp) {}
     148
     149    /// \brief Reads an lp variable from the given stream.
     150    ///
     151    /// Reads an lp variable string from the given stream.
     152    void read(std::istream& is, LpSolverBase::Col& col) const {
     153      char x;
     154      is >> std::ws;
     155      if (!is.get(x))
     156        throw DataFormatError("Wrong Lp Column format!");
     157      if (varFirstChar(x)) {
     158        std::string var;
     159        var += x;
     160       
     161        while (is.get(x) && varChar(x)) {
     162          var += x;
     163        }
     164        if (!is) {
     165          is.clear();
     166        } else {
     167          is.putback(x);
     168        }
     169        col = lp.colByName(var);
     170        if (col == INVALID) {
     171          col = lp.addCol();
     172          lp.colName(col, var);
     173        }
     174      } else if (x == '-') {
     175        col = INVALID;
     176        is >> std::ws;
     177      } else {
     178        std::cerr << x << std::endl;
     179        throw DataFormatError("Wrong Lp Column format");
     180      }
     181    }
     182
     183  private:
     184
     185    static bool varFirstChar(char c) {
     186      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
     187    }
     188
     189    static bool varChar(char c) {
     190      return (c >= '0' && c <= '9') ||
     191        (c >= 'a' && c <= 'z') ||
     192        (c >= 'A' && c <= 'Z') ||
     193        c == '[' || c == ']';
     194    }
     195   
     196    LpSolverBase& lp;
     197
     198  };
     199
     200  /// \ingroup gen_opt_tools
     201  ///
     202  /// \brief Lp variable item writer for Lemon IO
     203  ///
     204  /// This class is an Lp variable item writer for Lemon IO. It makes
     205  /// possible to store lp variables in lemon file. The usage of this
     206  /// class is very simple:
     207  ///
     208  ///\code
     209  /// Graph graph;
     210  /// Lp lp;
     211  /// Graph::EdgeMap<Lp::Col> var(graph);
     212  ///
     213  /// GraphWriter<Graph> writer(cin, graph);
     214  /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
     215  /// writer.run();
     216  ///\endcode
     217  ///
     218  /// If there is no name associated to the current item then the name
     219  /// will automatically constructed. If the value is INVALID then it
     220  /// will write an \c '-' value to the file.
     221  class LpColWriter {
     222  public:
     223
     224    /// \brief The value type of writer.
     225    ///
     226    /// The value type of writer.
     227    typedef LpSolverBase::Col Value;
     228
     229    /// \brief Constructor for the writer.
     230    ///
     231    /// Constructor for the writer.
     232    LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
     233
     234    /// \brief Writes an lp variable to the given stream.
     235    ///
     236    /// Writes an lp variable to the given stream.
     237    void write(std::ostream& os, const LpSolverBase::Col& col) const {
     238      if (col != INVALID) {
     239        std::string name = lp.colName(col);
     240        if (name.empty()) {
     241          std::ostringstream ls;
     242          ls << "x" << num;
     243          ++num;
     244          while (lp.colByName(ls.str()) != INVALID) {
     245            ls.str(std::string());
     246            ls << "x" << num;
     247            ++num;
     248          }
     249          const_cast<LpSolverBase&>(lp).colName(col, ls.str());
     250          os << ls.str();
     251        } else {
     252          os << name;
     253        }
     254      } else {
     255        os << "-";
     256      }
     257    }
     258
     259  private:
     260
     261    const LpSolverBase& lp;
     262    mutable int num;
     263
     264  };
     265
     266  /// \ingroup gen_opt_tools
     267  ///
     268  /// \brief Lp section reader for lemon IO
     269  ///
     270  /// This section reader provides an easy way to read an Lp problem
     271  /// from a file. The lemon lp section format contains three parts.
     272  ///
     273  ///\code
     274  /// @lp
     275  /// constraints
     276  ///   7 == x1 - 1 * x2
     277  ///   2 * x1 + x3 / 2 <= 7
     278  ///   x2 + -3 * x3 >= 8
     279  ///   3 <= x2 - 2 * x1 <= 8
     280  /// bounds
     281  ///   x1 >= 3
     282  ///   2 <= x2 <= 5
     283  ///   0 <= x3 <= 8
     284  /// objective
     285  ///   min x1 + 2 * x2 - x3
     286  ///\endcode
     287  ///
     288  /// The first part gives the constraints to the lp. The constraints
     289  /// could be equality, lower bound, upper bound or range for an
     290  /// expression or equality, less or more for two expressions.
     291  ///
     292  /// The second part gives the bounds for the variables. The bounds
     293  /// could be the same as for the single expression so equality,
     294  /// lower bound, upper bound or range.
     295  ///
     296  /// The third part is the objective function, it should start with
     297  /// \c min or \c max and then a valid linear expression.
     298  ///
     299  /// The reader constructs automatically the variable for a name if
     300  /// there is not already a variable with the same name.
     301  ///
     302  /// The basic way to read an LP problem is made by the next code:
     303  ///\code
     304  /// Lp lp;
     305  ///
     306  /// LemonReader reader(filename_or_istream);
     307  /// LpReader lpreader(reader, lp);
     308  ///
     309  /// reader.run();
     310  ///\endcode
     311  ///
     312  /// Of course instead of \c LemonReader you can give a \c
     313  /// GraphReader to the LpReader constructor. Also useful that you
     314  /// can mix lp problems and graphs in the same file.
    29315  class LpReader : public LemonReader::SectionReader {
    30316    typedef LemonReader::SectionReader Parent;
     
    34320    /// \brief Constructor.
    35321    ///
    36     /// Constructor for LpReader. It creates the LpReader and attach
     322    /// Constructor for LpReader. It creates the LpReader and attachs
    37323    /// it into the given LemonReader. The lp reader will add
    38324    /// variables, constraints and objective function to the
     
    45331    /// \brief Destructor.
    46332    ///
    47     /// Destructor for NodeSetReader.
     333    /// Destructor for LpReader.
    48334    virtual ~LpReader() {}
    49335
     
    69355  private:
    70356
    71     enum SubSection {
     357    enum Part {
    72358      CONSTRAINTS, BOUNDS, OBJECTIVE
    73359    };
     
    211497            lp.colUpperBound(c, v);
    212498          }
     499          is >> std::ws;
    213500          if (is.get(x)) {
    214501            throw DataFormatError("Wrong variable bounds format");
     
    344631        is.putback(x);
    345632      }
    346       ColMap::const_iterator it = cols.find(var);
    347       if (cols.find(var) != cols.end()) {
    348         c = it->second;
    349       } else {
     633      c = lp.colByName(var);
     634      if (c == INVALID) {
    350635        c = lp.addCol();
    351         cols.insert(std::make_pair(var, c));
    352636        lp.colName(c, var);
    353637      }
     
    391675      return (c >= '0' && c <= '9') || c == '.';
    392676    }
    393 
     677   
    394678    static bool varChar(char c) {
    395679      return (c >= '0' && c <= '9') ||
     
    406690    virtual void read(std::istream& is) {
    407691      std::string line;
    408       SubSection sub = CONSTRAINTS;
     692      Part part = CONSTRAINTS;
    409693      while (getline(is, line)) {
    410694        std::istringstream ls(line);
     
    412696        ls >> type;
    413697        if (type == "constraints") {
    414           sub = CONSTRAINTS;
     698          part = CONSTRAINTS;
     699          ls >> std::ws;
     700          char x;
     701          if (ls.get(x))
     702            throw DataFormatError("Wrong Lp format");
    415703        } else if (type == "bounds") {
    416           sub = BOUNDS;
     704          part = BOUNDS;
     705          ls >> std::ws;
     706          char x;
     707          if (ls.get(x))
     708            throw DataFormatError("Wrong Lp format");
    417709        } else if (type == "objective") {
    418           sub = OBJECTIVE;
     710          part = OBJECTIVE;
     711          ls >> std::ws;
     712          char x;
     713          if (ls.get(x))
     714            throw DataFormatError("Wrong Lp format");
    419715        } else {
    420716          ls.str(line);
    421           switch (sub) {
     717          switch (part) {
    422718          case CONSTRAINTS:
    423719            readConstraint(ls);
     
    430726            break;
    431727          }
    432         }       
     728        }
    433729      }
    434730    }
     
    442738  private:
    443739
    444     typedef std::map<std::string, LpSolverBase::Col> ColMap;
    445740     
    446741    LpSolverBase& lp;
    447742    std::string name;
    448     ColMap cols;
    449743  };
    450744
    451745
     746  /// \ingroup gen_opt_tools
     747  ///
     748  /// \brief Lp section writer for lemon IO
     749  ///
     750  /// This section reader provides an easy way to write an Lp problem
     751  /// to a file. The lemon lp section format contains three parts.
     752  ///
     753  ///\code
     754  /// @lp
     755  /// constraints
     756  ///   7 == x1 - 1 * x2
     757  ///   2 * x1 + x3 / 2 <= 7
     758  ///   x2 + -3 * x3 >= 8
     759  ///   3 <= x2 - 2 * x1 <= 8
     760  /// bounds
     761  ///   x1 >= 3
     762  ///   2 <= x2 <= 5
     763  ///   0 <= x3 <= 8
     764  /// objective
     765  ///   min x1 + 2 * x2 - x3
     766  ///\endcode
     767  ///
     768  /// The first part gives the constraints to the lp. The constraints
     769  /// could be equality, lower bound, upper bound or range for an
     770  /// expression or equality, less or more for two expressions.
     771  ///
     772  /// The second part gives the bounds for the variables. The bounds
     773  /// could be the same as for the single expression so equality,
     774  /// lower bound, upper bound or range.
     775  ///
     776  /// The third part is the objective function, it should start with
     777  /// \c min or \c max and then a valid linear expression.
     778  ///
     779  /// If an LP variable does not have name in the writer, then it will
     780  /// automatically created in the writer. This make a slight change
     781  /// in the \c const variable.
     782  ///
     783  /// The basic way to write an LP problem is made by the next code:
     784  ///\code
     785  /// Lp lp;
     786  ///
     787  /// LemonWriter writer(filename_or_ostream);
     788  /// LpWriter lpwriter(writer, lp);
     789  ///
     790  /// writer.run();
     791  ///\endcode
     792  ///
     793  /// Of course instead of \c LemonWriter you can give a \c
     794  /// GraphWriter to the LpWriter constructor. Also useful that you
     795  /// can mix lp problems and graphs in the same file.
    452796  class LpWriter : public LemonWriter::SectionWriter {
    453797    typedef LemonWriter::SectionWriter Parent;
     
    458802    ///
    459803    /// 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,
     804    /// it into the given LemonWriter.
     805    LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
    464806             const std::string& _name = std::string())
    465807      : Parent(_writer), lp(_lp), name(_name) {}
     
    468810    /// \brief Destructor.
    469811    ///
    470     /// Destructor for NodeSetWriter.
     812    /// Destructor for LpWriter.
    471813    virtual ~LpWriter() {}
    472814
     
    490832
    491833    void createCols() {
    492       int num = 1;
    493 
    494       std::map<std::string, LpSolverBase::Col> inverse;
     834      int num = 0;
    495835
    496836      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
    497837        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 {
     838        if (name.empty()) {
    502839          std::ostringstream ls;
    503           ls << "var" << num;
     840          ls << "x" << num;
    504841          ++num;
    505           cols.insert(std::make_pair(it, ls.str()));
    506           inverse.insert(std::make_pair(ls.str(), it));
     842          while (lp.colByName(ls.str()) != INVALID) {
     843            ls.str(std::string());
     844            ls << "x" << num;
     845            ++num;
     846          }
     847          const_cast<LpSolverBase&>(lp).colName(it, ls.str());
    507848        }
    508849      }
     
    527868        }
    528869        first = false;
    529         os << cols[jt->first] << " ";
     870        os << lp.colName(jt->first) << " ";
    530871      }
    531872      if (e.constComp() < 0.0) {
     
    590931          }
    591932         
    592           os << cols[it] << " ";
     933          os << lp.colName(it) << " ";
    593934         
    594935          if (upper != LpSolverBase::INF) {
     
    596937          }
    597938        } else {
    598           os << cols[it] << " == " << upper << " ";
     939          os << lp.colName(it) << " == " << upper << " ";
    599940        }
    600941        os << std::endl;
     
    615956  private:
    616957
    617     typedef std::map<LpSolverBase::Col, std::string> ColMap;
    618      
    619     LpSolverBase& lp;
     958    const LpSolverBase& lp;
    620959    std::string name;
    621     ColMap cols;
    622960  };
    623961
Note: See TracChangeset for help on using the changeset viewer.