1 // -*- c++ -*- |
|
2 #ifndef LEMON_LP_SOLVER_WRAPPER_H |
|
3 #define LEMON_LP_SOLVER_WRAPPER_H |
|
4 |
|
5 ///\ingroup misc |
|
6 ///\file |
|
7 ///\brief Dijkstra algorithm. |
|
8 |
|
9 // #include <stdio.h> |
|
10 #include <stdlib.h> |
|
11 #include <iostream> |
|
12 #include <map> |
|
13 #include <limits> |
|
14 // #include <stdio> |
|
15 //#include <stdlib> |
|
16 extern "C" { |
|
17 #include "glpk.h" |
|
18 } |
|
19 |
|
20 #include <iostream> |
|
21 #include <vector> |
|
22 #include <string> |
|
23 #include <list> |
|
24 #include <memory> |
|
25 #include <utility> |
|
26 |
|
27 //#include <sage_graph.h> |
|
28 //#include <lemon/list_graph.h> |
|
29 //#include <lemon/graph_wrapper.h> |
|
30 #include <lemon/invalid.h> |
|
31 #include <expression.h> |
|
32 //#include <bfs_dfs.h> |
|
33 //#include <stp.h> |
|
34 //#include <lemon/max_flow.h> |
|
35 //#include <augmenting_flow.h> |
|
36 //#include <iter_map.h> |
|
37 |
|
38 using std::cout; |
|
39 using std::cin; |
|
40 using std::endl; |
|
41 |
|
42 namespace lemon { |
|
43 |
|
44 /// \addtogroup misc |
|
45 /// @{ |
|
46 |
|
47 /// \brief A partitioned vector with iterable classes. |
|
48 /// |
|
49 /// This class implements a container in which the data is stored in an |
|
50 /// stl vector, the range is partitioned into sets and each set is |
|
51 /// doubly linked in a list. |
|
52 /// That is, each class is iterable by lemon iterators, and any member of |
|
53 /// the vector can bo moved to an other class. |
|
54 template <typename T> |
|
55 class IterablePartition { |
|
56 protected: |
|
57 struct Node { |
|
58 T data; |
|
59 int prev; //invalid az -1 |
|
60 int next; |
|
61 }; |
|
62 std::vector<Node> nodes; |
|
63 struct Tip { |
|
64 int first; |
|
65 int last; |
|
66 }; |
|
67 std::vector<Tip> tips; |
|
68 public: |
|
69 /// The classes are indexed by integers from \c 0 to \c classNum()-1. |
|
70 int classNum() const { return tips.size(); } |
|
71 /// This lemon style iterator iterates through a class. |
|
72 class ClassIt; |
|
73 /// Constructor. The number of classes is to be given which is fixed |
|
74 /// over the life of the container. |
|
75 /// The partition classes are indexed from 0 to class_num-1. |
|
76 IterablePartition(int class_num) { |
|
77 for (int i=0; i<class_num; ++i) { |
|
78 Tip t; |
|
79 t.first=t.last=-1; |
|
80 tips.push_back(t); |
|
81 } |
|
82 } |
|
83 protected: |
|
84 void befuz(ClassIt it, int class_id) { |
|
85 if (tips[class_id].first==-1) { |
|
86 if (tips[class_id].last==-1) { |
|
87 nodes[it.i].prev=nodes[it.i].next=-1; |
|
88 tips[class_id].first=tips[class_id].last=it.i; |
|
89 } |
|
90 } else { |
|
91 nodes[it.i].prev=tips[class_id].last; |
|
92 nodes[it.i].next=-1; |
|
93 nodes[tips[class_id].last].next=it.i; |
|
94 tips[class_id].last=it.i; |
|
95 } |
|
96 } |
|
97 void kifuz(ClassIt it, int class_id) { |
|
98 if (tips[class_id].first==it.i) { |
|
99 if (tips[class_id].last==it.i) { |
|
100 tips[class_id].first=tips[class_id].last=-1; |
|
101 } else { |
|
102 tips[class_id].first=nodes[it.i].next; |
|
103 nodes[nodes[it.i].next].prev=-1; |
|
104 } |
|
105 } else { |
|
106 if (tips[class_id].last==it.i) { |
|
107 tips[class_id].last=nodes[it.i].prev; |
|
108 nodes[nodes[it.i].prev].next=-1; |
|
109 } else { |
|
110 nodes[nodes[it.i].next].prev=nodes[it.i].prev; |
|
111 nodes[nodes[it.i].prev].next=nodes[it.i].next; |
|
112 } |
|
113 } |
|
114 } |
|
115 public: |
|
116 /// A new element with data \c t is pushed into the vector and into class |
|
117 /// \c class_id. |
|
118 ClassIt push_back(const T& t, int class_id) { |
|
119 Node n; |
|
120 n.data=t; |
|
121 nodes.push_back(n); |
|
122 int i=nodes.size()-1; |
|
123 befuz(i, class_id); |
|
124 return i; |
|
125 } |
|
126 /// A member is moved to an other class. |
|
127 void set(ClassIt it, int old_class_id, int new_class_id) { |
|
128 kifuz(it.i, old_class_id); |
|
129 befuz(it.i, new_class_id); |
|
130 } |
|
131 /// Returns the data pointed by \c it. |
|
132 T& operator[](ClassIt it) { return nodes[it.i].data; } |
|
133 /// Returns the data pointed by \c it. |
|
134 const T& operator[](ClassIt it) const { return nodes[it.i].data; } |
|
135 ///. |
|
136 class ClassIt { |
|
137 friend class IterablePartition; |
|
138 protected: |
|
139 int i; |
|
140 public: |
|
141 /// Default constructor. |
|
142 ClassIt() { } |
|
143 /// This constructor constructs an iterator which points |
|
144 /// to the member of th container indexed by the integer _i. |
|
145 ClassIt(const int& _i) : i(_i) { } |
|
146 /// Invalid constructor. |
|
147 ClassIt(const Invalid&) : i(-1) { } |
|
148 friend bool operator<(const ClassIt& x, const ClassIt& y); |
|
149 friend std::ostream& operator<<(std::ostream& os, |
|
150 const ClassIt& it); |
|
151 }; |
|
152 friend bool operator<(const ClassIt& x, const ClassIt& y) { |
|
153 return (x.i < y.i); |
|
154 } |
|
155 friend std::ostream& operator<<(std::ostream& os, |
|
156 const ClassIt& it) { |
|
157 os << it.i; |
|
158 return os; |
|
159 } |
|
160 /// First member of class \c class_id. |
|
161 ClassIt& first(ClassIt& it, int class_id) const { |
|
162 it.i=tips[class_id].first; |
|
163 return it; |
|
164 } |
|
165 /// Next member. |
|
166 ClassIt& next(ClassIt& it) const { |
|
167 it.i=nodes[it.i].next; |
|
168 return it; |
|
169 } |
|
170 /// True iff the iterator is valid. |
|
171 bool valid(const ClassIt& it) const { return it.i!=-1; } |
|
172 }; |
|
173 |
|
174 |
|
175 /*! \e |
|
176 |
|
177 \todo A[x,y]-t cserel. Jobboldal, baloldal csere. |
|
178 \todo LEKERDEZESEK!!! |
|
179 \todo DOKSI!!!! Doxygen group!!! |
|
180 |
|
181 */ |
|
182 template <typename _Value> |
|
183 class LPSolverBase { |
|
184 public: |
|
185 /// \e |
|
186 typedef _Value Value; |
|
187 /// \e |
|
188 typedef IterablePartition<int>::ClassIt RowIt; |
|
189 /// \e |
|
190 typedef IterablePartition<int>::ClassIt ColIt; |
|
191 public: |
|
192 /// \e |
|
193 IterablePartition<int> row_iter_map; |
|
194 /// \e |
|
195 IterablePartition<int> col_iter_map; |
|
196 /// \e |
|
197 const int VALID_CLASS; |
|
198 /// \e |
|
199 const int INVALID_CLASS; |
|
200 /// \e |
|
201 static const _Value INF; |
|
202 public: |
|
203 /// \e |
|
204 LPSolverBase() : row_iter_map(2), |
|
205 col_iter_map(2), |
|
206 VALID_CLASS(0), INVALID_CLASS(1) { } |
|
207 /// \e |
|
208 virtual ~LPSolverBase() { } |
|
209 |
|
210 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
|
211 |
|
212 public: |
|
213 /// \e |
|
214 virtual void setMinimize() = 0; |
|
215 /// \e |
|
216 virtual void setMaximize() = 0; |
|
217 |
|
218 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
|
219 |
|
220 protected: |
|
221 /// \e |
|
222 virtual int _addRow() = 0; |
|
223 /// \e |
|
224 virtual int _addCol() = 0; |
|
225 /// \e |
|
226 virtual void _setRowCoeffs(int i, |
|
227 const std::vector<std::pair<int, _Value> >& coeffs) = 0; |
|
228 /// \e |
|
229 virtual void _setColCoeffs(int i, |
|
230 const std::vector<std::pair<int, _Value> >& coeffs) = 0; |
|
231 /// \e |
|
232 virtual void _eraseCol(int i) = 0; |
|
233 /// \e |
|
234 virtual void _eraseRow(int i) = 0; |
|
235 public: |
|
236 /// \e |
|
237 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED }; |
|
238 protected: |
|
239 /// \e |
|
240 /// The lower bound of a variable (column) have to be given by an |
|
241 /// extended number of type _Value, i.e. a finite number of type |
|
242 /// _Value or -INF. |
|
243 virtual void _setColLowerBound(int i, _Value value) = 0; |
|
244 /// \e |
|
245 /// The upper bound of a variable (column) have to be given by an |
|
246 /// extended number of type _Value, i.e. a finite number of type |
|
247 /// _Value or INF. |
|
248 virtual void _setColUpperBound(int i, _Value value) = 0; |
|
249 /// \e |
|
250 /// The lower bound of a variable (column) is an |
|
251 /// extended number of type _Value, i.e. a finite number of type |
|
252 /// _Value or -INF. |
|
253 virtual _Value _getColLowerBound(int i) = 0; |
|
254 /// \e |
|
255 /// The upper bound of a variable (column) is an |
|
256 /// extended number of type _Value, i.e. a finite number of type |
|
257 /// _Value or INF. |
|
258 virtual _Value _getColUpperBound(int i) = 0; |
|
259 /// \e |
|
260 virtual void _setColBounds(int i, Bound bound, |
|
261 _Value lo, _Value up) = 0; |
|
262 /// \e |
|
263 virtual void _setRowBounds(int i, Bound bound, |
|
264 _Value lo, _Value up) = 0; |
|
265 /// \e |
|
266 virtual void _setObjCoef(int i, _Value obj_coef) = 0; |
|
267 /// \e |
|
268 virtual _Value _getObjCoef(int i) = 0; |
|
269 |
|
270 //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS |
|
271 |
|
272 protected: |
|
273 virtual _Value _getPrimal(int i) = 0; |
|
274 |
|
275 //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS |
|
276 |
|
277 public: |
|
278 /// \e |
|
279 RowIt addRow() { |
|
280 int i=_addRow(); |
|
281 RowIt row_it; |
|
282 row_iter_map.first(row_it, INVALID_CLASS); |
|
283 if (row_iter_map.valid(row_it)) { //van hasznalhato hely |
|
284 row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS); |
|
285 row_iter_map[row_it]=i; |
|
286 } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
|
287 row_it=row_iter_map.push_back(i, VALID_CLASS); |
|
288 } |
|
289 return row_it; |
|
290 } |
|
291 /// \e |
|
292 ColIt addCol() { |
|
293 int i=_addCol(); |
|
294 ColIt col_it; |
|
295 col_iter_map.first(col_it, INVALID_CLASS); |
|
296 if (col_iter_map.valid(col_it)) { //van hasznalhato hely |
|
297 col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS); |
|
298 col_iter_map[col_it]=i; |
|
299 } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
|
300 col_it=col_iter_map.push_back(i, VALID_CLASS); |
|
301 } |
|
302 return col_it; |
|
303 } |
|
304 /// \e |
|
305 template <typename Begin, typename End> |
|
306 void setRowCoeffs(RowIt row_it, Begin begin, End end) { |
|
307 std::vector<std::pair<int, double> > coeffs; |
|
308 for ( ; begin!=end; ++begin) { |
|
309 coeffs.push_back(std:: |
|
310 make_pair(col_iter_map[begin->first], begin->second)); |
|
311 } |
|
312 _setRowCoeffs(row_iter_map[row_it], coeffs); |
|
313 } |
|
314 /// \e |
|
315 template <typename Begin, typename End> |
|
316 void setColCoeffs(ColIt col_it, Begin begin, End end) { |
|
317 std::vector<std::pair<int, double> > coeffs; |
|
318 for ( ; begin!=end; ++begin) { |
|
319 coeffs.push_back(std:: |
|
320 make_pair(row_iter_map[begin->first], begin->second)); |
|
321 } |
|
322 _setColCoeffs(col_iter_map[col_it], coeffs); |
|
323 } |
|
324 /// \e |
|
325 void eraseCol(const ColIt& col_it) { |
|
326 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS); |
|
327 int cols[2]; |
|
328 cols[1]=col_iter_map[col_it]; |
|
329 _eraseCol(cols[1]); |
|
330 col_iter_map[col_it]=0; //glpk specifikus, de kell ez?? |
|
331 ColIt it; |
|
332 for (col_iter_map.first(it, VALID_CLASS); |
|
333 col_iter_map.valid(it); col_iter_map.next(it)) { |
|
334 if (col_iter_map[it]>cols[1]) --col_iter_map[it]; |
|
335 } |
|
336 } |
|
337 /// \e |
|
338 void eraseRow(const RowIt& row_it) { |
|
339 row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS); |
|
340 int rows[2]; |
|
341 rows[1]=row_iter_map[row_it]; |
|
342 _eraseRow(rows[1]); |
|
343 row_iter_map[row_it]=0; //glpk specifikus, de kell ez?? |
|
344 RowIt it; |
|
345 for (row_iter_map.first(it, VALID_CLASS); |
|
346 row_iter_map.valid(it); row_iter_map.next(it)) { |
|
347 if (row_iter_map[it]>rows[1]) --row_iter_map[it]; |
|
348 } |
|
349 } |
|
350 /// \e |
|
351 void setColLowerBound(ColIt col_it, _Value lo) { |
|
352 _setColLowerBound(col_iter_map[col_it], lo); |
|
353 } |
|
354 /// \e |
|
355 void setColUpperBound(ColIt col_it, _Value up) { |
|
356 _setColUpperBound(col_iter_map[col_it], up); |
|
357 } |
|
358 /// \e |
|
359 _Value getColLowerBound(ColIt col_it) { |
|
360 return _getColLowerBound(col_iter_map[col_it]); |
|
361 } |
|
362 /// \e |
|
363 _Value getColUpperBound(ColIt col_it) { |
|
364 return _getColUpperBound(col_iter_map[col_it]); |
|
365 } |
|
366 /// \e |
|
367 void setColBounds(const ColIt& col_it, Bound bound, |
|
368 _Value lo, _Value up) { |
|
369 _setColBounds(col_iter_map[col_it], bound, lo, up); |
|
370 } |
|
371 /// \e |
|
372 void setRowBounds(const RowIt& row_it, Bound bound, |
|
373 _Value lo, _Value up) { |
|
374 _setRowBounds(row_iter_map[row_it], bound, lo, up); |
|
375 } |
|
376 /// \e |
|
377 void setObjCoef(const ColIt& col_it, _Value obj_coef) { |
|
378 _setObjCoef(col_iter_map[col_it], obj_coef); |
|
379 } |
|
380 /// \e |
|
381 _Value getObjCoef(const ColIt& col_it) { |
|
382 return _getObjCoef(col_iter_map[col_it]); |
|
383 } |
|
384 |
|
385 //MOST HIGH LEVEL, USER FRIEND FUNCTIONS |
|
386 |
|
387 /// \e |
|
388 typedef Expr<ColIt, _Value> Expression; |
|
389 /// \e |
|
390 typedef Expr<RowIt, _Value> DualExpression; |
|
391 /// \e |
|
392 void setRowCoeffs(RowIt row_it, const Expression& expr) { |
|
393 std::vector<std::pair<int, _Value> > row_coeffs; |
|
394 for(typename Expression::Data::const_iterator i=expr.data.begin(); |
|
395 i!=expr.data.end(); ++i) { |
|
396 row_coeffs.push_back(std::make_pair |
|
397 (col_iter_map[(*i).first], (*i).second)); |
|
398 } |
|
399 _setRowCoeffs(row_iter_map[row_it], row_coeffs); |
|
400 } |
|
401 /// \e |
|
402 void setColCoeffs(ColIt col_it, const DualExpression& expr) { |
|
403 std::vector<std::pair<int, _Value> > col_coeffs; |
|
404 for(typename DualExpression::Data::const_iterator i=expr.data.begin(); |
|
405 i!=expr.data.end(); ++i) { |
|
406 col_coeffs.push_back(std::make_pair |
|
407 (row_iter_map[(*i).first], (*i).second)); |
|
408 } |
|
409 _setColCoeffs(col_iter_map[col_it], col_coeffs); |
|
410 } |
|
411 /// \e |
|
412 void setObjCoeffs(const Expression& expr) { |
|
413 for(typename Expression::Data::const_iterator i=expr.data.begin(); |
|
414 i!=expr.data.end(); ++i) { |
|
415 setObjCoef((*i).first, (*i).second); |
|
416 } |
|
417 } |
|
418 //SOLVER FUNCTIONS |
|
419 |
|
420 /// \e |
|
421 virtual void solveSimplex() = 0; |
|
422 /// \e |
|
423 virtual void solvePrimalSimplex() = 0; |
|
424 /// \e |
|
425 virtual void solveDualSimplex() = 0; |
|
426 /// \e |
|
427 |
|
428 //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS |
|
429 |
|
430 public: |
|
431 _Value getPrimal(const ColIt& col_it) { |
|
432 return _getPrimal(col_iter_map[col_it]); |
|
433 } |
|
434 /// \e |
|
435 virtual _Value getObjVal() = 0; |
|
436 |
|
437 //OTHER FUNCTIONS |
|
438 |
|
439 /// \e |
|
440 virtual int rowNum() const = 0; |
|
441 /// \e |
|
442 virtual int colNum() const = 0; |
|
443 /// \e |
|
444 virtual int warmUp() = 0; |
|
445 /// \e |
|
446 virtual void printWarmUpStatus(int i) = 0; |
|
447 /// \e |
|
448 virtual int getPrimalStatus() = 0; |
|
449 /// \e |
|
450 virtual void printPrimalStatus(int i) = 0; |
|
451 /// \e |
|
452 virtual int getDualStatus() = 0; |
|
453 /// \e |
|
454 virtual void printDualStatus(int i) = 0; |
|
455 /// Returns the status of the slack variable assigned to row \c row_it. |
|
456 virtual int getRowStat(const RowIt& row_it) = 0; |
|
457 /// \e |
|
458 virtual void printRowStatus(int i) = 0; |
|
459 /// Returns the status of the variable assigned to column \c col_it. |
|
460 virtual int getColStat(const ColIt& col_it) = 0; |
|
461 /// \e |
|
462 virtual void printColStatus(int i) = 0; |
|
463 }; |
|
464 |
|
465 template <typename _Value> |
|
466 const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity(); |
|
467 |
|
468 |
|
469 /// \brief Wrappers for LP solvers |
|
470 /// |
|
471 /// This class implements a lemon wrapper for glpk. |
|
472 /// Later other LP-solvers will be wrapped into lemon. |
|
473 /// The aim of this class is to give a general surface to different |
|
474 /// solvers, i.e. it makes possible to write algorithms using LP's, |
|
475 /// in which the solver can be changed to an other one easily. |
|
476 class LPGLPK : public LPSolverBase<double> { |
|
477 public: |
|
478 typedef LPSolverBase<double> Parent; |
|
479 |
|
480 public: |
|
481 /// \e |
|
482 LPX* lp; |
|
483 |
|
484 public: |
|
485 /// \e |
|
486 LPGLPK() : Parent(), |
|
487 lp(lpx_create_prob()) { |
|
488 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
|
489 } |
|
490 /// \e |
|
491 ~LPGLPK() { |
|
492 lpx_delete_prob(lp); |
|
493 } |
|
494 |
|
495 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
|
496 |
|
497 /// \e |
|
498 void setMinimize() { |
|
499 lpx_set_obj_dir(lp, LPX_MIN); |
|
500 } |
|
501 /// \e |
|
502 void setMaximize() { |
|
503 lpx_set_obj_dir(lp, LPX_MAX); |
|
504 } |
|
505 |
|
506 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
|
507 |
|
508 protected: |
|
509 /// \e |
|
510 int _addCol() { |
|
511 int i=lpx_add_cols(lp, 1); |
|
512 _setColLowerBound(i, -INF); |
|
513 _setColUpperBound(i, INF); |
|
514 return i; |
|
515 } |
|
516 /// \e |
|
517 int _addRow() { |
|
518 int i=lpx_add_rows(lp, 1); |
|
519 return i; |
|
520 } |
|
521 /// \e |
|
522 virtual void _setRowCoeffs(int i, |
|
523 const std::vector<std::pair<int, double> >& coeffs) { |
|
524 int mem_length=1+colNum(); |
|
525 int* indices = new int[mem_length]; |
|
526 double* doubles = new double[mem_length]; |
|
527 int length=0; |
|
528 for (std::vector<std::pair<int, double> >:: |
|
529 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
|
530 ++length; |
|
531 indices[length]=it->first; |
|
532 doubles[length]=it->second; |
|
533 // std::cout << " " << indices[length] << " " |
|
534 // << doubles[length] << std::endl; |
|
535 } |
|
536 // std::cout << i << " " << length << std::endl; |
|
537 lpx_set_mat_row(lp, i, length, indices, doubles); |
|
538 delete [] indices; |
|
539 delete [] doubles; |
|
540 } |
|
541 /// \e |
|
542 virtual void _setColCoeffs(int i, |
|
543 const std::vector<std::pair<int, double> >& coeffs) { |
|
544 int mem_length=1+rowNum(); |
|
545 int* indices = new int[mem_length]; |
|
546 double* doubles = new double[mem_length]; |
|
547 int length=0; |
|
548 for (std::vector<std::pair<int, double> >:: |
|
549 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
|
550 ++length; |
|
551 indices[length]=it->first; |
|
552 doubles[length]=it->second; |
|
553 } |
|
554 lpx_set_mat_col(lp, i, length, indices, doubles); |
|
555 delete [] indices; |
|
556 delete [] doubles; |
|
557 } |
|
558 /// \e |
|
559 virtual void _eraseCol(int i) { |
|
560 int cols[2]; |
|
561 cols[1]=i; |
|
562 lpx_del_cols(lp, 1, cols); |
|
563 } |
|
564 virtual void _eraseRow(int i) { |
|
565 int rows[2]; |
|
566 rows[1]=i; |
|
567 lpx_del_rows(lp, 1, rows); |
|
568 } |
|
569 virtual void _setColLowerBound(int i, double lo) { |
|
570 if (lo==INF) { |
|
571 //FIXME error |
|
572 } |
|
573 int b=lpx_get_col_type(lp, i); |
|
574 double up=lpx_get_col_ub(lp, i); |
|
575 if (lo==-INF) { |
|
576 switch (b) { |
|
577 case LPX_FR: |
|
578 case LPX_LO: |
|
579 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
580 break; |
|
581 case LPX_UP: |
|
582 break; |
|
583 case LPX_DB: |
|
584 case LPX_FX: |
|
585 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
586 break; |
|
587 default: ; |
|
588 //FIXME error |
|
589 } |
|
590 } else { |
|
591 switch (b) { |
|
592 case LPX_FR: |
|
593 case LPX_LO: |
|
594 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
595 break; |
|
596 case LPX_UP: |
|
597 case LPX_DB: |
|
598 case LPX_FX: |
|
599 if (lo==up) |
|
600 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
601 else |
|
602 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
603 break; |
|
604 default: ; |
|
605 //FIXME error |
|
606 } |
|
607 } |
|
608 } |
|
609 virtual void _setColUpperBound(int i, double up) { |
|
610 if (up==-INF) { |
|
611 //FIXME error |
|
612 } |
|
613 int b=lpx_get_col_type(lp, i); |
|
614 double lo=lpx_get_col_lb(lp, i); |
|
615 if (up==INF) { |
|
616 switch (b) { |
|
617 case LPX_FR: |
|
618 case LPX_LO: |
|
619 break; |
|
620 case LPX_UP: |
|
621 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
622 break; |
|
623 case LPX_DB: |
|
624 case LPX_FX: |
|
625 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
626 break; |
|
627 default: ; |
|
628 //FIXME error |
|
629 } |
|
630 } else { |
|
631 switch (b) { |
|
632 case LPX_FR: |
|
633 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
634 case LPX_LO: |
|
635 if (lo==up) |
|
636 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
637 else |
|
638 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
639 break; |
|
640 case LPX_UP: |
|
641 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
642 break; |
|
643 case LPX_DB: |
|
644 case LPX_FX: |
|
645 if (lo==up) |
|
646 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
647 else |
|
648 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
649 break; |
|
650 default: ; |
|
651 //FIXME error |
|
652 } |
|
653 } |
|
654 } |
|
655 virtual double _getColLowerBound(int i) { |
|
656 int b=lpx_get_col_type(lp, i); |
|
657 switch (b) { |
|
658 case LPX_FR: |
|
659 return -INF; |
|
660 case LPX_LO: |
|
661 return lpx_get_col_lb(lp, i); |
|
662 case LPX_UP: |
|
663 return -INF; |
|
664 case LPX_DB: |
|
665 case LPX_FX: |
|
666 return lpx_get_col_lb(lp, i); |
|
667 default: ; |
|
668 //FIXME error |
|
669 return 0.0; |
|
670 } |
|
671 } |
|
672 virtual double _getColUpperBound(int i) { |
|
673 int b=lpx_get_col_type(lp, i); |
|
674 switch (b) { |
|
675 case LPX_FR: |
|
676 case LPX_LO: |
|
677 return INF; |
|
678 case LPX_UP: |
|
679 case LPX_DB: |
|
680 case LPX_FX: |
|
681 return lpx_get_col_ub(lp, i); |
|
682 default: ; |
|
683 //FIXME error |
|
684 return 0.0; |
|
685 } |
|
686 } |
|
687 virtual void _setColBounds(int i, Bound bound, |
|
688 double lo, double up) { |
|
689 switch (bound) { |
|
690 case FREE: |
|
691 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
692 break; |
|
693 case LOWER: |
|
694 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
695 break; |
|
696 case UPPER: |
|
697 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
698 break; |
|
699 case DOUBLE: |
|
700 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
701 break; |
|
702 case FIXED: |
|
703 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
704 break; |
|
705 } |
|
706 } |
|
707 virtual void _setRowBounds(int i, Bound bound, |
|
708 double lo, double up) { |
|
709 switch (bound) { |
|
710 case FREE: |
|
711 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
712 break; |
|
713 case LOWER: |
|
714 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
715 break; |
|
716 case UPPER: |
|
717 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
718 break; |
|
719 case DOUBLE: |
|
720 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
721 break; |
|
722 case FIXED: |
|
723 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
724 break; |
|
725 } |
|
726 } |
|
727 protected: |
|
728 /// \e |
|
729 virtual double _getObjCoef(int i) { |
|
730 return lpx_get_obj_coef(lp, i); |
|
731 } |
|
732 /// \e |
|
733 virtual void _setObjCoef(int i, double obj_coef) { |
|
734 lpx_set_obj_coef(lp, i, obj_coef); |
|
735 } |
|
736 public: |
|
737 /// \e |
|
738 void solveSimplex() { lpx_simplex(lp); } |
|
739 /// \e |
|
740 void solvePrimalSimplex() { lpx_simplex(lp); } |
|
741 /// \e |
|
742 void solveDualSimplex() { lpx_simplex(lp); } |
|
743 /// \e |
|
744 protected: |
|
745 virtual double _getPrimal(int i) { |
|
746 return lpx_get_col_prim(lp, i); |
|
747 } |
|
748 public: |
|
749 /// \e |
|
750 double getObjVal() { return lpx_get_obj_val(lp); } |
|
751 /// \e |
|
752 int rowNum() const { return lpx_get_num_rows(lp); } |
|
753 /// \e |
|
754 int colNum() const { return lpx_get_num_cols(lp); } |
|
755 /// \e |
|
756 int warmUp() { return lpx_warm_up(lp); } |
|
757 /// \e |
|
758 void printWarmUpStatus(int i) { |
|
759 switch (i) { |
|
760 case LPX_E_OK: cout << "LPX_E_OK" << endl; break; |
|
761 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; |
|
762 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; |
|
763 case LPX_E_SING: cout << "LPX_E_SING" << endl; break; |
|
764 } |
|
765 } |
|
766 /// \e |
|
767 int getPrimalStatus() { return lpx_get_prim_stat(lp); } |
|
768 /// \e |
|
769 void printPrimalStatus(int i) { |
|
770 switch (i) { |
|
771 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; |
|
772 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; |
|
773 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; |
|
774 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; |
|
775 } |
|
776 } |
|
777 /// \e |
|
778 int getDualStatus() { return lpx_get_dual_stat(lp); } |
|
779 /// \e |
|
780 void printDualStatus(int i) { |
|
781 switch (i) { |
|
782 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; |
|
783 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; |
|
784 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; |
|
785 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; |
|
786 } |
|
787 } |
|
788 /// Returns the status of the slack variable assigned to row \c row_it. |
|
789 int getRowStat(const RowIt& row_it) { |
|
790 return lpx_get_row_stat(lp, row_iter_map[row_it]); |
|
791 } |
|
792 /// \e |
|
793 void printRowStatus(int i) { |
|
794 switch (i) { |
|
795 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
796 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
797 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
798 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
799 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
800 } |
|
801 } |
|
802 /// Returns the status of the variable assigned to column \c col_it. |
|
803 int getColStat(const ColIt& col_it) { |
|
804 return lpx_get_col_stat(lp, col_iter_map[col_it]); |
|
805 } |
|
806 /// \e |
|
807 void printColStatus(int i) { |
|
808 switch (i) { |
|
809 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
810 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
811 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
812 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
813 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
814 } |
|
815 } |
|
816 }; |
|
817 |
|
818 /// @} |
|
819 |
|
820 } //namespace lemon |
|
821 |
|
822 #endif //LEMON_LP_SOLVER_WRAPPER_H |
|