|
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 not yet implemented |
|
168 } |
|
169 double _getCoeff(int col, int row) { |
|
170 /// FIXME not yet implemented |
|
171 return 0.0; |
|
172 } |
|
173 virtual void _setColLowerBound(int i, double lo) { |
|
174 if (lo==INF) { |
|
175 //FIXME error |
|
176 } |
|
177 int b=lpx_get_col_type(lp, i); |
|
178 double up=lpx_get_col_ub(lp, i); |
|
179 if (lo==-INF) { |
|
180 switch (b) { |
|
181 case LPX_FR: |
|
182 case LPX_LO: |
|
183 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
184 break; |
|
185 case LPX_UP: |
|
186 break; |
|
187 case LPX_DB: |
|
188 case LPX_FX: |
|
189 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
190 break; |
|
191 default: ; |
|
192 //FIXME error |
|
193 } |
|
194 } else { |
|
195 switch (b) { |
|
196 case LPX_FR: |
|
197 case LPX_LO: |
|
198 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
199 break; |
|
200 case LPX_UP: |
|
201 case LPX_DB: |
|
202 case LPX_FX: |
|
203 if (lo==up) |
|
204 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
205 else |
|
206 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
207 break; |
|
208 default: ; |
|
209 //FIXME error |
|
210 } |
|
211 } |
|
212 } |
|
213 virtual double _getColLowerBound(int i) { |
|
214 int b=lpx_get_col_type(lp, i); |
|
215 switch (b) { |
|
216 case LPX_FR: |
|
217 return -INF; |
|
218 case LPX_LO: |
|
219 return lpx_get_col_lb(lp, i); |
|
220 case LPX_UP: |
|
221 return -INF; |
|
222 case LPX_DB: |
|
223 case LPX_FX: |
|
224 return lpx_get_col_lb(lp, i); |
|
225 default: ; |
|
226 //FIXME error |
|
227 return 0.0; |
|
228 } |
|
229 } |
|
230 virtual void _setColUpperBound(int i, double up) { |
|
231 if (up==-INF) { |
|
232 //FIXME error |
|
233 } |
|
234 int b=lpx_get_col_type(lp, i); |
|
235 double lo=lpx_get_col_lb(lp, i); |
|
236 if (up==INF) { |
|
237 switch (b) { |
|
238 case LPX_FR: |
|
239 case LPX_LO: |
|
240 break; |
|
241 case LPX_UP: |
|
242 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
243 break; |
|
244 case LPX_DB: |
|
245 case LPX_FX: |
|
246 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
247 break; |
|
248 default: ; |
|
249 //FIXME error |
|
250 } |
|
251 } else { |
|
252 switch (b) { |
|
253 case LPX_FR: |
|
254 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
255 case LPX_LO: |
|
256 if (lo==up) |
|
257 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
258 else |
|
259 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
260 break; |
|
261 case LPX_UP: |
|
262 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
263 break; |
|
264 case LPX_DB: |
|
265 case LPX_FX: |
|
266 if (lo==up) |
|
267 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
268 else |
|
269 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
270 break; |
|
271 default: ; |
|
272 //FIXME error |
|
273 } |
|
274 } |
|
275 } |
|
276 virtual double _getColUpperBound(int i) { |
|
277 int b=lpx_get_col_type(lp, i); |
|
278 switch (b) { |
|
279 case LPX_FR: |
|
280 case LPX_LO: |
|
281 return INF; |
|
282 case LPX_UP: |
|
283 case LPX_DB: |
|
284 case LPX_FX: |
|
285 return lpx_get_col_ub(lp, i); |
|
286 default: ; |
|
287 //FIXME error |
|
288 return 0.0; |
|
289 } |
|
290 } |
|
291 virtual void _setRowLowerBound(int i, double lo) { |
|
292 if (lo==INF) { |
|
293 //FIXME error |
|
294 } |
|
295 int b=lpx_get_row_type(lp, i); |
|
296 double up=lpx_get_row_ub(lp, i); |
|
297 if (lo==-INF) { |
|
298 switch (b) { |
|
299 case LPX_FR: |
|
300 case LPX_LO: |
|
301 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
302 break; |
|
303 case LPX_UP: |
|
304 break; |
|
305 case LPX_DB: |
|
306 case LPX_FX: |
|
307 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
308 break; |
|
309 default: ; |
|
310 //FIXME error |
|
311 } |
|
312 } else { |
|
313 switch (b) { |
|
314 case LPX_FR: |
|
315 case LPX_LO: |
|
316 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
317 break; |
|
318 case LPX_UP: |
|
319 case LPX_DB: |
|
320 case LPX_FX: |
|
321 if (lo==up) |
|
322 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
323 else |
|
324 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
325 break; |
|
326 default: ; |
|
327 //FIXME error |
|
328 } |
|
329 } |
|
330 } |
|
331 virtual double _getRowLowerBound(int i) { |
|
332 int b=lpx_get_row_type(lp, i); |
|
333 switch (b) { |
|
334 case LPX_FR: |
|
335 return -INF; |
|
336 case LPX_LO: |
|
337 return lpx_get_row_lb(lp, i); |
|
338 case LPX_UP: |
|
339 return -INF; |
|
340 case LPX_DB: |
|
341 case LPX_FX: |
|
342 return lpx_get_row_lb(lp, i); |
|
343 default: ; |
|
344 //FIXME error |
|
345 return 0.0; |
|
346 } |
|
347 } |
|
348 virtual void _setRowUpperBound(int i, double up) { |
|
349 if (up==-INF) { |
|
350 //FIXME error |
|
351 } |
|
352 int b=lpx_get_row_type(lp, i); |
|
353 double lo=lpx_get_row_lb(lp, i); |
|
354 if (up==INF) { |
|
355 switch (b) { |
|
356 case LPX_FR: |
|
357 case LPX_LO: |
|
358 break; |
|
359 case LPX_UP: |
|
360 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
361 break; |
|
362 case LPX_DB: |
|
363 case LPX_FX: |
|
364 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
365 break; |
|
366 default: ; |
|
367 //FIXME error |
|
368 } |
|
369 } else { |
|
370 switch (b) { |
|
371 case LPX_FR: |
|
372 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
373 case LPX_LO: |
|
374 if (lo==up) |
|
375 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
376 else |
|
377 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
378 break; |
|
379 case LPX_UP: |
|
380 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
381 break; |
|
382 case LPX_DB: |
|
383 case LPX_FX: |
|
384 if (lo==up) |
|
385 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
386 else |
|
387 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
388 break; |
|
389 default: ; |
|
390 //FIXME error |
|
391 } |
|
392 } |
|
393 } |
|
394 virtual double _getRowUpperBound(int i) { |
|
395 int b=lpx_get_row_type(lp, i); |
|
396 switch (b) { |
|
397 case LPX_FR: |
|
398 case LPX_LO: |
|
399 return INF; |
|
400 case LPX_UP: |
|
401 case LPX_DB: |
|
402 case LPX_FX: |
|
403 return lpx_get_row_ub(lp, i); |
|
404 default: ; |
|
405 //FIXME error |
|
406 return 0.0; |
|
407 } |
|
408 } |
|
409 /// \e |
|
410 virtual double _getObjCoeff(int i) { |
|
411 return lpx_get_obj_coef(lp, i); |
|
412 } |
|
413 /// \e |
|
414 virtual void _setObjCoeff(int i, double obj_coef) { |
|
415 lpx_set_obj_coef(lp, i, obj_coef); |
|
416 } |
|
417 public: |
|
418 /// \e |
|
419 void solveSimplex() { lpx_simplex(lp); } |
|
420 /// \e |
|
421 void solvePrimalSimplex() { lpx_simplex(lp); } |
|
422 /// \e |
|
423 void solveDualSimplex() { lpx_simplex(lp); } |
|
424 protected: |
|
425 virtual double _getPrimal(int i) { |
|
426 return lpx_get_col_prim(lp, i); |
|
427 } |
|
428 public: |
|
429 /// \e |
|
430 double getObjVal() { return lpx_get_obj_val(lp); } |
|
431 /// \e |
|
432 int rowNum() const { return lpx_get_num_rows(lp); } |
|
433 /// \e |
|
434 int colNum() const { return lpx_get_num_cols(lp); } |
|
435 /// \e |
|
436 int warmUp() { return lpx_warm_up(lp); } |
|
437 /// \e |
|
438 void printWarmUpStatus(int i) { |
|
439 switch (i) { |
|
440 case LPX_E_OK: cout << "LPX_E_OK" << endl; break; |
|
441 case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; |
|
442 case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; |
|
443 case LPX_E_SING: cout << "LPX_E_SING" << endl; break; |
|
444 } |
|
445 } |
|
446 /// \e |
|
447 int getPrimalStatus() { return lpx_get_prim_stat(lp); } |
|
448 /// \e |
|
449 void printPrimalStatus(int i) { |
|
450 switch (i) { |
|
451 case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; |
|
452 case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; |
|
453 case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; |
|
454 case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; |
|
455 } |
|
456 } |
|
457 /// \e |
|
458 int getDualStatus() { return lpx_get_dual_stat(lp); } |
|
459 /// \e |
|
460 void printDualStatus(int i) { |
|
461 switch (i) { |
|
462 case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; |
|
463 case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; |
|
464 case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; |
|
465 case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; |
|
466 } |
|
467 } |
|
468 /// Returns the status of the slack variable assigned to row \c row. |
|
469 int getRowStat(const Row& row) { |
|
470 return lpx_get_row_stat(lp, row_iter_map[row]); |
|
471 } |
|
472 /// \e |
|
473 void printRowStatus(int i) { |
|
474 switch (i) { |
|
475 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
476 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
477 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
478 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
479 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
480 } |
|
481 } |
|
482 /// Returns the status of the variable assigned to column \c col. |
|
483 int getColStat(const Col& col) { |
|
484 return lpx_get_col_stat(lp, col_iter_map[col]); |
|
485 } |
|
486 /// \e |
|
487 void printColStatus(int i) { |
|
488 switch (i) { |
|
489 case LPX_BS: cout << "LPX_BS" << endl; break; |
|
490 case LPX_NL: cout << "LPX_NL" << endl; break; |
|
491 case LPX_NU: cout << "LPX_NU" << endl; break; |
|
492 case LPX_NF: cout << "LPX_NF" << endl; break; |
|
493 case LPX_NS: cout << "LPX_NS" << endl; break; |
|
494 } |
|
495 } |
|
496 |
|
497 // MIP |
|
498 /// \e |
|
499 void solveBandB() { lpx_integer(lp); } |
|
500 /// \e |
|
501 void setLP() { lpx_set_class(lp, LPX_LP); } |
|
502 /// \e |
|
503 void setMIP() { lpx_set_class(lp, LPX_MIP); } |
|
504 protected: |
|
505 /// \e |
|
506 void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); } |
|
507 /// \e |
|
508 void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); } |
|
509 /// \e |
|
510 double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); } |
|
511 }; |
|
512 |
|
513 /// @} |
|
514 |
|
515 } //namespace lemon |
|
516 |
|
517 #endif //LEMON_LP_SOLVER_GLPK_H |