1 /* -*- C++ -*- |
|
2 * src/lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_LP_GLPK_CC |
|
18 #define LEMON_LP_GLPK_CC |
|
19 |
|
20 ///\file |
|
21 ///\brief Implementation of the LEMON-GLPK lp solver interface. |
|
22 |
|
23 #include <lemon/lp_glpk.h> |
|
24 |
|
25 namespace lemon { |
|
26 |
|
27 ///\e |
|
28 |
|
29 ///\bug Unimplemented! |
|
30 /// |
|
31 LpSolverBase &LpGlpk::_newLp() |
|
32 { |
|
33 LpSolverBase *tmp=0; |
|
34 return *tmp; |
|
35 } |
|
36 |
|
37 ///\e |
|
38 |
|
39 ///\bug Unimplemented! |
|
40 /// |
|
41 LpSolverBase &LpGlpk::_copyLp() |
|
42 { |
|
43 LpSolverBase *tmp=0; |
|
44 return *tmp; |
|
45 } |
|
46 |
|
47 LpGlpk::LpGlpk() : Parent(), |
|
48 lp(lpx_create_prob()) { |
|
49 ///\todo constrol function for this: |
|
50 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
|
51 messageLevel(0); |
|
52 } |
|
53 |
|
54 LpGlpk::~LpGlpk() { |
|
55 lpx_delete_prob(lp); |
|
56 } |
|
57 |
|
58 int LpGlpk::_addCol() { |
|
59 int i=lpx_add_cols(lp, 1); |
|
60 _setColLowerBound(i, -INF); |
|
61 _setColUpperBound(i, INF); |
|
62 return i; |
|
63 } |
|
64 |
|
65 int LpGlpk::_addRow() { |
|
66 int i=lpx_add_rows(lp, 1); |
|
67 return i; |
|
68 } |
|
69 |
|
70 |
|
71 void LpGlpk::_eraseCol(int i) { |
|
72 int cols[2]; |
|
73 cols[1]=i; |
|
74 lpx_del_cols(lp, 1, cols); |
|
75 } |
|
76 |
|
77 void LpGlpk::_eraseRow(int i) { |
|
78 int rows[2]; |
|
79 rows[1]=i; |
|
80 lpx_del_rows(lp, 1, rows); |
|
81 } |
|
82 |
|
83 void LpGlpk::_setRowCoeffs(int i, |
|
84 int length, |
|
85 const int * indices, |
|
86 const Value * values ) |
|
87 { |
|
88 lpx_set_mat_row(lp, i, length, |
|
89 const_cast<int * >(indices) , |
|
90 const_cast<Value * >(values)); |
|
91 } |
|
92 |
|
93 void LpGlpk::_setColCoeffs(int i, |
|
94 int length, |
|
95 const int * indices, |
|
96 const Value * values) |
|
97 { |
|
98 lpx_set_mat_col(lp, i, length, |
|
99 const_cast<int * >(indices), |
|
100 const_cast<Value * >(values)); |
|
101 } |
|
102 |
|
103 |
|
104 void LpGlpk::_setCoeff(int row, int col, Value value) |
|
105 { |
|
106 ///FIXME Of course this is not efficient at all, but GLPK knows not more. |
|
107 // First approach: get one row, apply changes and set it again |
|
108 //(one idea to improve this: maybe it is better to do this with 1 coloumn) |
|
109 |
|
110 int mem_length=2+lpx_get_num_cols(lp); |
|
111 int* indices = new int[mem_length]; |
|
112 Value* values = new Value[mem_length]; |
|
113 |
|
114 |
|
115 int length=lpx_get_mat_row(lp, row, indices, values); |
|
116 |
|
117 //The following code does not suppose that the elements of the array indices are sorted |
|
118 int i=1; |
|
119 bool found=false; |
|
120 while (i <= length && !found){ |
|
121 if (indices[i]==col){ |
|
122 found = true; |
|
123 values[i]=value; |
|
124 } |
|
125 ++i; |
|
126 } |
|
127 if (!found){ |
|
128 ++length; |
|
129 indices[length]=col; |
|
130 values[length]=value; |
|
131 } |
|
132 |
|
133 lpx_set_mat_row(lp, row, length, indices, values); |
|
134 delete [] indices; |
|
135 delete [] values; |
|
136 |
|
137 } |
|
138 |
|
139 void LpGlpk::_setColLowerBound(int i, Value lo) |
|
140 { |
|
141 if (lo==INF) { |
|
142 //FIXME error |
|
143 } |
|
144 int b=lpx_get_col_type(lp, i); |
|
145 double up=lpx_get_col_ub(lp, i); |
|
146 if (lo==-INF) { |
|
147 switch (b) { |
|
148 case LPX_FR: |
|
149 case LPX_LO: |
|
150 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
151 break; |
|
152 case LPX_UP: |
|
153 break; |
|
154 case LPX_DB: |
|
155 case LPX_FX: |
|
156 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
157 break; |
|
158 default: ; |
|
159 //FIXME error |
|
160 } |
|
161 } else { |
|
162 switch (b) { |
|
163 case LPX_FR: |
|
164 case LPX_LO: |
|
165 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
166 break; |
|
167 case LPX_UP: |
|
168 case LPX_DB: |
|
169 case LPX_FX: |
|
170 if (lo==up) |
|
171 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
172 else |
|
173 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
174 break; |
|
175 default: ; |
|
176 //FIXME error |
|
177 } |
|
178 } |
|
179 |
|
180 } |
|
181 |
|
182 void LpGlpk::_setColUpperBound(int i, Value up) |
|
183 { |
|
184 if (up==-INF) { |
|
185 //FIXME error |
|
186 } |
|
187 int b=lpx_get_col_type(lp, i); |
|
188 double lo=lpx_get_col_lb(lp, i); |
|
189 if (up==INF) { |
|
190 switch (b) { |
|
191 case LPX_FR: |
|
192 case LPX_LO: |
|
193 break; |
|
194 case LPX_UP: |
|
195 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
|
196 break; |
|
197 case LPX_DB: |
|
198 case LPX_FX: |
|
199 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
|
200 break; |
|
201 default: ; |
|
202 //FIXME error |
|
203 } |
|
204 } else { |
|
205 switch (b) { |
|
206 case LPX_FR: |
|
207 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
208 break; |
|
209 case LPX_UP: |
|
210 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
|
211 break; |
|
212 case LPX_LO: |
|
213 case LPX_DB: |
|
214 case LPX_FX: |
|
215 if (lo==up) |
|
216 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
|
217 else |
|
218 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
|
219 break; |
|
220 default: ; |
|
221 //FIXME error |
|
222 } |
|
223 } |
|
224 } |
|
225 |
|
226 // void LpGlpk::_setRowLowerBound(int i, Value lo) |
|
227 // { |
|
228 // if (lo==INF) { |
|
229 // //FIXME error |
|
230 // } |
|
231 // int b=lpx_get_row_type(lp, i); |
|
232 // double up=lpx_get_row_ub(lp, i); |
|
233 // if (lo==-INF) { |
|
234 // switch (b) { |
|
235 // case LPX_FR: |
|
236 // case LPX_LO: |
|
237 // lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
238 // break; |
|
239 // case LPX_UP: |
|
240 // break; |
|
241 // case LPX_DB: |
|
242 // case LPX_FX: |
|
243 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
244 // break; |
|
245 // default: ; |
|
246 // //FIXME error |
|
247 // } |
|
248 // } else { |
|
249 // switch (b) { |
|
250 // case LPX_FR: |
|
251 // case LPX_LO: |
|
252 // lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
253 // break; |
|
254 // case LPX_UP: |
|
255 // case LPX_DB: |
|
256 // case LPX_FX: |
|
257 // if (lo==up) |
|
258 // lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
259 // else |
|
260 // lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
261 // break; |
|
262 // default: ; |
|
263 // //FIXME error |
|
264 // } |
|
265 // } |
|
266 // } |
|
267 |
|
268 // void LpGlpk::_setRowUpperBound(int i, Value up) |
|
269 // { |
|
270 // if (up==-INF) { |
|
271 // //FIXME error |
|
272 // } |
|
273 // int b=lpx_get_row_type(lp, i); |
|
274 // double lo=lpx_get_row_lb(lp, i); |
|
275 // if (up==INF) { |
|
276 // switch (b) { |
|
277 // case LPX_FR: |
|
278 // case LPX_LO: |
|
279 // break; |
|
280 // case LPX_UP: |
|
281 // lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
282 // break; |
|
283 // case LPX_DB: |
|
284 // case LPX_FX: |
|
285 // lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
286 // break; |
|
287 // default: ; |
|
288 // //FIXME error |
|
289 // } |
|
290 // } else { |
|
291 // switch (b) { |
|
292 // case LPX_FR: |
|
293 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
294 // break; |
|
295 // case LPX_UP: |
|
296 // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
297 // break; |
|
298 // case LPX_LO: |
|
299 // case LPX_DB: |
|
300 // case LPX_FX: |
|
301 // if (lo==up) |
|
302 // lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
303 // else |
|
304 // lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
305 // break; |
|
306 // default: ; |
|
307 // //FIXME error |
|
308 // } |
|
309 // } |
|
310 // } |
|
311 |
|
312 void LpGlpk::_setRowBounds(int i, Value lb, Value ub) |
|
313 { |
|
314 //Bad parameter |
|
315 if (lb==INF || ub==-INF) { |
|
316 //FIXME error |
|
317 } |
|
318 |
|
319 if (lb == -INF){ |
|
320 if (ub == INF){ |
|
321 lpx_set_row_bnds(lp, i, LPX_FR, lb, ub); |
|
322 } |
|
323 else{ |
|
324 lpx_set_row_bnds(lp, i, LPX_UP, lb, ub); |
|
325 } |
|
326 } |
|
327 else{ |
|
328 if (ub==INF){ |
|
329 lpx_set_row_bnds(lp, i, LPX_LO, lb, ub); |
|
330 |
|
331 } |
|
332 else{ |
|
333 if (lb == ub){ |
|
334 lpx_set_row_bnds(lp, i, LPX_FX, lb, ub); |
|
335 } |
|
336 else{ |
|
337 lpx_set_row_bnds(lp, i, LPX_DB, lb, ub); |
|
338 } |
|
339 } |
|
340 } |
|
341 |
|
342 } |
|
343 |
|
344 void LpGlpk::_setObjCoeff(int i, Value obj_coef) |
|
345 { |
|
346 //i=0 means the constant term (shift) |
|
347 lpx_set_obj_coef(lp, i, obj_coef); |
|
348 } |
|
349 |
|
350 void LpGlpk::_clearObj() |
|
351 { |
|
352 for (int i=0;i<=lpx_get_num_cols(lp);++i){ |
|
353 lpx_set_obj_coef(lp, i, 0); |
|
354 } |
|
355 } |
|
356 // void LpGlpk::_setObj(int length, |
|
357 // int const * indices, |
|
358 // Value const * values ) |
|
359 // { |
|
360 // Value new_values[1+lpx_num_cols()]; |
|
361 // for (i=0;i<=lpx_num_cols();++i){ |
|
362 // new_values[i]=0; |
|
363 // } |
|
364 // for (i=1;i<=length;++i){ |
|
365 // new_values[indices[i]]=values[i]; |
|
366 // } |
|
367 |
|
368 // for (i=0;i<=lpx_num_cols();++i){ |
|
369 // lpx_set_obj_coef(lp, i, new_values[i]); |
|
370 // } |
|
371 // } |
|
372 |
|
373 LpGlpk::SolveExitStatus LpGlpk::_solve() |
|
374 { |
|
375 int i= lpx_simplex(lp); |
|
376 switch (i) { |
|
377 case LPX_E_OK: |
|
378 return SOLVED; |
|
379 break; |
|
380 default: |
|
381 return UNSOLVED; |
|
382 } |
|
383 } |
|
384 |
|
385 LpGlpk::Value LpGlpk::_getPrimal(int i) |
|
386 { |
|
387 return lpx_get_col_prim(lp,i); |
|
388 } |
|
389 |
|
390 LpGlpk::Value LpGlpk::_getPrimalValue() |
|
391 { |
|
392 return lpx_get_obj_val(lp); |
|
393 } |
|
394 |
|
395 |
|
396 LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() |
|
397 { |
|
398 int stat= lpx_get_status(lp); |
|
399 switch (stat) { |
|
400 case LPX_UNDEF://Undefined (no solve has been run yet) |
|
401 return UNDEFINED; |
|
402 break; |
|
403 case LPX_NOFEAS://There is no feasible solution (primal, I guess) |
|
404 case LPX_INFEAS://Infeasible |
|
405 return INFEASIBLE; |
|
406 break; |
|
407 case LPX_UNBND://Unbounded |
|
408 return INFINITE; |
|
409 break; |
|
410 case LPX_FEAS://Feasible |
|
411 return FEASIBLE; |
|
412 break; |
|
413 case LPX_OPT://Feasible |
|
414 return OPTIMAL; |
|
415 break; |
|
416 default: |
|
417 return UNDEFINED; //to avoid gcc warning |
|
418 //FIXME error |
|
419 } |
|
420 } |
|
421 |
|
422 |
|
423 void LpGlpk::_setMax() |
|
424 { |
|
425 lpx_set_obj_dir(lp, LPX_MAX); |
|
426 } |
|
427 |
|
428 void LpGlpk::_setMin() |
|
429 { |
|
430 lpx_set_obj_dir(lp, LPX_MIN); |
|
431 } |
|
432 |
|
433 |
|
434 void LpGlpk::messageLevel(int m) |
|
435 { |
|
436 lpx_set_int_parm(lp, LPX_K_MSGLEV, m); |
|
437 } |
|
438 |
|
439 void LpGlpk::presolver(bool b) |
|
440 { |
|
441 lpx_set_int_parm(lp, LPX_K_PRESOL, b); |
|
442 } |
|
443 |
|
444 |
|
445 } //END OF NAMESPACE LEMON |
|
446 |
|
447 #endif //LEMON_LP_GLPK_CC |
|