182 LPSolverBase() : row_iter_map(2), |
181 LPSolverBase() : row_iter_map(2), |
183 col_iter_map(2), |
182 col_iter_map(2), |
184 VALID_CLASS(0), INVALID_CLASS(1) { } |
183 VALID_CLASS(0), INVALID_CLASS(1) { } |
185 /// \e |
184 /// \e |
186 virtual ~LPSolverBase() { } |
185 virtual ~LPSolverBase() { } |
|
186 |
|
187 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
|
188 |
|
189 public: |
187 /// \e |
190 /// \e |
188 virtual void setMinimize() = 0; |
191 virtual void setMinimize() = 0; |
189 /// \e |
192 /// \e |
190 virtual void setMaximize() = 0; |
193 virtual void setMaximize() = 0; |
|
194 |
|
195 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
|
196 |
191 protected: |
197 protected: |
192 /// \e |
198 /// \e |
193 virtual int _addRow() = 0; |
199 virtual int _addRow() = 0; |
194 /// \e |
200 /// \e |
195 virtual int _addCol() = 0; |
201 virtual int _addCol() = 0; |
|
202 /// \e |
|
203 virtual void _setRowCoeffs(int i, |
|
204 std::vector<std::pair<int, double> > coeffs) = 0; |
|
205 /// \e |
|
206 virtual void _setColCoeffs(int i, |
|
207 std::vector<std::pair<int, double> > coeffs) = 0; |
|
208 /// \e |
|
209 virtual void _eraseCol(int i) = 0; |
|
210 /// \e |
|
211 virtual void _eraseRow(int i) = 0; |
|
212 public: |
|
213 /// \e |
|
214 enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED }; |
|
215 protected: |
|
216 /// \e |
|
217 virtual void _setColBounds(int i, Bound bound, |
|
218 _Value lo, _Value up) = 0; |
|
219 /// \e |
|
220 virtual void _setRowBounds(int i, Bound bound, |
|
221 _Value lo, _Value up) = 0; |
|
222 /// \e |
|
223 virtual void _setObjCoef(int i, _Value obj_coef) = 0; |
|
224 /// \e |
|
225 virtual _Value _getObjCoef(int i) = 0; |
|
226 |
|
227 //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS |
|
228 |
|
229 protected: |
|
230 virtual _Value _getPrimal(int i) = 0; |
|
231 |
|
232 //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS |
|
233 |
196 public: |
234 public: |
197 /// \e |
235 /// \e |
198 RowIt addRow() { |
236 RowIt addRow() { |
199 int i=_addRow(); |
237 int i=_addRow(); |
200 RowIt row_it; |
238 RowIt row_it; |
219 col_it=col_iter_map.push_back(i, VALID_CLASS); |
257 col_it=col_iter_map.push_back(i, VALID_CLASS); |
220 } |
258 } |
221 return col_it; |
259 return col_it; |
222 } |
260 } |
223 /// \e |
261 /// \e |
224 virtual void setRowCoeffs(int i, |
|
225 std::vector<std::pair<int, double> > coeffs) = 0; |
|
226 /// \e |
|
227 virtual void setColCoeffs(int i, |
|
228 std::vector<std::pair<int, double> > coeffs) = 0; |
|
229 /// \e |
|
230 template <typename Begin, typename End> |
262 template <typename Begin, typename End> |
231 void setRowCoeffs(RowIt row_it, Begin begin, End end) { |
263 void setRowCoeffs(RowIt row_it, Begin begin, End end) { |
232 std::vector<std::pair<int, double> > coeffs; |
264 std::vector<std::pair<int, double> > coeffs; |
233 for ( ; begin!=end; ++begin) { |
265 for ( ; begin!=end; ++begin) { |
234 coeffs.push_back(std:: |
266 coeffs.push_back(std:: |
235 make_pair(col_iter_map[begin->first], begin->second)); |
267 make_pair(col_iter_map[begin->first], begin->second)); |
236 } |
268 } |
237 setRowCoeffs(row_iter_map[row_it], coeffs); |
269 _setRowCoeffs(row_iter_map[row_it], coeffs); |
238 } |
270 } |
239 /// \e |
271 /// \e |
240 template <typename Begin, typename End> |
272 template <typename Begin, typename End> |
241 void setColCoeffs(ColIt col_it, Begin begin, End end) { |
273 void setColCoeffs(ColIt col_it, Begin begin, End end) { |
242 std::vector<std::pair<int, double> > coeffs; |
274 std::vector<std::pair<int, double> > coeffs; |
243 for ( ; begin!=end; ++begin) { |
275 for ( ; begin!=end; ++begin) { |
244 coeffs.push_back(std:: |
276 coeffs.push_back(std:: |
245 make_pair(row_iter_map[begin->first], begin->second)); |
277 make_pair(row_iter_map[begin->first], begin->second)); |
246 } |
278 } |
247 setColCoeffs(col_iter_map[col_it], coeffs); |
279 _setColCoeffs(col_iter_map[col_it], coeffs); |
248 } |
280 } |
249 /// temporally, glpk style indexing |
|
250 //virtual void setRowCoeffs(RowIt row_it, int num, |
|
251 // int* indices, _Value* doubles) = 0; |
|
252 //pair<RowIt, _Value>-bol kell megadni egy std range-et |
|
253 /// \e |
|
254 // virtual void seColCoeffs(int i, |
|
255 // std::vector<std::pair<int, double> > coeffs) = 0; |
|
256 /// \e |
|
257 // template <typename Begin, typename End> |
|
258 // void setRowCoeffs(RowIt row_it, Begin begin, End end) { |
|
259 // int mem_length=1+colNum(); |
|
260 // int* indices = new int[mem_length]; |
|
261 // _Value* doubles = new _Value[mem_length]; |
|
262 // int length=0; |
|
263 // for ( ; begin!=end; ++begin) { |
|
264 // ++length; |
|
265 // indices[length]=col_iter_map[begin->first]; |
|
266 // doubles[length]=begin->second; |
|
267 // } |
|
268 // setRowCoeffs(row_it, length, indices, doubles); |
|
269 // delete [] indices; |
|
270 // delete [] doubles; |
|
271 // } |
|
272 /// temporally, glpk style indexing |
|
273 //virtual void setColCoeffs(ColIt col_it, int num, |
|
274 // int* indices, _Value* doubles) = 0; |
|
275 //pair<ColIt, _Value>-bol kell megadni egy std range-et |
|
276 /// \e |
|
277 // template <typename Begin, typename End> |
|
278 // void setColCoeffs(ColIt col_it, Begin begin, End end) { |
|
279 // int mem_length=1+rowNum(); |
|
280 // int* indices = new int[mem_length]; |
|
281 // _Value* doubles = new _Value[mem_length]; |
|
282 // int length=0; |
|
283 // for ( ; begin!=end; ++begin) { |
|
284 // ++length; |
|
285 // indices[length]=row_iter_map[begin->first]; |
|
286 // doubles[length]=begin->second; |
|
287 // } |
|
288 // setColCoeffs(col_it, length, indices, doubles); |
|
289 // delete [] indices; |
|
290 // delete [] doubles; |
|
291 // } |
|
292 protected: |
|
293 /// \e |
|
294 virtual void _eraseCol(int i) = 0; |
|
295 /// \e |
|
296 virtual void _eraseRow(int i) = 0; |
|
297 public: |
|
298 /// \e |
281 /// \e |
299 void eraseCol(const ColIt& col_it) { |
282 void eraseCol(const ColIt& col_it) { |
300 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS); |
283 col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS); |
301 int cols[2]; |
284 int cols[2]; |
302 cols[1]=col_iter_map[col_it]; |
285 cols[1]=col_iter_map[col_it]; |
320 row_iter_map.valid(it); row_iter_map.next(it)) { |
303 row_iter_map.valid(it); row_iter_map.next(it)) { |
321 if (row_iter_map[it]>rows[1]) --row_iter_map[it]; |
304 if (row_iter_map[it]>rows[1]) --row_iter_map[it]; |
322 } |
305 } |
323 } |
306 } |
324 /// \e |
307 /// \e |
325 virtual void setColBounds(const ColIt& col_it, int bound_type, |
308 void setColBounds(const ColIt& col_it, Bound bound, |
326 _Value lo, _Value up) =0; |
309 _Value lo, _Value up) { |
327 /// \e |
310 _setColBounds(col_iter_map[col_it], bound, lo, up); |
328 virtual _Value getObjCoef(const ColIt& col_it) = 0; |
311 } |
329 /// \e |
312 /// \e |
330 virtual void setRowBounds(const RowIt& row_it, int bound_type, |
313 void setRowBounds(const RowIt& row_it, Bound bound, |
331 _Value lo, _Value up) = 0; |
314 _Value lo, _Value up) { |
332 /// \e |
315 _setRowBounds(row_iter_map[row_it], bound, lo, up); |
333 virtual void setObjCoef(const ColIt& col_it, _Value obj_coef) = 0; |
316 } |
|
317 /// \e |
|
318 void setObjCoef(const ColIt& col_it, _Value obj_coef) { |
|
319 _setObjCoef(col_iter_map[col_it], obj_coef); |
|
320 } |
|
321 /// \e |
|
322 _Value getObjCoef(const ColIt& col_it) { |
|
323 return _getObjCoef(col_iter_map[col_it]); |
|
324 } |
|
325 |
|
326 //SOLVER FUNCTIONS |
|
327 |
334 /// \e |
328 /// \e |
335 virtual void solveSimplex() = 0; |
329 virtual void solveSimplex() = 0; |
336 /// \e |
330 /// \e |
337 virtual void solvePrimalSimplex() = 0; |
331 virtual void solvePrimalSimplex() = 0; |
338 /// \e |
332 /// \e |
339 virtual void solveDualSimplex() = 0; |
333 virtual void solveDualSimplex() = 0; |
340 /// \e |
334 /// \e |
341 virtual _Value getPrimal(const ColIt& col_it) = 0; |
335 |
|
336 //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS |
|
337 |
|
338 public: |
|
339 _Value getPrimal(const ColIt& col_it) { |
|
340 return _getPrimal(col_iter_map[col_it]); |
|
341 } |
342 /// \e |
342 /// \e |
343 virtual _Value getObjVal() = 0; |
343 virtual _Value getObjVal() = 0; |
|
344 |
|
345 //OTHER FUNCTIONS |
|
346 |
344 /// \e |
347 /// \e |
345 virtual int rowNum() const = 0; |
348 virtual int rowNum() const = 0; |
346 /// \e |
349 /// \e |
347 virtual int colNum() const = 0; |
350 virtual int colNum() const = 0; |
348 /// \e |
351 /// \e |
373 /// This class implements a lemon wrapper for glpk. |
376 /// This class implements a lemon wrapper for glpk. |
374 /// Later other LP-solvers will be wrapped into lemon. |
377 /// Later other LP-solvers will be wrapped into lemon. |
375 /// The aim of this class is to give a general surface to different |
378 /// The aim of this class is to give a general surface to different |
376 /// solvers, i.e. it makes possible to write algorithms using LP's, |
379 /// solvers, i.e. it makes possible to write algorithms using LP's, |
377 /// in which the solver can be changed to an other one easily. |
380 /// in which the solver can be changed to an other one easily. |
378 class LPSolverWrapper : public LPSolverBase<double> { |
381 class LPGLPK : public LPSolverBase<double> { |
379 public: |
382 public: |
380 typedef LPSolverBase<double> Parent; |
383 typedef LPSolverBase<double> Parent; |
381 |
384 |
382 public: |
385 public: |
383 /// \e |
386 /// \e |
384 LPX* lp; |
387 LPX* lp; |
385 |
388 |
386 public: |
389 public: |
387 /// \e |
390 /// \e |
388 LPSolverWrapper() : Parent(), |
391 LPGLPK() : Parent(), |
389 lp(lpx_create_prob()) { |
392 lp(lpx_create_prob()) { |
390 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
393 lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
391 } |
394 } |
392 /// \e |
395 /// \e |
393 ~LPSolverWrapper() { |
396 ~LPGLPK() { |
394 lpx_delete_prob(lp); |
397 lpx_delete_prob(lp); |
395 } |
398 } |
|
399 |
|
400 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
|
401 |
396 /// \e |
402 /// \e |
397 void setMinimize() { |
403 void setMinimize() { |
398 lpx_set_obj_dir(lp, LPX_MIN); |
404 lpx_set_obj_dir(lp, LPX_MIN); |
399 } |
405 } |
400 /// \e |
406 /// \e |
401 void setMaximize() { |
407 void setMaximize() { |
402 lpx_set_obj_dir(lp, LPX_MAX); |
408 lpx_set_obj_dir(lp, LPX_MAX); |
403 } |
409 } |
|
410 |
|
411 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
|
412 |
404 protected: |
413 protected: |
405 /// \e |
414 /// \e |
406 int _addCol() { |
415 int _addCol() { |
407 return lpx_add_cols(lp, 1); |
416 return lpx_add_cols(lp, 1); |
408 } |
417 } |
409 /// \e |
418 /// \e |
410 int _addRow() { |
419 int _addRow() { |
411 return lpx_add_rows(lp, 1); |
420 return lpx_add_rows(lp, 1); |
412 } |
421 } |
413 public: |
422 /// \e |
414 using Parent::setRowCoeffs; |
423 virtual void _setRowCoeffs(int i, |
415 /// \e |
424 std::vector<std::pair<int, double> > coeffs) { |
416 virtual void setRowCoeffs(int i, |
|
417 std::vector<std::pair<int, double> > coeffs) { |
|
418 int mem_length=1+colNum(); |
425 int mem_length=1+colNum(); |
419 int* indices = new int[mem_length]; |
426 int* indices = new int[mem_length]; |
420 double* doubles = new double[mem_length]; |
427 double* doubles = new double[mem_length]; |
421 int length=0; |
428 int length=0; |
422 for (std::vector<std::pair<int, double> >:: |
429 for (std::vector<std::pair<int, double> >:: |
423 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
430 const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
424 ++length; |
431 ++length; |
425 indices[length]=it->first; |
432 indices[length]=it->first; |
426 doubles[length]=it->second; |
433 doubles[length]=it->second; |
427 std::cout << " " << indices[length] << " " |
434 // std::cout << " " << indices[length] << " " |
428 << doubles[length] << std::endl; |
435 // << doubles[length] << std::endl; |
429 } |
436 } |
430 std::cout << i << " " << length << std::endl; |
437 // std::cout << i << " " << length << std::endl; |
431 lpx_set_mat_row(lp, i, length, indices, doubles); |
438 lpx_set_mat_row(lp, i, length, indices, doubles); |
432 delete [] indices; |
439 delete [] indices; |
433 delete [] doubles; |
440 delete [] doubles; |
434 } |
441 } |
435 /// \e |
442 /// \e |
436 virtual void setColCoeffs(int i, |
443 virtual void _setColCoeffs(int i, |
437 std::vector<std::pair<int, double> > coeffs) { |
444 std::vector<std::pair<int, double> > coeffs) { |
438 int mem_length=1+rowNum(); |
445 int mem_length=1+rowNum(); |
439 int* indices = new int[mem_length]; |
446 int* indices = new int[mem_length]; |
440 double* doubles = new double[mem_length]; |
447 double* doubles = new double[mem_length]; |
441 int length=0; |
448 int length=0; |
442 for (std::vector<std::pair<int, double> >:: |
449 for (std::vector<std::pair<int, double> >:: |
447 } |
454 } |
448 lpx_set_mat_col(lp, i, length, indices, doubles); |
455 lpx_set_mat_col(lp, i, length, indices, doubles); |
449 delete [] indices; |
456 delete [] indices; |
450 delete [] doubles; |
457 delete [] doubles; |
451 } |
458 } |
452 // /// \e |
459 /// \e |
453 // /// temporally, glpk style indexing |
|
454 // virtual void setRowCoeffs(RowIt row_it, int num, |
|
455 // int* indices, _Value* doubles) = 0; |
|
456 // //pair<RowIt, _Value>-bol kell megadni egy std range-et |
|
457 // /// \e |
|
458 // template <typename Begin, typename End> |
|
459 // void setRowCoeffs(RowIt row_it, Begin begin, End end) { |
|
460 // int mem_length=1+colNum(); |
|
461 // int* indices = new int[mem_length]; |
|
462 // _Value* doubles = new _Value[mem_length]; |
|
463 // int length=0; |
|
464 // for ( ; begin!=end; ++begin) { |
|
465 // ++length; |
|
466 // indices[length]=col_iter_map[begin->first]; |
|
467 // doubles[length]=begin->second; |
|
468 // } |
|
469 // setRowCoeffs(row_it, length, indices, doubles); |
|
470 // delete [] indices; |
|
471 // delete [] doubles; |
|
472 // } |
|
473 // void setRowCoeffs(RowIt row_it, int length, |
|
474 // int* indices, double* doubles) { |
|
475 // lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles); |
|
476 // } |
|
477 // using Parent::setColCoeffs; |
|
478 // void setColCoeffs(ColIt col_it, int length, |
|
479 // int* indices, double* doubles) { |
|
480 // lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles); |
|
481 // } |
|
482 // //pair<RowIt, double>-bol kell megadni egy std range-et |
|
483 // /// \e |
|
484 // template <typename Begin, typename End> |
|
485 // void setColCoeffs(const ColIt& col_it, |
|
486 // Begin begin, End end) { |
|
487 // int mem_length=1+lpx_get_num_rows(lp); |
|
488 // int* indices = new int[mem_length]; |
|
489 // double* doubles = new double[mem_length]; |
|
490 // int length=0; |
|
491 // for ( ; begin!=end; ++begin) { |
|
492 // ++length; |
|
493 // indices[length]=row_iter_map[begin->first]; |
|
494 // doubles[length]=begin->second; |
|
495 // } |
|
496 // lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles); |
|
497 // delete [] indices; |
|
498 // delete [] doubles; |
|
499 // } |
|
500 // //pair<ColIt, double>-bol kell megadni egy std range-et |
|
501 // /// \e |
|
502 // template <typename Begin, typename End> |
|
503 // void setRowCoeffs(const RowIt& row_it, |
|
504 // Begin begin, End end) { |
|
505 // int mem_length=1+lpx_get_num_cols(lp); |
|
506 // int* indices = new int[mem_length]; |
|
507 // double* doubles = new double[mem_length]; |
|
508 // int length=0; |
|
509 // for ( ; begin!=end; ++begin) { |
|
510 // ++length; |
|
511 // indices[length]=col_iter_map[begin->first]; |
|
512 // doubles[length]=begin->second; |
|
513 // } |
|
514 // lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles); |
|
515 // delete [] indices; |
|
516 // delete [] doubles; |
|
517 // } |
|
518 /// \e |
|
519 protected: |
|
520 virtual void _eraseCol(int i) { |
460 virtual void _eraseCol(int i) { |
521 int cols[2]; |
461 int cols[2]; |
522 cols[1]=i; |
462 cols[1]=i; |
523 lpx_del_cols(lp, 1, cols); |
463 lpx_del_cols(lp, 1, cols); |
524 } |
464 } |
525 virtual void _eraseRow(int i) { |
465 virtual void _eraseRow(int i) { |
526 int rows[2]; |
466 int rows[2]; |
527 rows[1]=i; |
467 rows[1]=i; |
528 lpx_del_rows(lp, 1, rows); |
468 lpx_del_rows(lp, 1, rows); |
529 } |
469 } |
530 public: |
470 virtual void _setColBounds(int i, Bound bound, |
531 /// \e |
471 double lo, double up) { |
532 void setColBounds(const ColIt& col_it, int bound_type, |
472 switch (bound) { |
533 double lo, double up) { |
473 case FREE: |
534 lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up); |
474 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
535 } |
475 break; |
536 /// \e |
476 case LOWER: |
537 double getObjCoef(const ColIt& col_it) { |
477 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
538 return lpx_get_obj_coef(lp, col_iter_map[col_it]); |
478 break; |
539 } |
479 case UPPER: |
540 /// \e |
480 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
541 void setRowBounds(const RowIt& row_it, int bound_type, |
481 break; |
542 double lo, double up) { |
482 case DOUBLE: |
543 lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up); |
483 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
544 } |
484 break; |
545 /// \e |
485 case FIXED: |
546 void setObjCoef(const ColIt& col_it, double obj_coef) { |
486 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
547 lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef); |
487 break; |
548 } |
488 } |
|
489 } |
|
490 virtual void _setRowBounds(int i, Bound bound, |
|
491 double lo, double up) { |
|
492 switch (bound) { |
|
493 case FREE: |
|
494 lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
|
495 break; |
|
496 case LOWER: |
|
497 lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
|
498 break; |
|
499 case UPPER: |
|
500 lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
|
501 break; |
|
502 case DOUBLE: |
|
503 lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
|
504 break; |
|
505 case FIXED: |
|
506 lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
|
507 break; |
|
508 } |
|
509 } |
|
510 protected: |
|
511 /// \e |
|
512 virtual double _getObjCoef(int i) { |
|
513 return lpx_get_obj_coef(lp, i); |
|
514 } |
|
515 /// \e |
|
516 virtual void _setObjCoef(int i, double obj_coef) { |
|
517 lpx_set_obj_coef(lp, i, obj_coef); |
|
518 } |
|
519 public: |
549 /// \e |
520 /// \e |
550 void solveSimplex() { lpx_simplex(lp); } |
521 void solveSimplex() { lpx_simplex(lp); } |
551 /// \e |
522 /// \e |
552 void solvePrimalSimplex() { lpx_simplex(lp); } |
523 void solvePrimalSimplex() { lpx_simplex(lp); } |
553 /// \e |
524 /// \e |
554 void solveDualSimplex() { lpx_simplex(lp); } |
525 void solveDualSimplex() { lpx_simplex(lp); } |
555 /// \e |
526 /// \e |
556 double getPrimal(const ColIt& col_it) { |
527 protected: |
557 return lpx_get_col_prim(lp, col_iter_map[col_it]); |
528 virtual double _getPrimal(int i) { |
558 } |
529 return lpx_get_col_prim(lp, i); |
|
530 } |
|
531 public: |
559 /// \e |
532 /// \e |
560 double getObjVal() { return lpx_get_obj_val(lp); } |
533 double getObjVal() { return lpx_get_obj_val(lp); } |
561 /// \e |
534 /// \e |
562 int rowNum() const { return lpx_get_num_rows(lp); } |
535 int rowNum() const { return lpx_get_num_rows(lp); } |
563 /// \e |
536 /// \e |