COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 9 years ago

#191 new enhancement

Benchmark questions related to Preflow

Reported by: kpeter Owned by: kpeter
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by kpeter)

There are some efficiency questions about the Preflow implementation, that require thorough benchmarking.

  • Elevator or LinkedElevator should be used by default?
  • The BFS implementation in the init() function could be made more efficient using only one vector and three indices (first, last, new_level).
  • We should try very large instances and check again whether the current heuristics and the constant 20 factor that is used for them are really optimal or not.
  • We should try Goldberg's new idea of partial augmentations. (However it should probably be a new class.)

Change History (3)

comment:1 Changed 10 years ago by alpar

  • Milestone LEMON 1.1 release deleted

comment:2 Changed 10 years ago by kpeter

  • Description modified (diff)

comment:3 Changed 9 years ago by kpeter

  • Type changed from task to enhancement
Note: See TracTickets for help on using tickets.