[Lemon-user] Infinite loop in LEMON Cost Scaling

[Lobron, David]

Hello LEMON developers,

I recently encountered an infinite-loop behavior in lemon's Cost Scaling algorithm, in the loop starting on line 1378 of cost_scaling.h (the partial augment and relabel operations).  To exit the loop, the _active_nodes deque has to be empty.  I am finding that the number of elements in the array never changes- it always has 102 elements.  Here's a snapshot of the array in gdb:

(gdb) p _active_nodes
$3 = std::deque with 102 elements = {16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 
  48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 
  89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 0, 1, 2, 3, 4, 6, 7, 8, 9, 5, 11, 10, 14, 12, 15, 13}

I set breakpoints on the lines where _active_nodes is changed (1382 and 1459), but neither one was triggered.  

I printed out all of the arcs in my input graph that have nonzero flow.  Here, the first number is the internal arc number, and the rest of the numbers respectively are the source, destination, l bound cap, u bound cap, arc flow, and arc cost:

13: src=0, dest=2, l=0, u=75915662, flow=5148395, cost=0.000000
42: src=5, dest=1, l=0, u=5939549, flow=5939549, cost=0.000000
79: src=7, dest=1, l=0, u=520947, flow=17127440, cost=90.000000
91: src=8, dest=1, l=0, u=143010, flow=5148395, cost=70.000000
195: src=0, dest=15, l=0, u=75915662, flow=5939549, cost=0.000000
377: src=0, dest=28, l=0, u=75915662, flow=1365077, cost=0.000000
639: src=47, dest=1, l=0, u=488270, flow=7171507, cost=90.000000
643: src=0, dest=47, l=0, u=75915662, flow=7171507, cost=0.000000
709: src=52, dest=1, l=0, u=943, flow=33956, cost=90.000000
1003: src=73, dest=1, l=0, u=934392, flow=33638135, cost=90.000000
1007: src=0, dest=73, l=0, u=75915662, flow=33638135, cost=0.000000
1031: src=75, dest=1, l=0, u=37918, flow=1365077, cost=90.000000
1129: src=82, dest=1, l=0, u=152544, flow=5491603, cost=90.000000
1133: src=0, dest=82, l=0, u=75915662, flow=5491603, cost=0.000000
1203: src=0, dest=87, l=0, u=75915662, flow=17127440, cost=0.000000
1273: src=0, dest=92, l=0, u=75915662, flow=33956, cost=0.000000

I was curious as to whether you have seen this behavior before.  Do this this is a bug in LEMON, or is my input graph invalid?  I'd very much like to understand this.  I've seen a similar behavior from the cs2 program from IG Systems, so it appears that either my input is invalid in both cases, or there's a shared bug.

Thank you in advance for any help you can give.

Sincerely,

David