1.1 --- a/doc/groups.dox Mon Feb 19 09:55:43 2007 +0000
1.2 +++ b/doc/groups.dox Mon Feb 19 12:11:41 2007 +0000
1.3 @@ -213,6 +213,17 @@
1.4
1.5 */
1.6
1.7 +/**
1.8 +\ingroup gen_opt_group
1.9 +@defgroup gen_opt_tools Various Tools for Optimization
1.10 +\brief This group adds some helper tools to general optimization
1.11 +framework implemented in LEMON.
1.12 +
1.13 +This group adds some helper tools to general optimization framework
1.14 +implemented in LEMON.
1.15 +
1.16 +*/
1.17 +
1.18 /**
1.19 @defgroup misc Miscellaneous Tools
1.20 Here you can find several useful tools for development,
2.1 --- a/lemon/lemon_reader.h Mon Feb 19 09:55:43 2007 +0000
2.2 +++ b/lemon/lemon_reader.h Mon Feb 19 12:11:41 2007 +0000
2.3 @@ -740,9 +740,9 @@
2.4 /// \ingroup section_io
2.5 /// \brief SectionReader for reading a graph's nodeset.
2.6 ///
2.7 - /// The lemon format can store multiple graph nodesets with several maps.
2.8 - /// The nodeset section's header line is \c \@nodeset \c nodeset_name, but the
2.9 - /// \c nodeset_name may be empty.
2.10 + /// The lemon format can store multiple graph nodesets with several
2.11 + /// maps. The nodeset section's header line is \c \@nodeset \c
2.12 + /// nodeset_name, but the \c nodeset_name may be empty.
2.13 ///
2.14 /// The first line of the section contains the names of the maps separated
2.15 /// with white spaces. Each next lines describes a node in the nodeset, and
3.1 --- a/lemon/lp_base.h Mon Feb 19 09:55:43 2007 +0000
3.2 +++ b/lemon/lp_base.h Mon Feb 19 12:11:41 2007 +0000
3.3 @@ -1060,6 +1060,15 @@
3.4 void colName(Col c, const std::string& name) {
3.5 _setColName(_lpId(c), name);
3.6 }
3.7 +
3.8 + /// Get the column by its name
3.9 +
3.10 + ///\param name The name of the column
3.11 + ///\return the proper column or \c INVALID
3.12 + Col colByName(const std::string& name) const {
3.13 + int k = _colByName(name);
3.14 + return k != -1 ? Col(cols.fixId(k)) : Col(INVALID);
3.15 + }
3.16
3.17 /// Set an element of the coefficient matrix of the LP
3.18
4.1 --- a/lemon/lp_glpk.cc Mon Feb 19 09:55:43 2007 +0000
4.2 +++ b/lemon/lp_glpk.cc Mon Feb 19 12:11:41 2007 +0000
4.3 @@ -28,6 +28,7 @@
4.4 rows = _lp_bits::LpId(1);
4.5 cols = _lp_bits::LpId(1);
4.6 lp = lpx_create_prob();
4.7 + lpx_create_index(lp);
4.8 ///\todo control function for this:
4.9 lpx_set_int_parm(lp, LPX_K_DUAL, 1);
4.10 messageLevel(0);
5.1 --- a/lemon/lp_soplex.cc Mon Feb 19 09:55:43 2007 +0000
5.2 +++ b/lemon/lp_soplex.cc Mon Feb 19 12:11:41 2007 +0000
5.3 @@ -76,7 +76,9 @@
5.4
5.5 void LpSoplex::_eraseCol(int i) {
5.6 soplex->removeCol(i);
5.7 + invColNames.erase(colNames[i]);
5.8 colNames[i] = colNames.back();
5.9 + invColNames[colNames.back()] = i;
5.10 colNames.pop_back();
5.11 primal_value[i] = primal_value.back();
5.12 primal_value.pop_back();
6.1 --- a/lemon/lp_utils.h Mon Feb 19 09:55:43 2007 +0000
6.2 +++ b/lemon/lp_utils.h Mon Feb 19 12:11:41 2007 +0000
6.3 @@ -24,8 +24,294 @@
6.4 #include <lemon/lemon_reader.h>
6.5 #include <lemon/lemon_writer.h>
6.6
6.7 +#include <map>
6.8 +#include <set>
6.9 +
6.10 +
6.11 namespace lemon {
6.12
6.13 + /// \ingroup gen_opt_tools
6.14 + ///
6.15 + /// \brief The map for the result of the lp variables.
6.16 + ///
6.17 + /// The map for the result of the lp variables.
6.18 + class LpResultMap {
6.19 + public:
6.20 + typedef LpSolverBase::Col Key;
6.21 + typedef LpSolverBase::Value Value;
6.22 +
6.23 + /// \brief Constructor
6.24 + ///
6.25 + /// Constructor
6.26 + LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
6.27 + LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
6.28 + return lp.primal(col);
6.29 + }
6.30 + private:
6.31 + const LpSolverBase& lp;
6.32 + };
6.33 +
6.34 + /// \ingroup gen_opt_tools
6.35 + ///
6.36 + /// \brief The map for the name of the lp variables.
6.37 + ///
6.38 + /// The map for the name of the lp variables.
6.39 + class LpColNameMap {
6.40 + public:
6.41 + typedef LpSolverBase::Col Key;
6.42 + typedef std::string Value;
6.43 +
6.44 + /// \brief Constructor
6.45 + ///
6.46 + /// Constructor
6.47 + LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
6.48 + std::string operator[](const LpSolverBase::Col col) const {
6.49 + return lp.colName(col);
6.50 + }
6.51 + private:
6.52 + const LpSolverBase& lp;
6.53 + };
6.54 +
6.55 + /// \ingroup gen_opt_tools
6.56 + ///
6.57 + /// \brief Writeable map for the name of the lp variables.
6.58 + ///
6.59 + /// Writeable map for the name of the lp variables.
6.60 + class LpColNameWriteMap {
6.61 + public:
6.62 + typedef LpSolverBase::Col Key;
6.63 + typedef std::string Value;
6.64 +
6.65 + /// \brief Constructor
6.66 + ///
6.67 + /// Constructor
6.68 + LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
6.69 + std::string operator[](const LpSolverBase::Col col) const {
6.70 + return lp.colName(col);
6.71 + }
6.72 + void set(const LpSolverBase::Col col, const std::string& name) {
6.73 + lp.colName(col, name);
6.74 + }
6.75 + private:
6.76 + LpSolverBase& lp;
6.77 + };
6.78 +
6.79 + /// \ingroup gen_opt_tools
6.80 + ///
6.81 + /// \brief Returns an \ref LpColNameMap class
6.82 + ///
6.83 + /// This function just returns an \ref LpColNameMap class.
6.84 + /// \relates LpColNameMap
6.85 + LpColNameMap lpColNameMap(const LpSolverBase& lp) {
6.86 + return LpColNameMap(lp);
6.87 + }
6.88 +
6.89 + LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
6.90 + return LpColNameWriteMap(lp);
6.91 + }
6.92 +
6.93 + /// \ingroup gen_opt_tools
6.94 + ///
6.95 + /// \brief Lp variable item reader for Lemon IO
6.96 + ///
6.97 + /// This class is an Lp variable item reader for Lemon IO. It makes
6.98 + /// possible to store lp variables in lemon file. The usage of this
6.99 + /// class is very simple:
6.100 + ///
6.101 + ///\code
6.102 + /// Graph graph;
6.103 + /// Lp lp;
6.104 + /// Graph::EdgeMap<Lp::Col> var(graph);
6.105 + ///
6.106 + /// GraphReader<Graph> reader(cin, graph);
6.107 + /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
6.108 + /// reader.run();
6.109 + ///\endcode
6.110 + ///
6.111 + /// If there is already a variable with the same name in the lp then
6.112 + /// it will be used for the return value. If there is no such variable
6.113 + /// then it will be constructed. The file could contain \c '-' as value
6.114 + /// which means that no lp variable associated to the current item and
6.115 + /// in this case INVALID will be returned.
6.116 + class LpColReader {
6.117 + public:
6.118 +
6.119 + /// \brief The value type of reader.
6.120 + ///
6.121 + /// The value type of reader.
6.122 + typedef LpSolverBase::Col Value;
6.123 +
6.124 + /// \brief Constructor for the reader.
6.125 + ///
6.126 + /// Constructor for the reader.
6.127 + LpColReader(LpSolverBase& _lp) : lp(_lp) {}
6.128 +
6.129 + /// \brief Reads an lp variable from the given stream.
6.130 + ///
6.131 + /// Reads an lp variable string from the given stream.
6.132 + void read(std::istream& is, LpSolverBase::Col& col) const {
6.133 + char x;
6.134 + is >> std::ws;
6.135 + if (!is.get(x))
6.136 + throw DataFormatError("Wrong Lp Column format!");
6.137 + if (varFirstChar(x)) {
6.138 + std::string var;
6.139 + var += x;
6.140 +
6.141 + while (is.get(x) && varChar(x)) {
6.142 + var += x;
6.143 + }
6.144 + if (!is) {
6.145 + is.clear();
6.146 + } else {
6.147 + is.putback(x);
6.148 + }
6.149 + col = lp.colByName(var);
6.150 + if (col == INVALID) {
6.151 + col = lp.addCol();
6.152 + lp.colName(col, var);
6.153 + }
6.154 + } else if (x == '-') {
6.155 + col = INVALID;
6.156 + is >> std::ws;
6.157 + } else {
6.158 + std::cerr << x << std::endl;
6.159 + throw DataFormatError("Wrong Lp Column format");
6.160 + }
6.161 + }
6.162 +
6.163 + private:
6.164 +
6.165 + static bool varFirstChar(char c) {
6.166 + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
6.167 + }
6.168 +
6.169 + static bool varChar(char c) {
6.170 + return (c >= '0' && c <= '9') ||
6.171 + (c >= 'a' && c <= 'z') ||
6.172 + (c >= 'A' && c <= 'Z') ||
6.173 + c == '[' || c == ']';
6.174 + }
6.175 +
6.176 + LpSolverBase& lp;
6.177 +
6.178 + };
6.179 +
6.180 + /// \ingroup gen_opt_tools
6.181 + ///
6.182 + /// \brief Lp variable item writer for Lemon IO
6.183 + ///
6.184 + /// This class is an Lp variable item writer for Lemon IO. It makes
6.185 + /// possible to store lp variables in lemon file. The usage of this
6.186 + /// class is very simple:
6.187 + ///
6.188 + ///\code
6.189 + /// Graph graph;
6.190 + /// Lp lp;
6.191 + /// Graph::EdgeMap<Lp::Col> var(graph);
6.192 + ///
6.193 + /// GraphWriter<Graph> writer(cin, graph);
6.194 + /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
6.195 + /// writer.run();
6.196 + ///\endcode
6.197 + ///
6.198 + /// If there is no name associated to the current item then the name
6.199 + /// will automatically constructed. If the value is INVALID then it
6.200 + /// will write an \c '-' value to the file.
6.201 + class LpColWriter {
6.202 + public:
6.203 +
6.204 + /// \brief The value type of writer.
6.205 + ///
6.206 + /// The value type of writer.
6.207 + typedef LpSolverBase::Col Value;
6.208 +
6.209 + /// \brief Constructor for the writer.
6.210 + ///
6.211 + /// Constructor for the writer.
6.212 + LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
6.213 +
6.214 + /// \brief Writes an lp variable to the given stream.
6.215 + ///
6.216 + /// Writes an lp variable to the given stream.
6.217 + void write(std::ostream& os, const LpSolverBase::Col& col) const {
6.218 + if (col != INVALID) {
6.219 + std::string name = lp.colName(col);
6.220 + if (name.empty()) {
6.221 + std::ostringstream ls;
6.222 + ls << "x" << num;
6.223 + ++num;
6.224 + while (lp.colByName(ls.str()) != INVALID) {
6.225 + ls.str(std::string());
6.226 + ls << "x" << num;
6.227 + ++num;
6.228 + }
6.229 + const_cast<LpSolverBase&>(lp).colName(col, ls.str());
6.230 + os << ls.str();
6.231 + } else {
6.232 + os << name;
6.233 + }
6.234 + } else {
6.235 + os << "-";
6.236 + }
6.237 + }
6.238 +
6.239 + private:
6.240 +
6.241 + const LpSolverBase& lp;
6.242 + mutable int num;
6.243 +
6.244 + };
6.245 +
6.246 + /// \ingroup gen_opt_tools
6.247 + ///
6.248 + /// \brief Lp section reader for lemon IO
6.249 + ///
6.250 + /// This section reader provides an easy way to read an Lp problem
6.251 + /// from a file. The lemon lp section format contains three parts.
6.252 + ///
6.253 + ///\code
6.254 + /// @lp
6.255 + /// constraints
6.256 + /// 7 == x1 - 1 * x2
6.257 + /// 2 * x1 + x3 / 2 <= 7
6.258 + /// x2 + -3 * x3 >= 8
6.259 + /// 3 <= x2 - 2 * x1 <= 8
6.260 + /// bounds
6.261 + /// x1 >= 3
6.262 + /// 2 <= x2 <= 5
6.263 + /// 0 <= x3 <= 8
6.264 + /// objective
6.265 + /// min x1 + 2 * x2 - x3
6.266 + ///\endcode
6.267 + ///
6.268 + /// The first part gives the constraints to the lp. The constraints
6.269 + /// could be equality, lower bound, upper bound or range for an
6.270 + /// expression or equality, less or more for two expressions.
6.271 + ///
6.272 + /// The second part gives the bounds for the variables. The bounds
6.273 + /// could be the same as for the single expression so equality,
6.274 + /// lower bound, upper bound or range.
6.275 + ///
6.276 + /// The third part is the objective function, it should start with
6.277 + /// \c min or \c max and then a valid linear expression.
6.278 + ///
6.279 + /// The reader constructs automatically the variable for a name if
6.280 + /// there is not already a variable with the same name.
6.281 + ///
6.282 + /// The basic way to read an LP problem is made by the next code:
6.283 + ///\code
6.284 + /// Lp lp;
6.285 + ///
6.286 + /// LemonReader reader(filename_or_istream);
6.287 + /// LpReader lpreader(reader, lp);
6.288 + ///
6.289 + /// reader.run();
6.290 + ///\endcode
6.291 + ///
6.292 + /// Of course instead of \c LemonReader you can give a \c
6.293 + /// GraphReader to the LpReader constructor. Also useful that you
6.294 + /// can mix lp problems and graphs in the same file.
6.295 class LpReader : public LemonReader::SectionReader {
6.296 typedef LemonReader::SectionReader Parent;
6.297 public:
6.298 @@ -33,7 +319,7 @@
6.299
6.300 /// \brief Constructor.
6.301 ///
6.302 - /// Constructor for LpReader. It creates the LpReader and attach
6.303 + /// Constructor for LpReader. It creates the LpReader and attachs
6.304 /// it into the given LemonReader. The lp reader will add
6.305 /// variables, constraints and objective function to the
6.306 /// given lp solver.
6.307 @@ -44,7 +330,7 @@
6.308
6.309 /// \brief Destructor.
6.310 ///
6.311 - /// Destructor for NodeSetReader.
6.312 + /// Destructor for LpReader.
6.313 virtual ~LpReader() {}
6.314
6.315 private:
6.316 @@ -68,7 +354,7 @@
6.317
6.318 private:
6.319
6.320 - enum SubSection {
6.321 + enum Part {
6.322 CONSTRAINTS, BOUNDS, OBJECTIVE
6.323 };
6.324
6.325 @@ -210,6 +496,7 @@
6.326 lp.colLowerBound(c, w);
6.327 lp.colUpperBound(c, v);
6.328 }
6.329 + is >> std::ws;
6.330 if (is.get(x)) {
6.331 throw DataFormatError("Wrong variable bounds format");
6.332 }
6.333 @@ -343,12 +630,9 @@
6.334 } else {
6.335 is.putback(x);
6.336 }
6.337 - ColMap::const_iterator it = cols.find(var);
6.338 - if (cols.find(var) != cols.end()) {
6.339 - c = it->second;
6.340 - } else {
6.341 + c = lp.colByName(var);
6.342 + if (c == INVALID) {
6.343 c = lp.addCol();
6.344 - cols.insert(std::make_pair(var, c));
6.345 lp.colName(c, var);
6.346 }
6.347 return is;
6.348 @@ -390,7 +674,7 @@
6.349 static bool numFirstChar(char c) {
6.350 return (c >= '0' && c <= '9') || c == '.';
6.351 }
6.352 -
6.353 +
6.354 static bool varChar(char c) {
6.355 return (c >= '0' && c <= '9') ||
6.356 (c >= 'a' && c <= 'z') ||
6.357 @@ -405,20 +689,32 @@
6.358 /// It reads the content of the section.
6.359 virtual void read(std::istream& is) {
6.360 std::string line;
6.361 - SubSection sub = CONSTRAINTS;
6.362 + Part part = CONSTRAINTS;
6.363 while (getline(is, line)) {
6.364 std::istringstream ls(line);
6.365 std::string type;
6.366 ls >> type;
6.367 if (type == "constraints") {
6.368 - sub = CONSTRAINTS;
6.369 + part = CONSTRAINTS;
6.370 + ls >> std::ws;
6.371 + char x;
6.372 + if (ls.get(x))
6.373 + throw DataFormatError("Wrong Lp format");
6.374 } else if (type == "bounds") {
6.375 - sub = BOUNDS;
6.376 + part = BOUNDS;
6.377 + ls >> std::ws;
6.378 + char x;
6.379 + if (ls.get(x))
6.380 + throw DataFormatError("Wrong Lp format");
6.381 } else if (type == "objective") {
6.382 - sub = OBJECTIVE;
6.383 + part = OBJECTIVE;
6.384 + ls >> std::ws;
6.385 + char x;
6.386 + if (ls.get(x))
6.387 + throw DataFormatError("Wrong Lp format");
6.388 } else {
6.389 ls.str(line);
6.390 - switch (sub) {
6.391 + switch (part) {
6.392 case CONSTRAINTS:
6.393 readConstraint(ls);
6.394 break;
6.395 @@ -429,7 +725,7 @@
6.396 readObjective(ls);
6.397 break;
6.398 }
6.399 - }
6.400 + }
6.401 }
6.402 }
6.403
6.404 @@ -441,14 +737,62 @@
6.405
6.406 private:
6.407
6.408 - typedef std::map<std::string, LpSolverBase::Col> ColMap;
6.409
6.410 LpSolverBase& lp;
6.411 std::string name;
6.412 - ColMap cols;
6.413 };
6.414
6.415
6.416 + /// \ingroup gen_opt_tools
6.417 + ///
6.418 + /// \brief Lp section writer for lemon IO
6.419 + ///
6.420 + /// This section reader provides an easy way to write an Lp problem
6.421 + /// to a file. The lemon lp section format contains three parts.
6.422 + ///
6.423 + ///\code
6.424 + /// @lp
6.425 + /// constraints
6.426 + /// 7 == x1 - 1 * x2
6.427 + /// 2 * x1 + x3 / 2 <= 7
6.428 + /// x2 + -3 * x3 >= 8
6.429 + /// 3 <= x2 - 2 * x1 <= 8
6.430 + /// bounds
6.431 + /// x1 >= 3
6.432 + /// 2 <= x2 <= 5
6.433 + /// 0 <= x3 <= 8
6.434 + /// objective
6.435 + /// min x1 + 2 * x2 - x3
6.436 + ///\endcode
6.437 + ///
6.438 + /// The first part gives the constraints to the lp. The constraints
6.439 + /// could be equality, lower bound, upper bound or range for an
6.440 + /// expression or equality, less or more for two expressions.
6.441 + ///
6.442 + /// The second part gives the bounds for the variables. The bounds
6.443 + /// could be the same as for the single expression so equality,
6.444 + /// lower bound, upper bound or range.
6.445 + ///
6.446 + /// The third part is the objective function, it should start with
6.447 + /// \c min or \c max and then a valid linear expression.
6.448 + ///
6.449 + /// If an LP variable does not have name in the writer, then it will
6.450 + /// automatically created in the writer. This make a slight change
6.451 + /// in the \c const variable.
6.452 + ///
6.453 + /// The basic way to write an LP problem is made by the next code:
6.454 + ///\code
6.455 + /// Lp lp;
6.456 + ///
6.457 + /// LemonWriter writer(filename_or_ostream);
6.458 + /// LpWriter lpwriter(writer, lp);
6.459 + ///
6.460 + /// writer.run();
6.461 + ///\endcode
6.462 + ///
6.463 + /// Of course instead of \c LemonWriter you can give a \c
6.464 + /// GraphWriter to the LpWriter constructor. Also useful that you
6.465 + /// can mix lp problems and graphs in the same file.
6.466 class LpWriter : public LemonWriter::SectionWriter {
6.467 typedef LemonWriter::SectionWriter Parent;
6.468 public:
6.469 @@ -457,17 +801,15 @@
6.470 /// \brief Constructor.
6.471 ///
6.472 /// Constructor for LpWriter. It creates the LpWriter and attach
6.473 - /// it into the given LemonWriter. The lp writer will add
6.474 - /// variables, constraints and objective function to the
6.475 - /// given lp solver.
6.476 - LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
6.477 + /// it into the given LemonWriter.
6.478 + LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
6.479 const std::string& _name = std::string())
6.480 : Parent(_writer), lp(_lp), name(_name) {}
6.481
6.482
6.483 /// \brief Destructor.
6.484 ///
6.485 - /// Destructor for NodeSetWriter.
6.486 + /// Destructor for LpWriter.
6.487 virtual ~LpWriter() {}
6.488
6.489 private:
6.490 @@ -489,21 +831,20 @@
6.491 private:
6.492
6.493 void createCols() {
6.494 - int num = 1;
6.495 -
6.496 - std::map<std::string, LpSolverBase::Col> inverse;
6.497 + int num = 0;
6.498
6.499 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
6.500 std::string name = lp.colName(it);
6.501 - if (!name.empty() && inverse.find(name) == inverse.end()) {
6.502 - cols.insert(std::make_pair(it, name));
6.503 - inverse.insert(std::make_pair(name, it));
6.504 - } else {
6.505 + if (name.empty()) {
6.506 std::ostringstream ls;
6.507 - ls << "var" << num;
6.508 + ls << "x" << num;
6.509 ++num;
6.510 - cols.insert(std::make_pair(it, ls.str()));
6.511 - inverse.insert(std::make_pair(ls.str(), it));
6.512 + while (lp.colByName(ls.str()) != INVALID) {
6.513 + ls.str(std::string());
6.514 + ls << "x" << num;
6.515 + ++num;
6.516 + }
6.517 + const_cast<LpSolverBase&>(lp).colName(it, ls.str());
6.518 }
6.519 }
6.520 }
6.521 @@ -526,7 +867,7 @@
6.522 }
6.523 }
6.524 first = false;
6.525 - os << cols[jt->first] << " ";
6.526 + os << lp.colName(jt->first) << " ";
6.527 }
6.528 if (e.constComp() < 0.0) {
6.529 os << "- " << -e.constComp() << " ";
6.530 @@ -589,13 +930,13 @@
6.531 os << lower << " <= ";
6.532 }
6.533
6.534 - os << cols[it] << " ";
6.535 + os << lp.colName(it) << " ";
6.536
6.537 if (upper != LpSolverBase::INF) {
6.538 os << "<= " << upper << " ";
6.539 }
6.540 } else {
6.541 - os << cols[it] << " == " << upper << " ";
6.542 + os << lp.colName(it) << " == " << upper << " ";
6.543 }
6.544 os << std::endl;
6.545 }
6.546 @@ -614,11 +955,8 @@
6.547
6.548 private:
6.549
6.550 - typedef std::map<LpSolverBase::Col, std::string> ColMap;
6.551 -
6.552 - LpSolverBase& lp;
6.553 + const LpSolverBase& lp;
6.554 std::string name;
6.555 - ColMap cols;
6.556 };
6.557
6.558 }