3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_LP_UTILS_H
20 #define LEMON_LP_UTILS_H
22 #include <lemon/lp_base.h>
24 #include <lemon/lemon_reader.h>
25 #include <lemon/lemon_writer.h>
33 /// \ingroup gen_opt_tools
35 /// \brief The map for the result of the lp variables.
37 /// The map for the result of the lp variables.
40 typedef LpSolverBase::Col Key;
41 typedef LpSolverBase::Value Value;
43 /// \brief Constructor
46 LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
47 LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
48 return lp.primal(col);
51 const LpSolverBase& lp;
54 /// \ingroup gen_opt_tools
56 /// \brief The map for the name of the lp variables.
58 /// The map for the name of the lp variables.
61 typedef LpSolverBase::Col Key;
62 typedef std::string Value;
64 /// \brief Constructor
67 LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
68 std::string operator[](const LpSolverBase::Col col) const {
69 return lp.colName(col);
72 const LpSolverBase& lp;
75 /// \ingroup gen_opt_tools
77 /// \brief Writeable map for the name of the lp variables.
79 /// Writeable map for the name of the lp variables.
80 class LpColNameWriteMap {
82 typedef LpSolverBase::Col Key;
83 typedef std::string Value;
85 /// \brief Constructor
88 LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
89 std::string operator[](const LpSolverBase::Col col) const {
90 return lp.colName(col);
92 void set(const LpSolverBase::Col col, const std::string& name) {
93 lp.colName(col, name);
99 /// \ingroup gen_opt_tools
101 /// \brief Returns an \ref LpColNameMap class
103 /// This function just returns an \ref LpColNameMap class.
104 /// \relates LpColNameMap
105 LpColNameMap lpColNameMap(const LpSolverBase& lp) {
106 return LpColNameMap(lp);
109 LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
110 return LpColNameWriteMap(lp);
113 /// \ingroup gen_opt_tools
115 /// \brief Lp variable item reader for Lemon IO
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:
124 /// Graph::EdgeMap<Lp::Col> var(graph);
126 /// GraphReader<Graph> reader(cin, graph);
127 /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
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.
139 /// \brief The value type of reader.
141 /// The value type of reader.
142 typedef LpSolverBase::Col Value;
144 /// \brief Constructor for the reader.
146 /// Constructor for the reader.
147 LpColReader(LpSolverBase& _lp) : lp(_lp) {}
149 /// \brief Reads an lp variable from the given stream.
151 /// Reads an lp variable string from the given stream.
152 void read(std::istream& is, LpSolverBase::Col& col) const {
156 throw DataFormatError("Wrong Lp Column format!");
157 if (varFirstChar(x)) {
161 while (is.get(x) && varChar(x)) {
169 col = lp.colByName(var);
170 if (col == INVALID) {
172 lp.colName(col, var);
174 } else if (x == '-') {
178 std::cerr << x << std::endl;
179 throw DataFormatError("Wrong Lp Column format");
185 static bool varFirstChar(char c) {
186 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
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 == ']';
200 /// \ingroup gen_opt_tools
202 /// \brief Lp variable item writer for Lemon IO
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:
211 /// Graph::EdgeMap<Lp::Col> var(graph);
213 /// GraphWriter<Graph> writer(cin, graph);
214 /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
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.
224 /// \brief The value type of writer.
226 /// The value type of writer.
227 typedef LpSolverBase::Col Value;
229 /// \brief Constructor for the writer.
231 /// Constructor for the writer.
232 LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
234 /// \brief Writes an lp variable to the given stream.
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);
241 std::ostringstream ls;
244 while (lp.colByName(ls.str()) != INVALID) {
245 ls.str(std::string());
249 const_cast<LpSolverBase&>(lp).colName(col, ls.str());
261 const LpSolverBase& lp;
266 /// \ingroup gen_opt_tools
268 /// \brief Lp section reader for lemon IO
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.
277 /// 2 * x1 + x3 / 2 <= 7
278 /// x2 + -3 * x3 >= 8
279 /// 3 <= x2 - 2 * x1 <= 8
285 /// min x1 + 2 * x2 - x3
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.
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.
296 /// The third part is the objective function, it should start with
297 /// \c min or \c max and then a valid linear expression.
299 /// The reader constructs automatically the variable for a name if
300 /// there is not already a variable with the same name.
302 /// The basic way to read an LP problem is made by the next code:
306 /// LemonReader reader(filename_or_istream);
307 /// LpReader lpreader(reader, lp);
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.
315 class LpReader : public LemonReader::SectionReader {
316 typedef LemonReader::SectionReader Parent;
320 /// \brief Constructor.
322 /// Constructor for LpReader. It creates the LpReader and attachs
323 /// it into the given LemonReader. The lp reader will add
324 /// variables, constraints and objective function to the
326 LpReader(LemonReader& _reader, LpSolverBase& _lp,
327 const std::string& _name = std::string())
328 : Parent(_reader), lp(_lp), name(_name) {}
331 /// \brief Destructor.
333 /// Destructor for LpReader.
334 virtual ~LpReader() {}
337 LpReader(const LpReader&);
338 void operator=(const LpReader&);
342 /// \brief Gives back true when the SectionReader can process
343 /// the section with the given header line.
345 /// It gives back true when the header line starts with \c \@lp,
346 /// and the header line's name and the nodeset's name are the same.
347 virtual bool header(const std::string& line) {
348 std::istringstream ls(line);
352 return command == "@lp" && name == id;
358 CONSTRAINTS, BOUNDS, OBJECTIVE
365 std::istream& readConstraint(std::istream& is) {
366 LpSolverBase::Constr c;
368 LpSolverBase::Expr e1, e2;
371 readExpression(is, e1);
373 readRelation(is, op1);
375 readExpression(is, e2);
379 if (e1.size() == 0) {
385 } else if (op1 == GE) {
386 if (e1.size() == 0) {
392 if (e1.size() == 0) {
400 LpSolverBase::Expr e3;
402 readRelation(is, op2);
404 readExpression(is, e3);
405 if (!e1.empty() || !e3.empty()) {
406 throw DataFormatError("Wrong range format");
408 if (op2 != op1 || op1 == EQ) {
409 throw DataFormatError("Wrong range format");
412 c = e1.constComp() <= e2 <= e3.constComp();
414 c = e1.constComp() >= e2 >= e3.constComp();
418 throw DataFormatError("Wrong variable bounds format");
425 std::istream& readObjective(std::istream& is) {
429 if (sense != "min" && sense != "max") {
430 throw DataFormatError("Wrong objective function format");
432 LpSolverBase::Expr expr;
434 readExpression(is, expr);
436 if (sense == "min") {
444 std::istream& readBounds(std::istream& is) {
449 throw DataFormatError("Wrong variable bounds format");
451 if (varFirstChar(x)) {
456 readRelation(is, op1);
460 lp.colLowerBound(c, v);
461 lp.colUpperBound(c, v);
462 } else if (op1 == LE) {
463 lp.colUpperBound(c, v);
465 lp.colLowerBound(c, v);
469 throw DataFormatError("Wrong variable bounds format");
477 readRelation(is, op1);
485 readRelation(is, op2);
489 if (op2 != op1 || op1 == EQ) {
490 throw DataFormatError("Wrong range format");
493 lp.colLowerBound(c, v);
494 lp.colUpperBound(c, w);
496 lp.colLowerBound(c, w);
497 lp.colUpperBound(c, v);
501 throw DataFormatError("Wrong variable bounds format");
505 lp.colLowerBound(c, v);
506 lp.colUpperBound(c, v);
507 } else if (op1 == LE) {
508 lp.colLowerBound(c, v);
510 lp.colUpperBound(c, v);
517 std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
521 readElement(is, c, d);
528 while (is.get(x) && (x == '+' || x == '-')) {
530 readElement(is, c, d);
532 e += (x == '+' ? d : -d) * c;
534 e += (x == '+' ? d : -d);
546 std::istream& readElement(std::istream& is,
547 LpSolverBase::Col& c, double& d) {
551 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
552 if (x == '+' || x == '-') {
554 d *= x == '-' ? -1 : 1;
555 while (is.get(x) && (x == '+' || x == '-')) {
556 d *= x == '-' ? -1 : 1;
559 if (!is) throw DataFormatError("Cannot find lp element");
561 if (numFirstChar(x)) {
566 } else if (varFirstChar(x)) {
572 throw DataFormatError("Invalid expression format");
575 while (is.get(y) && (y == '*' || y == '/')) {
577 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
578 if (x == '+' || x == '-') {
580 d *= x == '-' ? -1 : 1;
581 while (is.get(x) && (x == '+' || x == '-')) {
582 d *= x == '-' ? -1 : 1;
585 if (!is) throw DataFormatError("Cannot find lp element");
587 if (numFirstChar(x)) {
596 } else if (varFirstChar(x)) {
604 throw DataFormatError("Quadratic element in expression");
607 throw DataFormatError("Division by variable");
610 throw DataFormatError("Invalid expression format");
622 std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
625 while (is.get(x) && varChar(x)) {
633 c = lp.colByName(var);
641 std::istream& readNum(std::istream& is, double& d) {
643 if (!is) throw DataFormatError("Wrong number format");
647 std::istream& readRelation(std::istream& is, Relation& op) {
649 if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
650 throw DataFormatError("Wrong relation operator");
652 if (!is.get(y) || y != '=') {
653 throw DataFormatError("Wrong relation operator");
666 static bool relationFirstChar(char c) {
667 return c == '<' || c == '=' || c == '>';
670 static bool varFirstChar(char c) {
671 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
674 static bool numFirstChar(char c) {
675 return (c >= '0' && c <= '9') || c == '.';
678 static bool varChar(char c) {
679 return (c >= '0' && c <= '9') ||
680 (c >= 'a' && c <= 'z') ||
681 (c >= 'A' && c <= 'Z') ||
682 c == '[' || c == ']';
687 /// \brief Reader function of the section.
689 /// It reads the content of the section.
690 virtual void read(std::istream& is) {
692 Part part = CONSTRAINTS;
693 while (getline(is, line)) {
694 std::istringstream ls(line);
697 if (type == "constraints") {
702 throw DataFormatError("Wrong Lp format");
703 } else if (type == "bounds") {
708 throw DataFormatError("Wrong Lp format");
709 } else if (type == "objective") {
714 throw DataFormatError("Wrong Lp format");
732 virtual void missing() {
734 msg << "Lp section not found in file: @lp " << name;
735 throw IoParameterError(msg.message());
746 /// \ingroup gen_opt_tools
748 /// \brief Lp section writer for lemon IO
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.
757 /// 2 * x1 + x3 / 2 <= 7
758 /// x2 + -3 * x3 >= 8
759 /// 3 <= x2 - 2 * x1 <= 8
765 /// min x1 + 2 * x2 - x3
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.
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.
776 /// The third part is the objective function, it should start with
777 /// \c min or \c max and then a valid linear expression.
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.
783 /// The basic way to write an LP problem is made by the next code:
787 /// LemonWriter writer(filename_or_ostream);
788 /// LpWriter lpwriter(writer, lp);
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.
796 class LpWriter : public LemonWriter::SectionWriter {
797 typedef LemonWriter::SectionWriter Parent;
801 /// \brief Constructor.
803 /// Constructor for LpWriter. It creates the LpWriter and attach
804 /// it into the given LemonWriter.
805 LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
806 const std::string& _name = std::string())
807 : Parent(_writer), lp(_lp), name(_name) {}
810 /// \brief Destructor.
812 /// Destructor for LpWriter.
813 virtual ~LpWriter() {}
816 LpWriter(const LpWriter&);
817 void operator=(const LpWriter&);
821 /// \brief Gives back true when the SectionWriter can process
822 /// the section with the given header line.
824 /// It gives back the header line of the \c \@lp section.
825 virtual std::string header() {
826 std::ostringstream ls;
827 ls << "@lp " << name;
836 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
837 std::string name = lp.colName(it);
839 std::ostringstream ls;
842 while (lp.colByName(ls.str()) != INVALID) {
843 ls.str(std::string());
847 const_cast<LpSolverBase&>(lp).colName(it, ls.str());
852 void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
854 for (LpSolverBase::Expr::const_iterator jt = e.begin();
855 jt != e.end(); ++jt) {
856 if (jt->second < 0.0) {
858 if (jt->second != -1.0) {
859 os << -jt->second << " * ";
861 } else if (jt->second > 0.0) {
865 if (jt->second != 1.0) {
866 os << jt->second << " * ";
870 os << lp.colName(jt->first) << " ";
872 if (e.constComp() < 0.0) {
873 os << "- " << -e.constComp() << " ";
874 } else if (e.constComp() > 0.0) {
878 os << e.constComp() << " ";
884 /// \brief Writer function of the section.
886 /// It writes the content of the section.
887 virtual void write(std::ostream& os) {
890 os << "constraints" << std::endl;
892 for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
894 lp.getRowBounds(it, lower, upper);
895 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
899 if (lower != upper) {
900 if (lower != -LpSolverBase::INF) {
901 os << lower << " <= ";
904 writeExpression(os, lp.row(it));
906 if (upper != LpSolverBase::INF) {
907 os << "<= " << upper << " ";
911 writeExpression(os, lp.row(it));
912 os << "== " << upper << " ";
919 os << "bounds" << std::endl;
921 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
922 double lower = lp.colLowerBound(it);
923 double upper = lp.colUpperBound(it);
924 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
928 if (lower != upper) {
929 if (lower != -LpSolverBase::INF) {
930 os << lower << " <= ";
933 os << lp.colName(it) << " ";
935 if (upper != LpSolverBase::INF) {
936 os << "<= " << upper << " ";
939 os << lp.colName(it) << " == " << upper << " ";
944 os << "objective" << std::endl;
951 writeExpression(os, lp.obj());
958 const LpSolverBase& lp;