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