Better handling of inexact computation.
We do not use tolerance for excess, just for edges
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>
28 class LpReader : public LemonReader::SectionReader {
29 typedef LemonReader::SectionReader Parent;
33 /// \brief Constructor.
35 /// Constructor for LpReader. It creates the LpReader and attach
36 /// it into the given LemonReader. The lp reader will add
37 /// variables, constraints and objective function to the
39 LpReader(LemonReader& _reader, LpSolverBase& _lp,
40 const std::string& _name = std::string())
41 : Parent(_reader), lp(_lp), name(_name) {}
44 /// \brief Destructor.
46 /// Destructor for NodeSetReader.
47 virtual ~LpReader() {}
50 LpReader(const LpReader&);
51 void operator=(const LpReader&);
55 /// \brief Gives back true when the SectionReader can process
56 /// the section with the given header line.
58 /// It gives back true when the header line starts with \c \@lp,
59 /// and the header line's name and the nodeset's name are the same.
60 virtual bool header(const std::string& line) {
61 std::istringstream ls(line);
65 return command == "@lp" && name == id;
74 std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
76 LpSolverBase::Expr e1, e2;
79 readExpression(is, e1);
81 readRelation(is, op1);
83 readExpression(is, e2);
87 } else if (op1 == GE) {
94 LpSolverBase::Expr e3;
96 readRelation(is, op2);
98 readExpression(is, e3);
99 if (!e1.empty() || !e3.empty()) {
100 throw DataFormatError("Wrong range format");
102 if (op2 != op1 || op1 == EQ) {
103 throw DataFormatError("Wrong range format");
106 c = e1.constComp() <= e2 <= e3.constComp();
108 c = e1.constComp() >= e2 >= e3.constComp();
113 std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
117 readElement(is, c, d);
124 while (is.get(x) && (x == '+' || x == '-')) {
126 readElement(is, c, d);
128 e += (x == '+' ? d : -d) * c;
130 e += (x == '+' ? d : -d);
142 std::istream& readElement(std::istream& is,
143 LpSolverBase::Col& c, double& d) {
147 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
148 if (x == '+' || x == '-') {
150 d *= x == '-' ? -1 : 1;
151 while (is.get(x) && (x == '+' || x == '-')) {
152 d *= x == '-' ? -1 : 1;
155 if (!is) throw DataFormatError("Cannot find lp element");
157 if (numFirstChar(x)) {
162 } else if (varFirstChar(x)) {
168 throw DataFormatError("Invalid expression format");
171 while (is.get(y) && (y == '*' || y == '/')) {
173 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
174 if (x == '+' || x == '-') {
176 d *= x == '-' ? -1 : 1;
177 while (is.get(x) && (x == '+' || x == '-')) {
178 d *= x == '-' ? -1 : 1;
181 if (!is) throw DataFormatError("Cannot find lp element");
183 if (numFirstChar(x)) {
192 } else if (varFirstChar(x)) {
200 throw DataFormatError("Quadratic element in expression");
203 throw DataFormatError("Division by variable");
206 throw DataFormatError("Invalid expression format");
218 std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
221 while (is.get(x) && varChar(x)) {
229 ColMap::const_iterator it = cols.find(var);
230 if (cols.find(var) != cols.end()) {
234 cols.insert(std::make_pair(var, c));
240 std::istream& readNum(std::istream& is, double& d) {
242 if (!is) throw DataFormatError("Wrong number format");
246 std::istream& readRelation(std::istream& is, Relation& op) {
248 if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
249 throw DataFormatError("Wrong relation operator");
251 if (!is.get(y) || y != '=') {
252 throw DataFormatError("Wrong relation operator");
265 static bool relationFirstChar(char c) {
266 return c == '<' || c == '=' || c == '>';
269 static bool varFirstChar(char c) {
270 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
273 static bool numFirstChar(char c) {
274 return (c >= '0' && c <= '9') || c == '.';
277 static bool varChar(char c) {
278 return (c >= '0' && c <= '9') ||
279 (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
283 void addConstraint(const LpSolverBase::Constr& constr) {
284 if (constr.expr().size() != 1) {
287 Lp::Expr e = constr.expr();
288 LpSolverBase::Col col = e.begin()->first;
289 double coeff = e.begin()->second;
290 double lb = LpSolverBase::NaN;
291 double ub = LpSolverBase::NaN;
293 if (constr.upperBounded()) {
294 lb = (constr.lowerBound() - e.constComp()) / coeff;
296 if (constr.lowerBounded()) {
297 ub = (constr.upperBound() - e.constComp()) / coeff;
299 } else if (coeff < 0) {
300 if (constr.upperBounded()) {
301 lb = (constr.upperBound() - e.constComp()) / coeff;
303 if (constr.lowerBounded()) {
304 ub = (constr.lowerBound() - e.constComp()) / coeff;
307 lb = -LpSolverBase::INF;
308 ub = LpSolverBase::INF;
310 lp.colLowerBound(col, lb);
311 lp.colUpperBound(col, ub);
317 /// \brief Reader function of the section.
319 /// It reads the content of the section.
320 virtual void read(std::istream& is) {
322 std::map<std::string, LpSolverBase::Col> vars;
323 while (getline(is, line)) {
324 std::istringstream ls(line);
327 if (sense == "min" || sense == "max") {
328 LpSolverBase::Expr expr;
330 readExpression(ls, expr);
332 if (sense == "min") {
339 LpSolverBase::Constr constr;
341 readConstraint(ls, constr);
342 addConstraint(constr);
347 virtual void missing() {
349 msg << "Lp section not found in file: @lp " << name;
350 throw IoParameterError(msg.message());
355 typedef std::map<std::string, LpSolverBase::Col> ColMap;