COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 8 years ago

#435 closed enhancement (fixed)

Improved implementation of the Altering List pivot rule in NetworkSimplex

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

Description (last modified by Peter Kovacs)

The attached patch improves the implementation of the Altering List pivot rule in NetworkSimplex.

Attachments (1)

435-fcb6ad1e67d0.patch (4.1 KB) - added by Peter Kovacs 8 years ago.

Download all attachments as: .zip

Change History (4)

comment:1 Changed 8 years ago by Peter Kovacs

Description: modified (diff)
Status: newassigned

Changed 8 years ago by Peter Kovacs

Attachment: 435-fcb6ad1e67d0.patch added

comment:2 Changed 8 years ago by Peter Kovacs

[fcb6ad1e67d0] modifies the Altering List pricing strategy: partial_sort() is used instead of heap operations and the size of the hot list is divided by 10. With these modifications, this rule turned out to be more stable and faster on all kind of input instances I have tested so far. Now it performs similarily or sometimes faster than the default rule (block search). (The default option is not changed, since block search is simpler rule and it seems to be slightly more stable.)

comment:3 Changed 8 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

[fcb6ad1e67d0] has been pushed to the main branch. Thanks.

Note: See TracTickets for help on using tickets.