1.1 --- a/lemon/lp_utils.h Mon Feb 19 09:55:43 2007 +0000
1.2 +++ b/lemon/lp_utils.h Mon Feb 19 12:11:41 2007 +0000
1.3 @@ -24,8 +24,294 @@
1.4 #include <lemon/lemon_reader.h>
1.5 #include <lemon/lemon_writer.h>
1.6
1.7 +#include <map>
1.8 +#include <set>
1.9 +
1.10 +
1.11 namespace lemon {
1.12
1.13 + /// \ingroup gen_opt_tools
1.14 + ///
1.15 + /// \brief The map for the result of the lp variables.
1.16 + ///
1.17 + /// The map for the result of the lp variables.
1.18 + class LpResultMap {
1.19 + public:
1.20 + typedef LpSolverBase::Col Key;
1.21 + typedef LpSolverBase::Value Value;
1.22 +
1.23 + /// \brief Constructor
1.24 + ///
1.25 + /// Constructor
1.26 + LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
1.27 + LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
1.28 + return lp.primal(col);
1.29 + }
1.30 + private:
1.31 + const LpSolverBase& lp;
1.32 + };
1.33 +
1.34 + /// \ingroup gen_opt_tools
1.35 + ///
1.36 + /// \brief The map for the name of the lp variables.
1.37 + ///
1.38 + /// The map for the name of the lp variables.
1.39 + class LpColNameMap {
1.40 + public:
1.41 + typedef LpSolverBase::Col Key;
1.42 + typedef std::string Value;
1.43 +
1.44 + /// \brief Constructor
1.45 + ///
1.46 + /// Constructor
1.47 + LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
1.48 + std::string operator[](const LpSolverBase::Col col) const {
1.49 + return lp.colName(col);
1.50 + }
1.51 + private:
1.52 + const LpSolverBase& lp;
1.53 + };
1.54 +
1.55 + /// \ingroup gen_opt_tools
1.56 + ///
1.57 + /// \brief Writeable map for the name of the lp variables.
1.58 + ///
1.59 + /// Writeable map for the name of the lp variables.
1.60 + class LpColNameWriteMap {
1.61 + public:
1.62 + typedef LpSolverBase::Col Key;
1.63 + typedef std::string Value;
1.64 +
1.65 + /// \brief Constructor
1.66 + ///
1.67 + /// Constructor
1.68 + LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
1.69 + std::string operator[](const LpSolverBase::Col col) const {
1.70 + return lp.colName(col);
1.71 + }
1.72 + void set(const LpSolverBase::Col col, const std::string& name) {
1.73 + lp.colName(col, name);
1.74 + }
1.75 + private:
1.76 + LpSolverBase& lp;
1.77 + };
1.78 +
1.79 + /// \ingroup gen_opt_tools
1.80 + ///
1.81 + /// \brief Returns an \ref LpColNameMap class
1.82 + ///
1.83 + /// This function just returns an \ref LpColNameMap class.
1.84 + /// \relates LpColNameMap
1.85 + LpColNameMap lpColNameMap(const LpSolverBase& lp) {
1.86 + return LpColNameMap(lp);
1.87 + }
1.88 +
1.89 + LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
1.90 + return LpColNameWriteMap(lp);
1.91 + }
1.92 +
1.93 + /// \ingroup gen_opt_tools
1.94 + ///
1.95 + /// \brief Lp variable item reader for Lemon IO
1.96 + ///
1.97 + /// This class is an Lp variable item reader for Lemon IO. It makes
1.98 + /// possible to store lp variables in lemon file. The usage of this
1.99 + /// class is very simple:
1.100 + ///
1.101 + ///\code
1.102 + /// Graph graph;
1.103 + /// Lp lp;
1.104 + /// Graph::EdgeMap<Lp::Col> var(graph);
1.105 + ///
1.106 + /// GraphReader<Graph> reader(cin, graph);
1.107 + /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
1.108 + /// reader.run();
1.109 + ///\endcode
1.110 + ///
1.111 + /// If there is already a variable with the same name in the lp then
1.112 + /// it will be used for the return value. If there is no such variable
1.113 + /// then it will be constructed. The file could contain \c '-' as value
1.114 + /// which means that no lp variable associated to the current item and
1.115 + /// in this case INVALID will be returned.
1.116 + class LpColReader {
1.117 + public:
1.118 +
1.119 + /// \brief The value type of reader.
1.120 + ///
1.121 + /// The value type of reader.
1.122 + typedef LpSolverBase::Col Value;
1.123 +
1.124 + /// \brief Constructor for the reader.
1.125 + ///
1.126 + /// Constructor for the reader.
1.127 + LpColReader(LpSolverBase& _lp) : lp(_lp) {}
1.128 +
1.129 + /// \brief Reads an lp variable from the given stream.
1.130 + ///
1.131 + /// Reads an lp variable string from the given stream.
1.132 + void read(std::istream& is, LpSolverBase::Col& col) const {
1.133 + char x;
1.134 + is >> std::ws;
1.135 + if (!is.get(x))
1.136 + throw DataFormatError("Wrong Lp Column format!");
1.137 + if (varFirstChar(x)) {
1.138 + std::string var;
1.139 + var += x;
1.140 +
1.141 + while (is.get(x) && varChar(x)) {
1.142 + var += x;
1.143 + }
1.144 + if (!is) {
1.145 + is.clear();
1.146 + } else {
1.147 + is.putback(x);
1.148 + }
1.149 + col = lp.colByName(var);
1.150 + if (col == INVALID) {
1.151 + col = lp.addCol();
1.152 + lp.colName(col, var);
1.153 + }
1.154 + } else if (x == '-') {
1.155 + col = INVALID;
1.156 + is >> std::ws;
1.157 + } else {
1.158 + std::cerr << x << std::endl;
1.159 + throw DataFormatError("Wrong Lp Column format");
1.160 + }
1.161 + }
1.162 +
1.163 + private:
1.164 +
1.165 + static bool varFirstChar(char c) {
1.166 + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
1.167 + }
1.168 +
1.169 + static bool varChar(char c) {
1.170 + return (c >= '0' && c <= '9') ||
1.171 + (c >= 'a' && c <= 'z') ||
1.172 + (c >= 'A' && c <= 'Z') ||
1.173 + c == '[' || c == ']';
1.174 + }
1.175 +
1.176 + LpSolverBase& lp;
1.177 +
1.178 + };
1.179 +
1.180 + /// \ingroup gen_opt_tools
1.181 + ///
1.182 + /// \brief Lp variable item writer for Lemon IO
1.183 + ///
1.184 + /// This class is an Lp variable item writer for Lemon IO. It makes
1.185 + /// possible to store lp variables in lemon file. The usage of this
1.186 + /// class is very simple:
1.187 + ///
1.188 + ///\code
1.189 + /// Graph graph;
1.190 + /// Lp lp;
1.191 + /// Graph::EdgeMap<Lp::Col> var(graph);
1.192 + ///
1.193 + /// GraphWriter<Graph> writer(cin, graph);
1.194 + /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
1.195 + /// writer.run();
1.196 + ///\endcode
1.197 + ///
1.198 + /// If there is no name associated to the current item then the name
1.199 + /// will automatically constructed. If the value is INVALID then it
1.200 + /// will write an \c '-' value to the file.
1.201 + class LpColWriter {
1.202 + public:
1.203 +
1.204 + /// \brief The value type of writer.
1.205 + ///
1.206 + /// The value type of writer.
1.207 + typedef LpSolverBase::Col Value;
1.208 +
1.209 + /// \brief Constructor for the writer.
1.210 + ///
1.211 + /// Constructor for the writer.
1.212 + LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
1.213 +
1.214 + /// \brief Writes an lp variable to the given stream.
1.215 + ///
1.216 + /// Writes an lp variable to the given stream.
1.217 + void write(std::ostream& os, const LpSolverBase::Col& col) const {
1.218 + if (col != INVALID) {
1.219 + std::string name = lp.colName(col);
1.220 + if (name.empty()) {
1.221 + std::ostringstream ls;
1.222 + ls << "x" << num;
1.223 + ++num;
1.224 + while (lp.colByName(ls.str()) != INVALID) {
1.225 + ls.str(std::string());
1.226 + ls << "x" << num;
1.227 + ++num;
1.228 + }
1.229 + const_cast<LpSolverBase&>(lp).colName(col, ls.str());
1.230 + os << ls.str();
1.231 + } else {
1.232 + os << name;
1.233 + }
1.234 + } else {
1.235 + os << "-";
1.236 + }
1.237 + }
1.238 +
1.239 + private:
1.240 +
1.241 + const LpSolverBase& lp;
1.242 + mutable int num;
1.243 +
1.244 + };
1.245 +
1.246 + /// \ingroup gen_opt_tools
1.247 + ///
1.248 + /// \brief Lp section reader for lemon IO
1.249 + ///
1.250 + /// This section reader provides an easy way to read an Lp problem
1.251 + /// from a file. The lemon lp section format contains three parts.
1.252 + ///
1.253 + ///\code
1.254 + /// @lp
1.255 + /// constraints
1.256 + /// 7 == x1 - 1 * x2
1.257 + /// 2 * x1 + x3 / 2 <= 7
1.258 + /// x2 + -3 * x3 >= 8
1.259 + /// 3 <= x2 - 2 * x1 <= 8
1.260 + /// bounds
1.261 + /// x1 >= 3
1.262 + /// 2 <= x2 <= 5
1.263 + /// 0 <= x3 <= 8
1.264 + /// objective
1.265 + /// min x1 + 2 * x2 - x3
1.266 + ///\endcode
1.267 + ///
1.268 + /// The first part gives the constraints to the lp. The constraints
1.269 + /// could be equality, lower bound, upper bound or range for an
1.270 + /// expression or equality, less or more for two expressions.
1.271 + ///
1.272 + /// The second part gives the bounds for the variables. The bounds
1.273 + /// could be the same as for the single expression so equality,
1.274 + /// lower bound, upper bound or range.
1.275 + ///
1.276 + /// The third part is the objective function, it should start with
1.277 + /// \c min or \c max and then a valid linear expression.
1.278 + ///
1.279 + /// The reader constructs automatically the variable for a name if
1.280 + /// there is not already a variable with the same name.
1.281 + ///
1.282 + /// The basic way to read an LP problem is made by the next code:
1.283 + ///\code
1.284 + /// Lp lp;
1.285 + ///
1.286 + /// LemonReader reader(filename_or_istream);
1.287 + /// LpReader lpreader(reader, lp);
1.288 + ///
1.289 + /// reader.run();
1.290 + ///\endcode
1.291 + ///
1.292 + /// Of course instead of \c LemonReader you can give a \c
1.293 + /// GraphReader to the LpReader constructor. Also useful that you
1.294 + /// can mix lp problems and graphs in the same file.
1.295 class LpReader : public LemonReader::SectionReader {
1.296 typedef LemonReader::SectionReader Parent;
1.297 public:
1.298 @@ -33,7 +319,7 @@
1.299
1.300 /// \brief Constructor.
1.301 ///
1.302 - /// Constructor for LpReader. It creates the LpReader and attach
1.303 + /// Constructor for LpReader. It creates the LpReader and attachs
1.304 /// it into the given LemonReader. The lp reader will add
1.305 /// variables, constraints and objective function to the
1.306 /// given lp solver.
1.307 @@ -44,7 +330,7 @@
1.308
1.309 /// \brief Destructor.
1.310 ///
1.311 - /// Destructor for NodeSetReader.
1.312 + /// Destructor for LpReader.
1.313 virtual ~LpReader() {}
1.314
1.315 private:
1.316 @@ -68,7 +354,7 @@
1.317
1.318 private:
1.319
1.320 - enum SubSection {
1.321 + enum Part {
1.322 CONSTRAINTS, BOUNDS, OBJECTIVE
1.323 };
1.324
1.325 @@ -210,6 +496,7 @@
1.326 lp.colLowerBound(c, w);
1.327 lp.colUpperBound(c, v);
1.328 }
1.329 + is >> std::ws;
1.330 if (is.get(x)) {
1.331 throw DataFormatError("Wrong variable bounds format");
1.332 }
1.333 @@ -343,12 +630,9 @@
1.334 } else {
1.335 is.putback(x);
1.336 }
1.337 - ColMap::const_iterator it = cols.find(var);
1.338 - if (cols.find(var) != cols.end()) {
1.339 - c = it->second;
1.340 - } else {
1.341 + c = lp.colByName(var);
1.342 + if (c == INVALID) {
1.343 c = lp.addCol();
1.344 - cols.insert(std::make_pair(var, c));
1.345 lp.colName(c, var);
1.346 }
1.347 return is;
1.348 @@ -390,7 +674,7 @@
1.349 static bool numFirstChar(char c) {
1.350 return (c >= '0' && c <= '9') || c == '.';
1.351 }
1.352 -
1.353 +
1.354 static bool varChar(char c) {
1.355 return (c >= '0' && c <= '9') ||
1.356 (c >= 'a' && c <= 'z') ||
1.357 @@ -405,20 +689,32 @@
1.358 /// It reads the content of the section.
1.359 virtual void read(std::istream& is) {
1.360 std::string line;
1.361 - SubSection sub = CONSTRAINTS;
1.362 + Part part = CONSTRAINTS;
1.363 while (getline(is, line)) {
1.364 std::istringstream ls(line);
1.365 std::string type;
1.366 ls >> type;
1.367 if (type == "constraints") {
1.368 - sub = CONSTRAINTS;
1.369 + part = CONSTRAINTS;
1.370 + ls >> std::ws;
1.371 + char x;
1.372 + if (ls.get(x))
1.373 + throw DataFormatError("Wrong Lp format");
1.374 } else if (type == "bounds") {
1.375 - sub = BOUNDS;
1.376 + part = BOUNDS;
1.377 + ls >> std::ws;
1.378 + char x;
1.379 + if (ls.get(x))
1.380 + throw DataFormatError("Wrong Lp format");
1.381 } else if (type == "objective") {
1.382 - sub = OBJECTIVE;
1.383 + part = OBJECTIVE;
1.384 + ls >> std::ws;
1.385 + char x;
1.386 + if (ls.get(x))
1.387 + throw DataFormatError("Wrong Lp format");
1.388 } else {
1.389 ls.str(line);
1.390 - switch (sub) {
1.391 + switch (part) {
1.392 case CONSTRAINTS:
1.393 readConstraint(ls);
1.394 break;
1.395 @@ -429,7 +725,7 @@
1.396 readObjective(ls);
1.397 break;
1.398 }
1.399 - }
1.400 + }
1.401 }
1.402 }
1.403
1.404 @@ -441,14 +737,62 @@
1.405
1.406 private:
1.407
1.408 - typedef std::map<std::string, LpSolverBase::Col> ColMap;
1.409
1.410 LpSolverBase& lp;
1.411 std::string name;
1.412 - ColMap cols;
1.413 };
1.414
1.415
1.416 + /// \ingroup gen_opt_tools
1.417 + ///
1.418 + /// \brief Lp section writer for lemon IO
1.419 + ///
1.420 + /// This section reader provides an easy way to write an Lp problem
1.421 + /// to a file. The lemon lp section format contains three parts.
1.422 + ///
1.423 + ///\code
1.424 + /// @lp
1.425 + /// constraints
1.426 + /// 7 == x1 - 1 * x2
1.427 + /// 2 * x1 + x3 / 2 <= 7
1.428 + /// x2 + -3 * x3 >= 8
1.429 + /// 3 <= x2 - 2 * x1 <= 8
1.430 + /// bounds
1.431 + /// x1 >= 3
1.432 + /// 2 <= x2 <= 5
1.433 + /// 0 <= x3 <= 8
1.434 + /// objective
1.435 + /// min x1 + 2 * x2 - x3
1.436 + ///\endcode
1.437 + ///
1.438 + /// The first part gives the constraints to the lp. The constraints
1.439 + /// could be equality, lower bound, upper bound or range for an
1.440 + /// expression or equality, less or more for two expressions.
1.441 + ///
1.442 + /// The second part gives the bounds for the variables. The bounds
1.443 + /// could be the same as for the single expression so equality,
1.444 + /// lower bound, upper bound or range.
1.445 + ///
1.446 + /// The third part is the objective function, it should start with
1.447 + /// \c min or \c max and then a valid linear expression.
1.448 + ///
1.449 + /// If an LP variable does not have name in the writer, then it will
1.450 + /// automatically created in the writer. This make a slight change
1.451 + /// in the \c const variable.
1.452 + ///
1.453 + /// The basic way to write an LP problem is made by the next code:
1.454 + ///\code
1.455 + /// Lp lp;
1.456 + ///
1.457 + /// LemonWriter writer(filename_or_ostream);
1.458 + /// LpWriter lpwriter(writer, lp);
1.459 + ///
1.460 + /// writer.run();
1.461 + ///\endcode
1.462 + ///
1.463 + /// Of course instead of \c LemonWriter you can give a \c
1.464 + /// GraphWriter to the LpWriter constructor. Also useful that you
1.465 + /// can mix lp problems and graphs in the same file.
1.466 class LpWriter : public LemonWriter::SectionWriter {
1.467 typedef LemonWriter::SectionWriter Parent;
1.468 public:
1.469 @@ -457,17 +801,15 @@
1.470 /// \brief Constructor.
1.471 ///
1.472 /// Constructor for LpWriter. It creates the LpWriter and attach
1.473 - /// it into the given LemonWriter. The lp writer will add
1.474 - /// variables, constraints and objective function to the
1.475 - /// given lp solver.
1.476 - LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
1.477 + /// it into the given LemonWriter.
1.478 + LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
1.479 const std::string& _name = std::string())
1.480 : Parent(_writer), lp(_lp), name(_name) {}
1.481
1.482
1.483 /// \brief Destructor.
1.484 ///
1.485 - /// Destructor for NodeSetWriter.
1.486 + /// Destructor for LpWriter.
1.487 virtual ~LpWriter() {}
1.488
1.489 private:
1.490 @@ -489,21 +831,20 @@
1.491 private:
1.492
1.493 void createCols() {
1.494 - int num = 1;
1.495 -
1.496 - std::map<std::string, LpSolverBase::Col> inverse;
1.497 + int num = 0;
1.498
1.499 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
1.500 std::string name = lp.colName(it);
1.501 - if (!name.empty() && inverse.find(name) == inverse.end()) {
1.502 - cols.insert(std::make_pair(it, name));
1.503 - inverse.insert(std::make_pair(name, it));
1.504 - } else {
1.505 + if (name.empty()) {
1.506 std::ostringstream ls;
1.507 - ls << "var" << num;
1.508 + ls << "x" << num;
1.509 ++num;
1.510 - cols.insert(std::make_pair(it, ls.str()));
1.511 - inverse.insert(std::make_pair(ls.str(), it));
1.512 + while (lp.colByName(ls.str()) != INVALID) {
1.513 + ls.str(std::string());
1.514 + ls << "x" << num;
1.515 + ++num;
1.516 + }
1.517 + const_cast<LpSolverBase&>(lp).colName(it, ls.str());
1.518 }
1.519 }
1.520 }
1.521 @@ -526,7 +867,7 @@
1.522 }
1.523 }
1.524 first = false;
1.525 - os << cols[jt->first] << " ";
1.526 + os << lp.colName(jt->first) << " ";
1.527 }
1.528 if (e.constComp() < 0.0) {
1.529 os << "- " << -e.constComp() << " ";
1.530 @@ -589,13 +930,13 @@
1.531 os << lower << " <= ";
1.532 }
1.533
1.534 - os << cols[it] << " ";
1.535 + os << lp.colName(it) << " ";
1.536
1.537 if (upper != LpSolverBase::INF) {
1.538 os << "<= " << upper << " ";
1.539 }
1.540 } else {
1.541 - os << cols[it] << " == " << upper << " ";
1.542 + os << lp.colName(it) << " == " << upper << " ";
1.543 }
1.544 os << std::endl;
1.545 }
1.546 @@ -614,11 +955,8 @@
1.547
1.548 private:
1.549
1.550 - typedef std::map<LpSolverBase::Col, std::string> ColMap;
1.551 -
1.552 - LpSolverBase& lp;
1.553 + const LpSolverBase& lp;
1.554 std::string name;
1.555 - ColMap cols;
1.556 };
1.557
1.558 }