COIN-OR::LEMON - Graph Library

Opened 16 years ago

Last modified 6 years ago

#191 new enhancement

Benchmark questions related to Preflow — at Version 2

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by Peter Kovacs)

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 (2)

comment:1 Changed 16 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:2 Changed 16 years ago by Peter Kovacs

Description: modified (diff)
Note: See TracTickets for help on using tickets.