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>
29 class LpReader : public LemonReader::SectionReader {
30 typedef LemonReader::SectionReader Parent;
34 /// \brief Constructor.
36 /// Constructor for LpReader. It creates the LpReader and attach
37 /// it into the given LemonReader. The lp reader will add
38 /// variables, constraints and objective function to the
40 LpReader(LemonReader& _reader, LpSolverBase& _lp,
41 const std::string& _name = std::string())
42 : Parent(_reader), lp(_lp), name(_name) {}
45 /// \brief Destructor.
47 /// Destructor for NodeSetReader.
48 virtual ~LpReader() {}
51 LpReader(const LpReader&);
52 void operator=(const LpReader&);
56 /// \brief Gives back true when the SectionReader can process
57 /// the section with the given header line.
59 /// It gives back true when the header line starts with \c \@lp,
60 /// and the header line's name and the nodeset's name are the same.
61 virtual bool header(const std::string& line) {
62 std::istringstream ls(line);
66 return command == "@lp" && name == id;
72 CONSTRAINTS, BOUNDS, OBJECTIVE
79 std::istream& readConstraint(std::istream& is) {
80 LpSolverBase::Constr c;
82 LpSolverBase::Expr e1, e2;
85 readExpression(is, e1);
87 readRelation(is, op1);
89 readExpression(is, e2);
99 } else if (op1 == GE) {
100 if (e1.size() == 0) {
106 if (e1.size() == 0) {
114 LpSolverBase::Expr e3;
116 readRelation(is, op2);
118 readExpression(is, e3);
119 if (!e1.empty() || !e3.empty()) {
120 throw DataFormatError("Wrong range format");
122 if (op2 != op1 || op1 == EQ) {
123 throw DataFormatError("Wrong range format");
126 c = e1.constComp() <= e2 <= e3.constComp();
128 c = e1.constComp() >= e2 >= e3.constComp();
132 throw DataFormatError("Wrong variable bounds format");
139 std::istream& readObjective(std::istream& is) {
143 if (sense != "min" && sense != "max") {
144 throw DataFormatError("Wrong objective function format");
146 LpSolverBase::Expr expr;
148 readExpression(is, expr);
150 if (sense == "min") {
158 std::istream& readBounds(std::istream& is) {
163 throw DataFormatError("Wrong variable bounds format");
165 if (varFirstChar(x)) {
170 readRelation(is, op1);
174 lp.colLowerBound(c, v);
175 lp.colUpperBound(c, v);
176 } else if (op1 == LE) {
177 lp.colUpperBound(c, v);
179 lp.colLowerBound(c, v);
183 throw DataFormatError("Wrong variable bounds format");
191 readRelation(is, op1);
199 readRelation(is, op2);
203 if (op2 != op1 || op1 == EQ) {
204 throw DataFormatError("Wrong range format");
207 lp.colLowerBound(c, v);
208 lp.colUpperBound(c, w);
210 lp.colLowerBound(c, w);
211 lp.colUpperBound(c, v);
214 throw DataFormatError("Wrong variable bounds format");
218 lp.colLowerBound(c, v);
219 lp.colUpperBound(c, v);
220 } else if (op1 == LE) {
221 lp.colLowerBound(c, v);
223 lp.colUpperBound(c, v);
230 std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
234 readElement(is, c, d);
241 while (is.get(x) && (x == '+' || x == '-')) {
243 readElement(is, c, d);
245 e += (x == '+' ? d : -d) * c;
247 e += (x == '+' ? d : -d);
259 std::istream& readElement(std::istream& is,
260 LpSolverBase::Col& c, double& d) {
264 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
265 if (x == '+' || x == '-') {
267 d *= x == '-' ? -1 : 1;
268 while (is.get(x) && (x == '+' || x == '-')) {
269 d *= x == '-' ? -1 : 1;
272 if (!is) throw DataFormatError("Cannot find lp element");
274 if (numFirstChar(x)) {
279 } else if (varFirstChar(x)) {
285 throw DataFormatError("Invalid expression format");
288 while (is.get(y) && (y == '*' || y == '/')) {
290 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
291 if (x == '+' || x == '-') {
293 d *= x == '-' ? -1 : 1;
294 while (is.get(x) && (x == '+' || x == '-')) {
295 d *= x == '-' ? -1 : 1;
298 if (!is) throw DataFormatError("Cannot find lp element");
300 if (numFirstChar(x)) {
309 } else if (varFirstChar(x)) {
317 throw DataFormatError("Quadratic element in expression");
320 throw DataFormatError("Division by variable");
323 throw DataFormatError("Invalid expression format");
335 std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
338 while (is.get(x) && varChar(x)) {
346 ColMap::const_iterator it = cols.find(var);
347 if (cols.find(var) != cols.end()) {
351 cols.insert(std::make_pair(var, c));
357 std::istream& readNum(std::istream& is, double& d) {
359 if (!is) throw DataFormatError("Wrong number format");
363 std::istream& readRelation(std::istream& is, Relation& op) {
365 if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
366 throw DataFormatError("Wrong relation operator");
368 if (!is.get(y) || y != '=') {
369 throw DataFormatError("Wrong relation operator");
382 static bool relationFirstChar(char c) {
383 return c == '<' || c == '=' || c == '>';
386 static bool varFirstChar(char c) {
387 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
390 static bool numFirstChar(char c) {
391 return (c >= '0' && c <= '9') || c == '.';
394 static bool varChar(char c) {
395 return (c >= '0' && c <= '9') ||
396 (c >= 'a' && c <= 'z') ||
397 (c >= 'A' && c <= 'Z') ||
398 c == '[' || c == ']';
403 /// \brief Reader function of the section.
405 /// It reads the content of the section.
406 virtual void read(std::istream& is) {
408 SubSection sub = CONSTRAINTS;
409 while (getline(is, line)) {
410 std::istringstream ls(line);
413 if (type == "constraints") {
415 } else if (type == "bounds") {
417 } else if (type == "objective") {
436 virtual void missing() {
438 msg << "Lp section not found in file: @lp " << name;
439 throw IoParameterError(msg.message());
444 typedef std::map<std::string, LpSolverBase::Col> ColMap;
452 class LpWriter : public LemonWriter::SectionWriter {
453 typedef LemonWriter::SectionWriter Parent;
457 /// \brief Constructor.
459 /// 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
463 LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
464 const std::string& _name = std::string())
465 : Parent(_writer), lp(_lp), name(_name) {}
468 /// \brief Destructor.
470 /// Destructor for NodeSetWriter.
471 virtual ~LpWriter() {}
474 LpWriter(const LpWriter&);
475 void operator=(const LpWriter&);
479 /// \brief Gives back true when the SectionWriter can process
480 /// the section with the given header line.
482 /// It gives back the header line of the \c \@lp section.
483 virtual std::string header() {
484 std::ostringstream ls;
485 ls << "@lp " << name;
494 std::map<std::string, LpSolverBase::Col> inverse;
496 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
497 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));
502 std::ostringstream ls;
505 cols.insert(std::make_pair(it, ls.str()));
506 inverse.insert(std::make_pair(ls.str(), it));
511 void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
513 for (LpSolverBase::Expr::const_iterator jt = e.begin();
514 jt != e.end(); ++jt) {
515 if (jt->second < 0.0) {
517 if (jt->second != -1.0) {
518 os << -jt->second << " * ";
520 } else if (jt->second > 0.0) {
524 if (jt->second != 1.0) {
525 os << jt->second << " * ";
529 os << cols[jt->first] << " ";
531 if (e.constComp() < 0.0) {
532 os << "- " << -e.constComp() << " ";
533 } else if (e.constComp() > 0.0) {
537 os << e.constComp() << " ";
543 /// \brief Writer function of the section.
545 /// It writes the content of the section.
546 virtual void write(std::ostream& os) {
549 os << "constraints" << std::endl;
551 for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
553 lp.getRowBounds(it, lower, upper);
554 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
558 if (lower != upper) {
559 if (lower != -LpSolverBase::INF) {
560 os << lower << " <= ";
563 writeExpression(os, lp.row(it));
565 if (upper != LpSolverBase::INF) {
566 os << "<= " << upper << " ";
570 writeExpression(os, lp.row(it));
571 os << "== " << upper << " ";
578 os << "bounds" << std::endl;
580 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
581 double lower = lp.colLowerBound(it);
582 double upper = lp.colUpperBound(it);
583 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
587 if (lower != upper) {
588 if (lower != -LpSolverBase::INF) {
589 os << lower << " <= ";
592 os << cols[it] << " ";
594 if (upper != LpSolverBase::INF) {
595 os << "<= " << upper << " ";
598 os << cols[it] << " == " << upper << " ";
603 os << "objective" << std::endl;
610 writeExpression(os, lp.obj());
617 typedef std::map<LpSolverBase::Col, std::string> ColMap;