COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 2 weeks ago

#191 new enhancement

Benchmark questions related to Preflow

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

comment:1 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:2 Changed 10 years ago by Peter Kovacs

Description: modified (diff)

comment:3 Changed 9 years ago by Peter Kovacs

Type: taskenhancement

comment:4 Changed 4 weeks ago by Peter Kovacs

Another idea to be considered is to store the last outgoing arc for each node, see #431.

comment:5 Changed 2 weeks ago by Peter Kovacs

Milestone: LEMON 1.5 release
Note: See TracTickets for help on using tickets.