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 <stdio> |
|
12 //#include <stdlib> |
|
13 extern "C" { |
|
14 #include "glpk.h" |
|
15 } |
|
16 |
|
17 #include <iostream> |
|
18 #include <vector> |
|
19 #include <string> |
|
20 #include <list> |
|
21 #include <memory> |
|
22 #include <utility> |
|
23 |
|
24 //#include <sage_graph.h> |
|
25 //#include <lemon/list_graph.h> |
|
26 //#include <lemon/graph_wrapper.h> |
|
27 #include <lemon/invalid.h> |
|
28 //#include <bfs_dfs.h> |
|
29 //#include <stp.h> |
|
30 //#include <lemon/max_flow.h> |
|
31 //#include <augmenting_flow.h> |
|
32 //#include <iter_map.h> |
|
33 |
|
34 using std::cout; |
|
35 using std::cin; |
|
36 using std::endl; |
|
37 |
|
38 namespace lemon { |
|
39 |
|
40 |
|
41 /// \addtogroup misc |
|
42 /// @{ |
|
43 |
|
44 /// \brief A partitioned vector with iterable classes. |
|
45 /// |
|
46 /// This class implements a container in which the data is stored in an |
|
47 /// stl vector, the range is partitioned into sets and each set is |
|
48 /// doubly linked in a list. |
|
49 /// That is, each class is iterable by lemon iterators, and any member of |
|
50 /// the vector can bo moved to an other class. |
|
51 template <typename T> |
|
52 class IterablePartition { |
|
53 protected: |
|
54 struct Node { |
|
55 T data; |
|
56 int prev; //invalid az -1 |
|
57 int next; |
|
58 }; |
|
59 std::vector<Node> nodes; |
|
60 struct Tip { |
|
61 int first; |
|
62 int last; |
|
63 }; |
|
64 std::vector<Tip> tips; |
|
65 public: |
|
66 /// The classes are indexed by integers from \c 0 to \c classNum()-1. |
|
67 int classNum() const { return tips.size(); } |
|
68 /// This lemon style iterator iterates through a class. |
|
69 class ClassIt; |
|
70 /// Constructor. The number of classes is to be given which is fixed |
|
71 /// over the life of the container. |
|
72 /// The partition classes are indexed from 0 to class_num-1. |
|
73 IterablePartition(int class_num) { |
|
74 for (int i=0; i<class_num; ++i) { |
|
75 Tip t; |
|
76 t.first=t.last=-1; |
|
77 tips.push_back(t); |
|
78 } |
|
79 } |
|
80 protected: |
|
81 void befuz(ClassIt it, int class_id) { |
|
82 if (tips[class_id].first==-1) { |
|
83 if (tips[class_id].last==-1) { |
|
84 nodes[it.i].prev=nodes[it.i].next=-1; |
|
85 tips[class_id].first=tips[class_id].last=it.i; |
|
86 } |
|
87 } else { |
|
88 nodes[it.i].prev=tips[class_id].last; |
|
89 nodes[it.i].next=-1; |
|
90 nodes[tips[class_id].last].next=it.i; |
|
91 tips[class_id].last=it.i; |
|
92 } |
|
93 } |
|
94 void kifuz(ClassIt it, int class_id) { |
|
95 if (tips[class_id].first==it.i) { |
|
96 if (tips[class_id].last==it.i) { |
|
97 tips[class_id].first=tips[class_id].last=-1; |
|
98 } else { |
|
99 tips[class_id].first=nodes[it.i].next; |
|
100 nodes[nodes[it.i].next].prev=-1; |
|
101 } |
|
102 } else { |
|
103 if (tips[class_id].last==it.i) { |
|
104 tips[class_id].last=nodes[it.i].prev; |
|
105 nodes[nodes[it.i].prev].next=-1; |
|
106 } else { |
|
107 nodes[nodes[it.i].next].prev=nodes[it.i].prev; |
|
108 nodes[nodes[it.i].prev].next=nodes[it.i].next; |
|
109 } |
|
110 } |
|
111 } |
|
112 public: |
|
113 /// A new element with data \c t is pushed into the vector and into class |
|
114 /// \c class_id. |
|
115 ClassIt push_back(const T& t, int class_id) { |
|
116 Node n; |
|
117 n.data=t; |
|
118 nodes.push_back(n); |
|
119 int i=nodes.size()-1; |
|
120 befuz(i, class_id); |
|
121 return i; |
|
122 } |
|
123 /// A member is moved to an other class. |
|
124 void set(ClassIt it, int old_class_id, int new_class_id) { |
|
125 kifuz(it.i, old_class_id); |
|
126 befuz(it.i, new_class_id); |
|
127 } |
|
128 /// Returns the data pointed by \c it. |
|
129 T& operator[](ClassIt it) { return nodes[it.i].data; } |
|
130 /// Returns the data pointed by \c it. |
|
131 const T& operator[](ClassIt it) const { return nodes[it.i].data; } |
|
132 ///. |
|
133 class ClassIt { |
|
134 friend class IterablePartition; |
|
135 protected: |
|
136 int i; |
|
137 public: |
|
138 /// Default constructor. |
|
139 ClassIt() { } |
|
140 /// This constructor constructs an iterator which points |
|
141 /// to the member of th container indexed by the integer _i. |
|
142 ClassIt(const int& _i) : i(_i) { } |
|
143 /// Invalid constructor. |
|
144 ClassIt(const Invalid&) : i(-1) { } |
|
145 }; |
|
146 /// First member of class \c class_id. |
|
147 ClassIt& first(ClassIt& it, int class_id) const { |
|
148 it.i=tips[class_id].first; |
|
149 return it; |
|
150 } |
|
151 /// Next member. |
|
152 ClassIt& next(ClassIt& it) const { |
|
153 it.i=nodes[it.i].next; |
|
154 return it; |
|
155 } |
|
156 /// True iff the iterator is valid. |
|
157 bool valid(const ClassIt& it) const { return it.i!=-1; } |
|
158 }; |
|
159 |
|
160 /// \brief Wrappers for LP solvers |
|
161 /// |
|
162 /// This class implements a lemon wrapper for glpk. |
|
163 /// Later other LP-solvers will be wrapped into lemon. |
|
164 /// The aim of this class is to give a general surface to different |
|
165 /// solvers, i.e. it makes possible to write algorithms using LP's, |
|
166 /// in which the solver can be changed to an other one easily. |
|
167 class LPSolverWrapper { |
|
168 public: |
|
169 |
|
170 // class Row { |
|
171 // protected: |
|
172 // int i; |
|
173 // public: |
|
174 // Row() { } |
|
175 // Row(const Invalid&) : i(0) { } |
|
176 // Row(const int& _i) : i(_i) { } |
|
177 // operator int() const { return i; } |
|
178 // }; |
|
179 // class RowIt : public Row { |
|
180 // public: |
|
181 // RowIt(const Row& row) : Row(row) { } |
|
182 // }; |
|
183 |
|
184 // class Col { |
|
185 // protected: |
|
186 // int i; |
|
187 // public: |
|
188 // Col() { } |
|
189 // Col(const Invalid&) : i(0) { } |
|
190 // Col(const int& _i) : i(_i) { } |
|
191 // operator int() const { return i; } |
|
192 // }; |
|
193 // class ColIt : public Col { |
|
194 // ColIt(const Col& col) : Col(col) { } |
|
195 // }; |
|
196 |
|
197 public: |
|
198 ///. |
|
199 LPX* lp; |
|
200 ///. |
|
201 typedef IterablePartition<int>::ClassIt RowIt; |
|
202 ///. |
|
203 IterablePartition<int> row_iter_map; |
|
204 ///. |
|
205 typedef IterablePartition<int>::ClassIt ColIt; |
|
206 ///. |
|
207 IterablePartition<int> col_iter_map; |
|
208 //std::vector<int> row_id_to_lp_row_id; |
|
209 //std::vector<int> col_id_to_lp_col_id; |
|
210 ///. |
|
211 const int VALID_ID; |
|
212 ///. |
|
213 const int INVALID_ID; |
|
214 |
|
215 public: |
|
216 ///. |
|
217 LPSolverWrapper() : lp(lpx_create_prob()), |
|
218 row_iter_map(2), |
|
219 col_iter_map(2), |
|
220 //row_id_to_lp_row_id(), col_id_to_lp_col_id(), |
|
221 VALID_ID(0), INVALID_ID(1) { |
|
222 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
|
223 } |
|
224 ///. |
|
225 ~LPSolverWrapper() { |
|
226 lpx_delete_prob(lp); |
|
227 } |
|
228 ///. |
|
229 void setMinimize() { |
|
230 lpx_set_obj_dir(lp, LPX_MIN); |
|
231 } |
|
232 ///. |
|
233 void setMaximize() { |
|
234 lpx_set_obj_dir(lp, LPX_MAX); |
|
235 } |
|
236 ///. |
|
237 ColIt addCol() { |
|
238 int i=lpx_add_cols(lp, 1); |
|
239 ColIt col_it; |
|
240 col_iter_map.first(col_it, INVALID_ID); |
|
241 if (col_iter_map.valid(col_it)) { //van hasznalhato hely |
|
242 col_iter_map.set(col_it, INVALID_ID, VALID_ID); |
|
243 col_iter_map[col_it]=i; |
|
244 //col_id_to_lp_col_id[col_iter_map[col_it]]=i; |
|
245 } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
|
246 //col_id_to_lp_col_id.push_back(i); |
|
247 //int j=col_id_to_lp_col_id.size()-1; |
|
248 col_it=col_iter_map.push_back(i, VALID_ID); |
|
249 } |
|
250 // edge_index_map.set(e, i); |
|
251 // lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0); |
|
252 // lpx_set_obj_coef(lp, i, cost[e]); |
|
253 return col_it; |
|
254 } |
|
255 ///. |
|
256 RowIt addRow() { |
|
257 int i=lpx_add_rows(lp, 1); |
|
258 RowIt row_it; |
|
259 row_iter_map.first(row_it, INVALID_ID); |
|
260 if (row_iter_map.valid(row_it)) { //van hasznalhato hely |
|
261 row_iter_map.set(row_it, INVALID_ID, VALID_ID); |
|
262 row_iter_map[row_it]=i; |
|
263 } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
|
264 row_it=row_iter_map.push_back(i, VALID_ID); |
|
265 } |
|
266 return row_it; |
|
267 } |
|
268 //pair<RowIt, double>-bol kell megadni egy std range-et |
|
269 ///. |
|
270 template <typename Begin, typename End> |
|
271 void setColCoeffs(const ColIt& col_it, |
|
272 Begin begin, End end) { |
|
273 int mem_length=1+lpx_get_num_rows(lp); |
|
274 int* indices = new int[mem_length]; |
|
275 double* doubles = new double[mem_length]; |
|
276 int length=0; |
|
277 for ( ; begin!=end; ++begin) { |
|
278 ++length; |
|
279 indices[length]=row_iter_map[begin->first]; |
|
280 doubles[length]=begin->second; |
|
281 } |
|
282 lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles); |
|
283 delete [] indices; |
|
284 delete [] doubles; |
|
285 } |
|
286 //pair<ColIt, double>-bol kell megadni egy std range-et |
|
287 ///. |
|
288 template <typename Begin, typename End> |
|
289 void setRowCoeffs(const RowIt& row_it, |
|
290 Begin begin, End end) { |
|
291 int mem_length=1+lpx_get_num_cols(lp); |
|
292 int* indices = new int[mem_length]; |
|
293 double* doubles = new double[mem_length]; |
|
294 int length=0; |
|
295 for ( ; begin!=end; ++begin) { |
|
296 ++length; |
|
297 indices[length]=col_iter_map[begin->first]; |
|
298 doubles[length]=begin->second; |
|
299 } |
|
300 lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles); |
|
301 delete [] indices; |
|
302 delete [] doubles; |
|
303 } |
|
304 ///. |
|
305 void eraseCol(const ColIt& col_it) { |
|
306 col_iter_map.set(col_it, VALID_ID, INVALID_ID); |
|
307 int cols[2]; |
|
308 cols[1]=col_iter_map[col_it]; |
|
309 lpx_del_cols(lp, 1, cols); |
|
310 col_iter_map[col_it]=0; //glpk specifikus |
|
311 ColIt it; |
|
312 for (col_iter_map.first(it, VALID_ID); |
|
313 col_iter_map.valid(it); col_iter_map.next(it)) { |
|
314 if (col_iter_map[it]>cols[1]) --col_iter_map[it]; |
|
315 } |
|
316 } |
|
317 ///. |
|
318 void eraseRow(const RowIt& row_it) { |
|
319 row_iter_map.set(row_it, VALID_ID, INVALID_ID); |
|
320 int rows[2]; |
|
321 rows[1]=row_iter_map[row_it]; |
|
322 lpx_del_rows(lp, 1, rows); |
|
323 row_iter_map[row_it]=0; //glpk specifikus |
|
324 RowIt it; |
|
325 for (row_iter_map.first(it, VALID_ID); |
|
326 row_iter_map.valid(it); row_iter_map.next(it)) { |
|
327 if (row_iter_map[it]>rows[1]) --row_iter_map[it]; |
|
328 } |
|
329 } |
|
330 ///. |
|
331 void setColBounds(const ColIt& col_it, int bound_type, |
|
332 double lo, double up) { |
|
333 lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up); |
|
334 } |
|
335 ///. |
|
336 double getObjCoef(const ColIt& col_it) { |
|
337 return lpx_get_obj_coef(lp, col_iter_map[col_it]); |
|
338 } |
|
339 ///. |
|
340 void setRowBounds(const RowIt& row_it, int bound_type, |
|
341 double lo, double up) { |
|
342 lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up); |
|
343 } |
|
344 ///. |
|
345 void setObjCoef(const ColIt& col_it, double obj_coef) { |
|
346 lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef); |
|
347 } |
|
348 ///. |
|
349 void solveSimplex() { lpx_simplex(lp); } |
|
350 ///. |
|
351 void solvePrimalSimplex() { lpx_simplex(lp); } |
|
352 ///. |
|
353 void solveDualSimplex() { lpx_simplex(lp); } |
|
354 ///. |
|
355 double getPrimal(const ColIt& col_it) { |
|
356 return lpx_get_col_prim(lp, col_iter_map[col_it]); |
|
357 } |
|
358 ///. |
|
359 double getObjVal() { return lpx_get_obj_val(lp); } |
|
360 ///. |
|
361 int rowNum() const { return lpx_get_num_rows(lp); } |
|
362 ///. |
|
363 int colNum() const { return lpx_get_num_cols(lp); } |
|
364 ///. |
|
365 int warmUp() { return lpx_warm_up(lp); } |
|
366 ///. |
|
367 void printWarmUpStatus(int i) { |
|
368 switch (i) { |
|
369 case LPX_E_OK: cout << "LPX_E_OK" << endl; break; |
|
370 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; |
|
371 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; |
|
372 case LPX_E_SING: cout << "LPX_E_SING" << endl; break; |
|
373 } |
|
374 } |
|
375 ///. |
|
376 int getPrimalStatus() { return lpx_get_prim_stat(lp); } |
|
377 ///. |
|
378 void printPrimalStatus(int i) { |
|
379 switch (i) { |
|
380 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; |
|
381 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; |
|
382 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; |
|
383 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; |
|
384 } |
|
385 } |
|
386 ///. |
|
387 int getDualStatus() { return lpx_get_dual_stat(lp); } |
|
388 ///. |
|
389 void printDualStatus(int i) { |
|
390 switch (i) { |
|
391 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; |
|
392 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; |
|
393 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; |
|
394 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; |
|
395 } |
|
396 } |
|
397 /// Returns the status of the slack variable assigned to row \c row_it. |
|
398 int getRowStat(const RowIt& row_it) { |
|
399 return lpx_get_row_stat(lp, row_iter_map[row_it]); |
|
400 } |
|
401 ///. |
|
402 void printRowStatus(int i) { |
|
403 switch (i) { |
|
404 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
405 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
406 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
407 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
408 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
409 } |
|
410 } |
|
411 /// Returns the status of the variable assigned to column \c col_it. |
|
412 int getColStat(const ColIt& col_it) { |
|
413 return lpx_get_col_stat(lp, col_iter_map[col_it]); |
|
414 } |
|
415 ///. |
|
416 void printColStatus(int i) { |
|
417 switch (i) { |
|
418 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
419 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
420 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
421 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
422 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
423 } |
|
424 } |
|
425 }; |
|
426 |
|
427 /// @} |
|
428 |
|
429 } //namespace lemon |
|
430 |
|
431 #endif //LEMON_LP_SOLVER_WRAPPER_H |
|