Changeset 1081:c0ad2673b11f in lemon-0.x for src/work
- Timestamp:
- 01/14/05 14:17:16 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1477
- Location:
- src/work/marci/lp
- Files:
-
- 2 edited
-
lp_solver_wrapper_3.h (modified) (17 diffs)
-
min_cost_gen_flow.h (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/lp/lp_solver_wrapper_3.h
r1074 r1081 37 37 38 38 namespace lemon { 39 40 39 41 40 /// \addtogroup misc … … 185 184 /// \e 186 185 virtual ~LPSolverBase() { } 186 187 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS 188 189 public: 187 190 /// \e 188 191 virtual void setMinimize() = 0; 189 192 /// \e 190 193 virtual void setMaximize() = 0; 194 195 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS 196 191 197 protected: 192 198 /// \e … … 194 200 /// \e 195 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 234 public: 197 235 /// \e … … 222 260 } 223 261 /// \e 224 virtual void setRowCoeffs(int i,225 std::vector<std::pair<int, double> > coeffs) = 0;226 /// \e227 virtual void setColCoeffs(int i,228 std::vector<std::pair<int, double> > coeffs) = 0;229 /// \e230 262 template <typename Begin, typename End> 231 263 void setRowCoeffs(RowIt row_it, Begin begin, End end) { … … 235 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 271 /// \e … … 245 277 make_pair(row_iter_map[begin->first], begin->second)); 246 278 } 247 setColCoeffs(col_iter_map[col_it], coeffs); 248 } 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: 279 _setColCoeffs(col_iter_map[col_it], coeffs); 280 } 298 281 /// \e 299 282 void eraseCol(const ColIt& col_it) { … … 323 306 } 324 307 /// \e 325 virtual void setColBounds(const ColIt& col_it, int bound_type, 326 _Value lo, _Value up) =0; 327 /// \e 328 virtual _Value getObjCoef(const ColIt& col_it) = 0; 329 /// \e 330 virtual void setRowBounds(const RowIt& row_it, int bound_type, 331 _Value lo, _Value up) = 0; 332 /// \e 333 virtual void setObjCoef(const ColIt& col_it, _Value obj_coef) = 0; 308 void setColBounds(const ColIt& col_it, Bound bound, 309 _Value lo, _Value up) { 310 _setColBounds(col_iter_map[col_it], bound, lo, up); 311 } 312 /// \e 313 void setRowBounds(const RowIt& row_it, Bound bound, 314 _Value lo, _Value up) { 315 _setRowBounds(row_iter_map[row_it], bound, lo, up); 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 328 /// \e 335 329 virtual void solveSimplex() = 0; … … 339 333 virtual void solveDualSimplex() = 0; 340 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 342 /// \e 343 343 virtual _Value getObjVal() = 0; 344 345 //OTHER FUNCTIONS 346 344 347 /// \e 345 348 virtual int rowNum() const = 0; … … 376 379 /// solvers, i.e. it makes possible to write algorithms using LP's, 377 380 /// in which the solver can be changed to an other one easily. 378 class LP SolverWrapper: public LPSolverBase<double> {381 class LPGLPK : public LPSolverBase<double> { 379 382 public: 380 383 typedef LPSolverBase<double> Parent; … … 386 389 public: 387 390 /// \e 388 LP SolverWrapper() : Parent(),391 LPGLPK() : Parent(), 389 392 lp(lpx_create_prob()) { 390 393 lpx_set_int_parm(lp, LPX_K_DUAL, 1); 391 394 } 392 395 /// \e 393 ~LP SolverWrapper() {396 ~LPGLPK() { 394 397 lpx_delete_prob(lp); 395 398 } 399 400 //MATRIX INDEPEDENT MANIPULATING FUNCTIONS 401 396 402 /// \e 397 403 void setMinimize() { … … 402 408 lpx_set_obj_dir(lp, LPX_MAX); 403 409 } 410 411 //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS 412 404 413 protected: 405 414 /// \e … … 411 420 return lpx_add_rows(lp, 1); 412 421 } 413 public: 414 using Parent::setRowCoeffs; 415 /// \e 416 virtual void setRowCoeffs(int i, 417 std::vector<std::pair<int, double> > coeffs) { 422 /// \e 423 virtual void _setRowCoeffs(int i, 424 std::vector<std::pair<int, double> > coeffs) { 418 425 int mem_length=1+colNum(); 419 426 int* indices = new int[mem_length]; … … 425 432 indices[length]=it->first; 426 433 doubles[length]=it->second; 427 std::cout << " " << indices[length] << " "428 << doubles[length] << std::endl;429 } 430 std::cout << i << " " << length << std::endl;434 // std::cout << " " << indices[length] << " " 435 // << doubles[length] << std::endl; 436 } 437 // std::cout << i << " " << length << std::endl; 431 438 lpx_set_mat_row(lp, i, length, indices, doubles); 432 439 delete [] indices; … … 434 441 } 435 442 /// \e 436 virtual void setColCoeffs(int i,437 std::vector<std::pair<int, double> > coeffs) {443 virtual void _setColCoeffs(int i, 444 std::vector<std::pair<int, double> > coeffs) { 438 445 int mem_length=1+rowNum(); 439 446 int* indices = new int[mem_length]; … … 450 457 delete [] doubles; 451 458 } 452 // /// \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: 459 /// \e 520 460 virtual void _eraseCol(int i) { 521 461 int cols[2]; … … 528 468 lpx_del_rows(lp, 1, rows); 529 469 } 530 public: 531 /// \e 532 void setColBounds(const ColIt& col_it, int bound_type, 533 double lo, double up) { 534 lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up); 535 } 536 /// \e 537 double getObjCoef(const ColIt& col_it) { 538 return lpx_get_obj_coef(lp, col_iter_map[col_it]); 539 } 540 /// \e 541 void setRowBounds(const RowIt& row_it, int bound_type, 542 double lo, double up) { 543 lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up); 544 } 545 /// \e 546 void setObjCoef(const ColIt& col_it, double obj_coef) { 547 lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef); 548 } 470 virtual void _setColBounds(int i, Bound bound, 471 double lo, double up) { 472 switch (bound) { 473 case FREE: 474 lpx_set_col_bnds(lp, i, LPX_FR, lo, up); 475 break; 476 case LOWER: 477 lpx_set_col_bnds(lp, i, LPX_LO, lo, up); 478 break; 479 case UPPER: 480 lpx_set_col_bnds(lp, i, LPX_UP, lo, up); 481 break; 482 case DOUBLE: 483 lpx_set_col_bnds(lp, i, LPX_DB, lo, up); 484 break; 485 case FIXED: 486 lpx_set_col_bnds(lp, i, LPX_FX, lo, up); 487 break; 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 520 /// \e 550 521 void solveSimplex() { lpx_simplex(lp); } … … 554 525 void solveDualSimplex() { lpx_simplex(lp); } 555 526 /// \e 556 double getPrimal(const ColIt& col_it) { 557 return lpx_get_col_prim(lp, col_iter_map[col_it]); 558 } 527 protected: 528 virtual double _getPrimal(int i) { 529 return lpx_get_col_prim(lp, i); 530 } 531 public: 559 532 /// \e 560 533 double getObjVal() { return lpx_get_obj_val(lp); } -
src/work/marci/lp/min_cost_gen_flow.h
r1074 r1081 22 22 class PrimalMap { 23 23 protected: 24 LP SolverWrapper* lp;24 LPGLPK* lp; 25 25 EdgeIndexMap* edge_index_map; 26 26 public: 27 PrimalMap(LP SolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :27 PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) : 28 28 lp(&_lp), edge_index_map(&_edge_index_map) { } 29 29 double operator[](Edge e) const { … … 212 212 } 213 213 void runByLP() { 214 typedef LP SolverWrapperLPSolver;214 typedef LPGLPK LPSolver; 215 215 LPSolver lp; 216 216 lp.setMinimize(); … … 224 224 edge_index_map.set(e, col_it); 225 225 if (lcapacity[e]==capacity[e]) 226 lp.setColBounds(col_it, LP X_FX, lcapacity[e], capacity[e]);226 lp.setColBounds(col_it, LPSolver::FIXED, lcapacity[e], capacity[e]); 227 227 else 228 lp.setColBounds(col_it, LP X_DB, lcapacity[e], capacity[e]);228 lp.setColBounds(col_it, LPSolver::DOUBLE, lcapacity[e], capacity[e]); 229 229 lp.setObjCoef(col_it, cost[e]); 230 230 } … … 233 233 lp.col_iter_map.valid(col_it); 234 234 lp.col_iter_map.next(col_it)) { 235 std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;235 // std::cout << "ize " << lp.col_iter_map[col_it] << std::endl; 236 236 } 237 237 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { … … 251 251 } 252 252 //std::cout << std::endl; 253 std::cout << " " << g.id(n) << " " << row.size() << std::endl;253 //std::cout << " " << g.id(n) << " " << row.size() << std::endl; 254 254 lp.setRowCoeffs(row_it, row.begin(), row.end()); 255 lp.setRowBounds(row_it, LP X_FX, 0.0, 0.0);255 lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0); 256 256 } 257 257 lp.solveSimplex();
Note: See TracChangeset
for help on using the changeset viewer.
