|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
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. |
|
12 * |
|
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 |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_LP_UTILS_H |
|
20 #define LEMON_LP_UTILS_H |
|
21 |
|
22 #include <lemon/lp_base.h> |
|
23 |
|
24 #include <lemon/lemon_reader.h> |
|
25 |
|
26 namespace lemon { |
|
27 |
|
28 class LpReader : public LemonReader::SectionReader { |
|
29 typedef LemonReader::SectionReader Parent; |
|
30 public: |
|
31 |
|
32 |
|
33 /// \brief Constructor. |
|
34 /// |
|
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 |
|
38 /// given lp solver. |
|
39 LpReader(LemonReader& _reader, LpSolverBase& _lp, |
|
40 const std::string& _name = std::string()) |
|
41 : Parent(_reader), lp(_lp), name(_name) {} |
|
42 |
|
43 |
|
44 /// \brief Destructor. |
|
45 /// |
|
46 /// Destructor for NodeSetReader. |
|
47 virtual ~LpReader() {} |
|
48 |
|
49 private: |
|
50 LpReader(const LpReader&); |
|
51 void operator=(const LpReader&); |
|
52 |
|
53 protected: |
|
54 |
|
55 /// \brief Gives back true when the SectionReader can process |
|
56 /// the section with the given header line. |
|
57 /// |
|
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); |
|
62 std::string command; |
|
63 std::string id; |
|
64 ls >> command >> id; |
|
65 return command == "@lp" && name == id; |
|
66 } |
|
67 |
|
68 private: |
|
69 |
|
70 enum Relation { |
|
71 LE, EQ, GE |
|
72 }; |
|
73 |
|
74 std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) { |
|
75 char x; |
|
76 LpSolverBase::Expr e1, e2; |
|
77 Relation op1; |
|
78 is >> std::ws; |
|
79 readExpression(is, e1); |
|
80 is >> std::ws; |
|
81 readRelation(is, op1); |
|
82 is >> std::ws; |
|
83 readExpression(is, e2); |
|
84 if (!is.get(x)) { |
|
85 if (op1 == LE) { |
|
86 c = e1 <= e2; |
|
87 } else if (op1 == GE) { |
|
88 c = e1 >= e2; |
|
89 } else { |
|
90 c = e1 == e2; |
|
91 } |
|
92 } else { |
|
93 is.putback(x); |
|
94 LpSolverBase::Expr e3; |
|
95 Relation op2; |
|
96 readRelation(is, op2); |
|
97 is >> std::ws; |
|
98 readExpression(is, e3); |
|
99 if (!e1.empty() || !e3.empty()) { |
|
100 throw DataFormatError("Wrong range format"); |
|
101 } |
|
102 if (op2 != op1 || op1 == EQ) { |
|
103 throw DataFormatError("Wrong range format"); |
|
104 } |
|
105 if (op1 == LE) { |
|
106 c = e1.constComp() <= e2 <= e3.constComp(); |
|
107 } else { |
|
108 c = e1.constComp() >= e2 >= e3.constComp(); |
|
109 } |
|
110 } |
|
111 } |
|
112 |
|
113 std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) { |
|
114 LpSolverBase::Col c; |
|
115 double d; |
|
116 char x; |
|
117 readElement(is, c, d); |
|
118 if (c != INVALID) { |
|
119 e += d * c; |
|
120 } else { |
|
121 e += d; |
|
122 } |
|
123 is >> std::ws; |
|
124 while (is.get(x) && (x == '+' || x == '-')) { |
|
125 is >> std::ws; |
|
126 readElement(is, c, d); |
|
127 if (c != INVALID) { |
|
128 e += (x == '+' ? d : -d) * c; |
|
129 } else { |
|
130 e += (x == '+' ? d : -d); |
|
131 } |
|
132 is >> std::ws; |
|
133 } |
|
134 if (!is) { |
|
135 is.clear(); |
|
136 } else { |
|
137 is.putback(x); |
|
138 } |
|
139 return is; |
|
140 } |
|
141 |
|
142 std::istream& readElement(std::istream& is, |
|
143 LpSolverBase::Col& c, double& d) { |
|
144 d = 1.0; |
|
145 c = INVALID; |
|
146 char x, y; |
|
147 if (!is.get(x)) throw DataFormatError("Cannot find lp element"); |
|
148 if (x == '+' || x == '-') { |
|
149 is >> std::ws; |
|
150 d *= x == '-' ? -1 : 1; |
|
151 while (is.get(x) && (x == '+' || x == '-')) { |
|
152 d *= x == '-' ? -1 : 1; |
|
153 is >> std::ws; |
|
154 } |
|
155 if (!is) throw DataFormatError("Cannot find lp element"); |
|
156 } |
|
157 if (numFirstChar(x)) { |
|
158 is.putback(x); |
|
159 double e; |
|
160 readNum(is, e); |
|
161 d *= e; |
|
162 } else if (varFirstChar(x)) { |
|
163 is.putback(x); |
|
164 LpSolverBase::Col f; |
|
165 readCol(is, f); |
|
166 c = f; |
|
167 } else { |
|
168 throw DataFormatError("Invalid expression format"); |
|
169 } |
|
170 is >> std::ws; |
|
171 while (is.get(y) && (y == '*' || y == '/')) { |
|
172 is >> std::ws; |
|
173 if (!is.get(x)) throw DataFormatError("Cannot find lp element"); |
|
174 if (x == '+' || x == '-') { |
|
175 is >> std::ws; |
|
176 d *= x == '-' ? -1 : 1; |
|
177 while (is.get(x) && (x == '+' || x == '-')) { |
|
178 d *= x == '-' ? -1 : 1; |
|
179 is >> std::ws; |
|
180 } |
|
181 if (!is) throw DataFormatError("Cannot find lp element"); |
|
182 } |
|
183 if (numFirstChar(x)) { |
|
184 is.putback(x); |
|
185 double e; |
|
186 readNum(is, e); |
|
187 if (y == '*') { |
|
188 d *= e; |
|
189 } else { |
|
190 d /= e; |
|
191 } |
|
192 } else if (varFirstChar(x)) { |
|
193 is.putback(x); |
|
194 LpSolverBase::Col f; |
|
195 readCol(is, f); |
|
196 if (y == '*') { |
|
197 if (c == INVALID) { |
|
198 c = f; |
|
199 } else { |
|
200 throw DataFormatError("Quadratic element in expression"); |
|
201 } |
|
202 } else { |
|
203 throw DataFormatError("Division by variable"); |
|
204 } |
|
205 } else { |
|
206 throw DataFormatError("Invalid expression format"); |
|
207 } |
|
208 is >> std::ws; |
|
209 } |
|
210 if (!is) { |
|
211 is.clear(); |
|
212 } else { |
|
213 is.putback(y); |
|
214 } |
|
215 return is; |
|
216 } |
|
217 |
|
218 std::istream& readCol(std::istream& is, LpSolverBase::Col& c) { |
|
219 char x; |
|
220 std::string var; |
|
221 while (is.get(x) && varChar(x)) { |
|
222 var += x; |
|
223 } |
|
224 if (!is) { |
|
225 is.clear(); |
|
226 } else { |
|
227 is.putback(x); |
|
228 } |
|
229 ColMap::const_iterator it = cols.find(var); |
|
230 if (cols.find(var) != cols.end()) { |
|
231 c = it->second; |
|
232 } else { |
|
233 c = lp.addCol(); |
|
234 cols.insert(std::make_pair(var, c)); |
|
235 lp.colName(c, var); |
|
236 } |
|
237 return is; |
|
238 } |
|
239 |
|
240 std::istream& readNum(std::istream& is, double& d) { |
|
241 is >> d; |
|
242 if (!is) throw DataFormatError("Wrong number format"); |
|
243 return is; |
|
244 } |
|
245 |
|
246 std::istream& readRelation(std::istream& is, Relation& op) { |
|
247 char x, y; |
|
248 if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) { |
|
249 throw DataFormatError("Wrong relation operator"); |
|
250 } |
|
251 if (!is.get(y) || y != '=') { |
|
252 throw DataFormatError("Wrong relation operator"); |
|
253 } |
|
254 switch (x) { |
|
255 case '<': op = LE; |
|
256 break; |
|
257 case '=': op = EQ; |
|
258 break; |
|
259 case '>': op = GE; |
|
260 break; |
|
261 } |
|
262 return is; |
|
263 } |
|
264 |
|
265 static bool relationFirstChar(char c) { |
|
266 return c == '<' || c == '=' || c == '>'; |
|
267 } |
|
268 |
|
269 static bool varFirstChar(char c) { |
|
270 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); |
|
271 } |
|
272 |
|
273 static bool numFirstChar(char c) { |
|
274 return (c >= '0' && c <= '9') || c == '.'; |
|
275 } |
|
276 |
|
277 static bool varChar(char c) { |
|
278 return (c >= '0' && c <= '9') || |
|
279 (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); |
|
280 } |
|
281 |
|
282 |
|
283 void addConstraint(const LpSolverBase::Constr& constr) { |
|
284 if (constr.expr().size() != 1) { |
|
285 lp.addRow(constr); |
|
286 } else { |
|
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; |
|
292 if (coeff > 0) { |
|
293 if (constr.upperBounded()) { |
|
294 lb = (constr.lowerBound() - e.constComp()) / coeff; |
|
295 } |
|
296 if (constr.lowerBounded()) { |
|
297 ub = (constr.upperBound() - e.constComp()) / coeff; |
|
298 } |
|
299 } else if (coeff < 0) { |
|
300 if (constr.upperBounded()) { |
|
301 lb = (constr.upperBound() - e.constComp()) / coeff; |
|
302 } |
|
303 if (constr.lowerBounded()) { |
|
304 ub = (constr.lowerBound() - e.constComp()) / coeff; |
|
305 } |
|
306 } else { |
|
307 lb = -LpSolverBase::INF; |
|
308 ub = LpSolverBase::INF; |
|
309 } |
|
310 lp.colLowerBound(col, lb); |
|
311 lp.colUpperBound(col, ub); |
|
312 } |
|
313 } |
|
314 |
|
315 protected: |
|
316 |
|
317 /// \brief Reader function of the section. |
|
318 /// |
|
319 /// It reads the content of the section. |
|
320 virtual void read(std::istream& is) { |
|
321 std::string line; |
|
322 std::map<std::string, LpSolverBase::Col> vars; |
|
323 while (getline(is, line)) { |
|
324 std::istringstream ls(line); |
|
325 std::string sense; |
|
326 ls >> sense; |
|
327 if (sense == "min" || sense == "max") { |
|
328 LpSolverBase::Expr expr; |
|
329 ls >> std::ws; |
|
330 readExpression(ls, expr); |
|
331 lp.setObj(expr); |
|
332 if (sense == "min") { |
|
333 lp.min(); |
|
334 } else { |
|
335 lp.max(); |
|
336 } |
|
337 } else { |
|
338 ls.str(line); |
|
339 LpSolverBase::Constr constr; |
|
340 ls >> std::ws; |
|
341 readConstraint(ls, constr); |
|
342 addConstraint(constr); |
|
343 } |
|
344 } |
|
345 } |
|
346 |
|
347 virtual void missing() { |
|
348 ErrorMessage msg; |
|
349 msg << "Lp section not found in file: @lp " << name; |
|
350 throw IoParameterError(msg.message()); |
|
351 } |
|
352 |
|
353 private: |
|
354 |
|
355 typedef std::map<std::string, LpSolverBase::Col> ColMap; |
|
356 |
|
357 LpSolverBase& lp; |
|
358 std::string name; |
|
359 ColMap cols; |
|
360 }; |
|
361 |
|
362 } |
|
363 |
|
364 #endif |