1 // -*- c++ -*- |
|
2 #ifndef LEMON_LP_SOLVER_GLPK_H |
|
3 #define LEMON_LP_SOLVER_GLPK_H |
|
4 |
|
5 ///\ingroup misc |
|
6 ///\file |
|
7 |
|
8 // #include <stdio.h> |
|
9 /* #include <stdlib.h> */ |
|
10 /* #include <iostream> */ |
|
11 /* #include <map> */ |
|
12 /* #include <limits> */ |
|
13 // #include <stdio> |
|
14 //#include <stdlib> |
|
15 extern "C" { |
|
16 #include "glpk.h" |
|
17 } |
|
18 |
|
19 /* #include <iostream> */ |
|
20 /* #include <vector> */ |
|
21 /* #include <string> */ |
|
22 /* #include <list> */ |
|
23 /* #include <memory> */ |
|
24 /* #include <utility> */ |
|
25 |
|
26 //#include <lemon/invalid.h> |
|
27 //#include <expression.h> |
|
28 #include <lp_solver_base.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 template <typename Value> |
|
42 const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity(); |
|
43 |
|
44 |
|
45 /// \brief Wrapper for GLPK solver |
|
46 /// |
|
47 /// This class implements a lemon wrapper for GLPK. |
|
48 class LpGlpk : public LpSolverBase<double> { |
|
49 public: |
|
50 typedef LpSolverBase<double> Parent; |
|
51 |
|
52 public: |
|
53 /// \e |
|
54 LPX* lp; |
|
55 |
|
56 public: |
|
57 /// \e |
|
58 LpGlpk() : Parent(), |
|
59 lp(lpx_create_prob()) { |
|
60 int_row_map.push_back(Row()); |
|
61 int_col_map.push_back(Col()); |
|
62 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
|
63 } |
|
64 /// \e |
|
65 ~LpGlpk() { |
|
66 lpx_delete_prob(lp); |
|
67 } |
|
68 |
|
69 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
|
70 |
|
71 /// \e |
|
72 void setMinimize() { |
|
73 lpx_set_obj_dir(lp, LPX_MIN); |
|
74 } |
|
75 /// \e |
|
76 void setMaximize() { |
|
77 lpx_set_obj_dir(lp, LPX_MAX); |
|
78 } |
|
79 |
|
80 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
|
81 |
|
82 protected: |
|
83 /// \e |
|
84 int _addCol() { |
|
85 int i=lpx_add_cols(lp, 1); |
|
86 _setColLowerBound(i, -INF); |
|
87 _setColUpperBound(i, INF); |
|
88 return i; |
|
89 } |
|
90 /// \e |
|
91 int _addRow() { |
|
92 int i=lpx_add_rows(lp, 1); |
|
93 return i; |
|
94 } |
|
95 /// \e |
|
96 virtual void _setRowCoeffs(int i, |
|
97 const std::vector<std::pair<int, double> >& coeffs) { |
|
98 int mem_length=1+colNum(); |
|
99 int* indices = new int[mem_length]; |
|
100 double* doubles = new double[mem_length]; |
|
101 int length=0; |
|
102 for (std::vector<std::pair<int, double> >:: |
|
103 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
|
104 ++length; |
|
105 indices[length]=it->first; |
|
106 doubles[length]=it->second; |
|
107 } |
|
108 lpx_set_mat_row(lp, i, length, indices, doubles); |
|
109 delete [] indices; |
|
110 delete [] doubles; |
|
111 } |
|
112 /// \e |
|
113 virtual void _getRowCoeffs(int i, |
|
114 std::vector<std::pair<int, double> >& coeffs) { |
|
115 int mem_length=1+colNum(); |
|
116 int* indices = new int[mem_length]; |
|
117 double* doubles = new double[mem_length]; |
|
118 int length=lpx_get_mat_row(lp, i, indices, doubles); |
|
119 for (int i=1; i<=length; ++i) { |
|
120 coeffs.push_back(std::make_pair(indices[i], doubles[i])); |
|
121 } |
|
122 delete [] indices; |
|
123 delete [] doubles; |
|
124 } |
|
125 /// \e |
|
126 virtual void _setColCoeffs(int i, |
|
127 const std::vector<std::pair<int, double> >& coeffs) { |
|
128 int mem_length=1+rowNum(); |
|
129 int* indices = new int[mem_length]; |
|
130 double* doubles = new double[mem_length]; |
|
131 int length=0; |
|
132 for (std::vector<std::pair<int, double> >:: |
|
133 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
|
134 ++length; |
|
135 indices[length]=it->first; |
|
136 doubles[length]=it->second; |
|
137 } |
|
138 lpx_set_mat_col(lp, i, length, indices, doubles); |
|
139 delete [] indices; |
|
140 delete [] doubles; |
|
141 } |
|
142 /// \e |
|
143 virtual void _getColCoeffs(int i, |
|
144 std::vector<std::pair<int, double> >& coeffs) { |
|
145 int mem_length=1+rowNum(); |
|
146 int* indices = new int[mem_length]; |
|
147 double* doubles = new double[mem_length]; |
|
148 int length=lpx_get_mat_col(lp, i, indices, doubles); |
|
149 for (int i=1; i<=length; ++i) { |
|
150 coeffs.push_back(std::make_pair(indices[i], doubles[i])); |
|
151 } |
|
152 delete [] indices; |
|
153 delete [] doubles; |
|
154 } |
|
155 /// \e |
|
156 virtual void _eraseCol(int i) { |
|
157 int cols[2]; |
|
158 cols[1]=i; |
|
159 lpx_del_cols(lp, 1, cols); |
|
160 } |
|
161 virtual void _eraseRow(int i) { |
|
162 int rows[2]; |
|
163 rows[1]=i; |
|
164 lpx_del_rows(lp, 1, rows); |
|
165 } |
|
166 void _setCoeff(int col, int row, double value) { |
|
167 ///FIXME Of course this is not efficient at all, but GLPK knows not more. |
|
168 int change_this; |
|
169 bool get_set_row; |
|
170 //The only thing we can do is optimize on whether working with a row |
|
171 //or a coloumn |
|
172 int row_num = rowNum(); |
|
173 int col_num = colNum(); |
|
174 if (col_num<row_num){ |
|
175 //There are more rows than coloumns |
|
176 get_set_row=true; |
|
177 int mem_length=1+row_num; |
|
178 int* indices = new int[mem_length]; |
|
179 double* doubles = new double[mem_length]; |
|
180 int length=lpx_get_mat_col(lp, i, indices, doubles); |
|
181 }else{ |
|
182 get_set_row=false; |
|
183 int mem_length=1+col_num; |
|
184 int* indices = new int[mem_length]; |
|
185 double* doubles = new double[mem_length]; |
|
186 int length=lpx_get_mat_row(lp, i, indices, doubles); |
|
187 } |
|
188 //Itten |
|
189 int* indices = new int[mem_length]; |
|
190 double* doubles = new double[mem_length]; |
|
191 int length=lpx_get_mat_col(lp, i, indices, doubles); |
|
192 |
|
193 delete [] indices; |
|
194 delete [] doubles; |
|
195 |
|
196 } |
|
197 double _getCoeff(int col, int row) { |
|
198 /// FIXME not yet implemented |
|
199 return 0.0; |
|
200 } |
|
201 virtual void _setColLowerBound(int i, double lo) { |
|
202 if (lo==INF) { |
|
203 //FIXME error |
|
204 } |
|
205 int b=lpx_get_col_type(lp, i); |
|
206 double up=lpx_get_col_ub(lp, i); |
|
207 if (lo==-INF) { |
|
208 switch (b) { |
|
209 case LPX_FR: |
|
210 case LPX_LO: |
|
211 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
212 break; |
|
213 case LPX_UP: |
|
214 break; |
|
215 case LPX_DB: |
|
216 case LPX_FX: |
|
217 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
218 break; |
|
219 default: ; |
|
220 //FIXME error |
|
221 } |
|
222 } else { |
|
223 switch (b) { |
|
224 case LPX_FR: |
|
225 case LPX_LO: |
|
226 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
227 break; |
|
228 case LPX_UP: |
|
229 case LPX_DB: |
|
230 case LPX_FX: |
|
231 if (lo==up) |
|
232 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
233 else |
|
234 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
235 break; |
|
236 default: ; |
|
237 //FIXME error |
|
238 } |
|
239 } |
|
240 } |
|
241 virtual double _getColLowerBound(int i) { |
|
242 int b=lpx_get_col_type(lp, i); |
|
243 switch (b) { |
|
244 case LPX_FR: |
|
245 return -INF; |
|
246 case LPX_LO: |
|
247 return lpx_get_col_lb(lp, i); |
|
248 case LPX_UP: |
|
249 return -INF; |
|
250 case LPX_DB: |
|
251 case LPX_FX: |
|
252 return lpx_get_col_lb(lp, i); |
|
253 default: ; |
|
254 //FIXME error |
|
255 return 0.0; |
|
256 } |
|
257 } |
|
258 virtual void _setColUpperBound(int i, double up) { |
|
259 if (up==-INF) { |
|
260 //FIXME error |
|
261 } |
|
262 int b=lpx_get_col_type(lp, i); |
|
263 double lo=lpx_get_col_lb(lp, i); |
|
264 if (up==INF) { |
|
265 switch (b) { |
|
266 case LPX_FR: |
|
267 case LPX_LO: |
|
268 break; |
|
269 case LPX_UP: |
|
270 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
271 break; |
|
272 case LPX_DB: |
|
273 case LPX_FX: |
|
274 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
275 break; |
|
276 default: ; |
|
277 //FIXME error |
|
278 } |
|
279 } else { |
|
280 switch (b) { |
|
281 case LPX_FR: |
|
282 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
283 case LPX_LO: |
|
284 if (lo==up) |
|
285 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
286 else |
|
287 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
288 break; |
|
289 case LPX_UP: |
|
290 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
291 break; |
|
292 case LPX_DB: |
|
293 case LPX_FX: |
|
294 if (lo==up) |
|
295 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
296 else |
|
297 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
298 break; |
|
299 default: ; |
|
300 //FIXME error |
|
301 } |
|
302 } |
|
303 } |
|
304 virtual double _getColUpperBound(int i) { |
|
305 int b=lpx_get_col_type(lp, i); |
|
306 switch (b) { |
|
307 case LPX_FR: |
|
308 case LPX_LO: |
|
309 return INF; |
|
310 case LPX_UP: |
|
311 case LPX_DB: |
|
312 case LPX_FX: |
|
313 return lpx_get_col_ub(lp, i); |
|
314 default: ; |
|
315 //FIXME error |
|
316 return 0.0; |
|
317 } |
|
318 } |
|
319 virtual void _setRowLowerBound(int i, double lo) { |
|
320 if (lo==INF) { |
|
321 //FIXME error |
|
322 } |
|
323 int b=lpx_get_row_type(lp, i); |
|
324 double up=lpx_get_row_ub(lp, i); |
|
325 if (lo==-INF) { |
|
326 switch (b) { |
|
327 case LPX_FR: |
|
328 case LPX_LO: |
|
329 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
330 break; |
|
331 case LPX_UP: |
|
332 break; |
|
333 case LPX_DB: |
|
334 case LPX_FX: |
|
335 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
336 break; |
|
337 default: ; |
|
338 //FIXME error |
|
339 } |
|
340 } else { |
|
341 switch (b) { |
|
342 case LPX_FR: |
|
343 case LPX_LO: |
|
344 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
345 break; |
|
346 case LPX_UP: |
|
347 case LPX_DB: |
|
348 case LPX_FX: |
|
349 if (lo==up) |
|
350 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
351 else |
|
352 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
353 break; |
|
354 default: ; |
|
355 //FIXME error |
|
356 } |
|
357 } |
|
358 } |
|
359 virtual double _getRowLowerBound(int i) { |
|
360 int b=lpx_get_row_type(lp, i); |
|
361 switch (b) { |
|
362 case LPX_FR: |
|
363 return -INF; |
|
364 case LPX_LO: |
|
365 return lpx_get_row_lb(lp, i); |
|
366 case LPX_UP: |
|
367 return -INF; |
|
368 case LPX_DB: |
|
369 case LPX_FX: |
|
370 return lpx_get_row_lb(lp, i); |
|
371 default: ; |
|
372 //FIXME error |
|
373 return 0.0; |
|
374 } |
|
375 } |
|
376 virtual void _setRowUpperBound(int i, double up) { |
|
377 if (up==-INF) { |
|
378 //FIXME error |
|
379 } |
|
380 int b=lpx_get_row_type(lp, i); |
|
381 double lo=lpx_get_row_lb(lp, i); |
|
382 if (up==INF) { |
|
383 switch (b) { |
|
384 case LPX_FR: |
|
385 case LPX_LO: |
|
386 break; |
|
387 case LPX_UP: |
|
388 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
389 break; |
|
390 case LPX_DB: |
|
391 case LPX_FX: |
|
392 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
393 break; |
|
394 default: ; |
|
395 //FIXME error |
|
396 } |
|
397 } else { |
|
398 switch (b) { |
|
399 case LPX_FR: |
|
400 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
401 case LPX_LO: |
|
402 if (lo==up) |
|
403 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
404 else |
|
405 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
406 break; |
|
407 case LPX_UP: |
|
408 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
409 break; |
|
410 case LPX_DB: |
|
411 case LPX_FX: |
|
412 if (lo==up) |
|
413 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
414 else |
|
415 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
416 break; |
|
417 default: ; |
|
418 //FIXME error |
|
419 } |
|
420 } |
|
421 } |
|
422 virtual double _getRowUpperBound(int i) { |
|
423 int b=lpx_get_row_type(lp, i); |
|
424 switch (b) { |
|
425 case LPX_FR: |
|
426 case LPX_LO: |
|
427 return INF; |
|
428 case LPX_UP: |
|
429 case LPX_DB: |
|
430 case LPX_FX: |
|
431 return lpx_get_row_ub(lp, i); |
|
432 default: ; |
|
433 //FIXME error |
|
434 return 0.0; |
|
435 } |
|
436 } |
|
437 /// \e |
|
438 virtual double _getObjCoeff(int i) { |
|
439 return lpx_get_obj_coef(lp, i); |
|
440 } |
|
441 /// \e |
|
442 virtual void _setObjCoeff(int i, double obj_coef) { |
|
443 lpx_set_obj_coef(lp, i, obj_coef); |
|
444 } |
|
445 public: |
|
446 /// \e |
|
447 void solveSimplex() { lpx_simplex(lp); } |
|
448 /// \e |
|
449 void solvePrimalSimplex() { lpx_simplex(lp); } |
|
450 /// \e |
|
451 void solveDualSimplex() { lpx_simplex(lp); } |
|
452 protected: |
|
453 virtual double _getPrimal(int i) { |
|
454 return lpx_get_col_prim(lp, i); |
|
455 } |
|
456 public: |
|
457 /// \e |
|
458 double getObjVal() { return lpx_get_obj_val(lp); } |
|
459 /// \e |
|
460 int rowNum() const { return lpx_get_num_rows(lp); } |
|
461 /// \e |
|
462 int colNum() const { return lpx_get_num_cols(lp); } |
|
463 /// \e |
|
464 int warmUp() { return lpx_warm_up(lp); } |
|
465 /// \e |
|
466 void printWarmUpStatus(int i) { |
|
467 switch (i) { |
|
468 case LPX_E_OK: cout << "LPX_E_OK" << endl; break; |
|
469 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; |
|
470 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; |
|
471 case LPX_E_SING: cout << "LPX_E_SING" << endl; break; |
|
472 } |
|
473 } |
|
474 /// \e |
|
475 int getPrimalStatus() { return lpx_get_prim_stat(lp); } |
|
476 /// \e |
|
477 void printPrimalStatus(int i) { |
|
478 switch (i) { |
|
479 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; |
|
480 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; |
|
481 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; |
|
482 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; |
|
483 } |
|
484 } |
|
485 /// \e |
|
486 int getDualStatus() { return lpx_get_dual_stat(lp); } |
|
487 /// \e |
|
488 void printDualStatus(int i) { |
|
489 switch (i) { |
|
490 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; |
|
491 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; |
|
492 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; |
|
493 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; |
|
494 } |
|
495 } |
|
496 /// Returns the status of the slack variable assigned to row \c row. |
|
497 int getRowStat(const Row& row) { |
|
498 return lpx_get_row_stat(lp, row_iter_map[row]); |
|
499 } |
|
500 /// \e |
|
501 void printRowStatus(int i) { |
|
502 switch (i) { |
|
503 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
504 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
505 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
506 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
507 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
508 } |
|
509 } |
|
510 /// Returns the status of the variable assigned to column \c col. |
|
511 int getColStat(const Col& col) { |
|
512 return lpx_get_col_stat(lp, col_iter_map[col]); |
|
513 } |
|
514 /// \e |
|
515 void printColStatus(int i) { |
|
516 switch (i) { |
|
517 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
518 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
519 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
520 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
521 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
522 } |
|
523 } |
|
524 |
|
525 // MIP |
|
526 /// \e |
|
527 void solveBandB() { lpx_integer(lp); } |
|
528 /// \e |
|
529 void setLP() { lpx_set_class(lp, LPX_LP); } |
|
530 /// \e |
|
531 void setMIP() { lpx_set_class(lp, LPX_MIP); } |
|
532 protected: |
|
533 /// \e |
|
534 void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); } |
|
535 /// \e |
|
536 void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); } |
|
537 /// \e |
|
538 double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); } |
|
539 }; |
|
540 |
|
541 /// @} |
|
542 |
|
543 } //namespace lemon |
|
544 |
|
545 #endif //LEMON_LP_SOLVER_GLPK_H |
|