Changeset 2368:6b2e8b734ae7 in lemon-0.x
- Timestamp:
- 02/19/07 13:11:41 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3183
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r2350 r2368 214 214 */ 215 215 216 /** 217 \ingroup gen_opt_group 218 @defgroup gen_opt_tools Various Tools for Optimization 219 \brief This group adds some helper tools to general optimization 220 framework implemented in LEMON. 221 222 This group adds some helper tools to general optimization framework 223 implemented in LEMON. 224 225 */ 226 216 227 /** 217 228 @defgroup misc Miscellaneous Tools -
lemon/lemon_reader.h
r2334 r2368 741 741 /// \brief SectionReader for reading a graph's nodeset. 742 742 /// 743 /// The lemon format can store multiple graph nodesets with several maps.744 /// The nodeset section's header line is \c \@nodeset \c nodeset_name, but the745 /// \c nodeset_name may be empty.743 /// The lemon format can store multiple graph nodesets with several 744 /// maps. The nodeset section's header line is \c \@nodeset \c 745 /// nodeset_name, but the \c nodeset_name may be empty. 746 746 /// 747 747 /// The first line of the section contains the names of the maps separated -
lemon/lp_base.h
r2366 r2368 1061 1061 _setColName(_lpId(c), name); 1062 1062 } 1063 1064 /// Get the column by its name 1065 1066 ///\param name The name of the column 1067 ///\return the proper column or \c INVALID 1068 Col colByName(const std::string& name) const { 1069 int k = _colByName(name); 1070 return k != -1 ? Col(cols.fixId(k)) : Col(INVALID); 1071 } 1063 1072 1064 1073 /// Set an element of the coefficient matrix of the LP -
lemon/lp_glpk.cc
r2366 r2368 29 29 cols = _lp_bits::LpId(1); 30 30 lp = lpx_create_prob(); 31 lpx_create_index(lp); 31 32 ///\todo control function for this: 32 33 lpx_set_int_parm(lp, LPX_K_DUAL, 1); -
lemon/lp_soplex.cc
r2366 r2368 77 77 void LpSoplex::_eraseCol(int i) { 78 78 soplex->removeCol(i); 79 invColNames.erase(colNames[i]); 79 80 colNames[i] = colNames.back(); 81 invColNames[colNames.back()] = i; 80 82 colNames.pop_back(); 81 83 primal_value[i] = primal_value.back(); -
lemon/lp_utils.h
r2364 r2368 25 25 #include <lemon/lemon_writer.h> 26 26 27 #include <map> 28 #include <set> 29 30 27 31 namespace lemon { 28 32 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. 29 315 class LpReader : public LemonReader::SectionReader { 30 316 typedef LemonReader::SectionReader Parent; … … 34 320 /// \brief Constructor. 35 321 /// 36 /// Constructor for LpReader. It creates the LpReader and attach 322 /// Constructor for LpReader. It creates the LpReader and attachs 37 323 /// it into the given LemonReader. The lp reader will add 38 324 /// variables, constraints and objective function to the … … 45 331 /// \brief Destructor. 46 332 /// 47 /// Destructor for NodeSetReader.333 /// Destructor for LpReader. 48 334 virtual ~LpReader() {} 49 335 … … 69 355 private: 70 356 71 enum SubSection{357 enum Part { 72 358 CONSTRAINTS, BOUNDS, OBJECTIVE 73 359 }; … … 211 497 lp.colUpperBound(c, v); 212 498 } 499 is >> std::ws; 213 500 if (is.get(x)) { 214 501 throw DataFormatError("Wrong variable bounds format"); … … 344 631 is.putback(x); 345 632 } 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) { 350 635 c = lp.addCol(); 351 cols.insert(std::make_pair(var, c));352 636 lp.colName(c, var); 353 637 } … … 391 675 return (c >= '0' && c <= '9') || c == '.'; 392 676 } 393 677 394 678 static bool varChar(char c) { 395 679 return (c >= '0' && c <= '9') || … … 406 690 virtual void read(std::istream& is) { 407 691 std::string line; 408 SubSection sub= CONSTRAINTS;692 Part part = CONSTRAINTS; 409 693 while (getline(is, line)) { 410 694 std::istringstream ls(line); … … 412 696 ls >> type; 413 697 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"); 415 703 } 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"); 417 709 } 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"); 419 715 } else { 420 716 ls.str(line); 421 switch ( sub) {717 switch (part) { 422 718 case CONSTRAINTS: 423 719 readConstraint(ls); … … 430 726 break; 431 727 } 432 } 728 } 433 729 } 434 730 } … … 442 738 private: 443 739 444 typedef std::map<std::string, LpSolverBase::Col> ColMap;445 740 446 741 LpSolverBase& lp; 447 742 std::string name; 448 ColMap cols;449 743 }; 450 744 451 745 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. 452 796 class LpWriter : public LemonWriter::SectionWriter { 453 797 typedef LemonWriter::SectionWriter Parent; … … 458 802 /// 459 803 /// 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, 464 806 const std::string& _name = std::string()) 465 807 : Parent(_writer), lp(_lp), name(_name) {} … … 468 810 /// \brief Destructor. 469 811 /// 470 /// Destructor for NodeSetWriter.812 /// Destructor for LpWriter. 471 813 virtual ~LpWriter() {} 472 814 … … 490 832 491 833 void createCols() { 492 int num = 1; 493 494 std::map<std::string, LpSolverBase::Col> inverse; 834 int num = 0; 495 835 496 836 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) { 497 837 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()) { 502 839 std::ostringstream ls; 503 ls << " var" << num;840 ls << "x" << num; 504 841 ++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()); 507 848 } 508 849 } … … 527 868 } 528 869 first = false; 529 os << cols[jt->first]<< " ";870 os << lp.colName(jt->first) << " "; 530 871 } 531 872 if (e.constComp() < 0.0) { … … 590 931 } 591 932 592 os << cols[it]<< " ";933 os << lp.colName(it) << " "; 593 934 594 935 if (upper != LpSolverBase::INF) { … … 596 937 } 597 938 } else { 598 os << cols[it]<< " == " << upper << " ";939 os << lp.colName(it) << " == " << upper << " "; 599 940 } 600 941 os << std::endl; … … 615 956 private: 616 957 617 typedef std::map<LpSolverBase::Col, std::string> ColMap; 618 619 LpSolverBase& lp; 958 const LpSolverBase& lp; 620 959 std::string name; 621 ColMap cols;622 960 }; 623 961
Note: See TracChangeset
for help on using the changeset viewer.