[Lemon-user] Infinite loop in LEMON Cost Scaling

[Péter Kovács]

Hi David,

I didn't experience such bug in CostScaling before.

Could you send me the whole input network and a simple code so that I 
could reproduce the issue (e.g. in a private email)?

If the source of the network is non-tirivial, then you can use the 
DigraphWriter tool to export your graph and the related maps at the 
point of the code where you use CostScaling:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00132.html

Anyway, you can try another min-cost flow algorithm of LEMON. There are 
four such classes with the same API, so you can easily switch between them:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00612.html

I suggest you to check NetworkSimplex, because it is the fastest and 
most robust algorithm in most cases.

Best regards,
Péter



2017.09.28. 17:53 keltezéssel, Lobron, David írta:
> A bit more info here: I've been stepping with a debugger in the "while true" loop, and I noticed that the last few entries in the _next_out array are changing.  For example:
> 
> Breaking at line 1405:
> (gdb) p _next_out
> $39 = std::vector of length 103, capacity 103 = {0, 15, 30, 45, 60, 88, 90, 105, 120, 135, 163, 165, 193, 208, 210, 225, 244, 255, 270, 285, 300, 315, 330, 345, 360,
>    375, 390, 405, 420, 435, 450, 465, 480, 495, 510, 525, 540, 555, 570, 585, 600, 615, 630, 645, 660, 675, 690, 705, 720, 735, 750, 765, 780, 795, 810, 825, 840, 855,
>    870, 885, 900, 915, 930, 945, 960, 975, 990, 1005, 1020, 1035, 1050, 1065, 1080, 1095, 1110, 1125, 1140, 1155, 1170, 1185, 1200, 1215, 1230, 1245, 1260, 1275, 1290,
>    1305, 1320, 1335, 1350, 1365, 1380, 1395, 1410, 1425, 1440, 1455, 1470, 1485, 1733, 2801, 2902}
> 
> A few steps later, at line 1405:
> (gdb) p _next_out
> $41 = std::vector of length 103, capacity 103 = {0, 15, 30, 45, 60, 88, 90, 105, 120, 135, 163, 165, 193, 208, 210, 225, 244, 255, 270, 285, 300, 315, 330, 345, 360,
>    375, 390, 405, 420, 435, 450, 465, 480, 495, 510, 525, 540, 555, 570, 585, 600, 615, 630, 645, 660, 675, 690, 705, 720, 735, 750, 765, 780, 795, 810, 825, 840, 855,
>    870, 885, 900, 915, 930, 945, 960, 975, 990, 1005, 1020, 1035, 1050, 1065, 1080, 1095, 1110, 1125, 1140, 1155, 1170, 1185, 1200, 1215, 1230, 1245, 1260, 1275, 1290,
>    1305, 1320, 1335, 1350, 1365, 1380, 1395, 1410, 1425, 1440, 1455, 1470, 1485, 1759, 2801, 2902}
> 
> The third-to-last element changes from 1733 to 1759.  I skipped the breakpoint 100,000 times, and observed again that only the third-to-last item had changed:
> 
> $45 = std::vector of length 103, capacity 103 = {0, 15, 30, 45, 60, 88, 90, 105, 120, 135, 163, 165, 193, 208, 210, 225, 244, 255, 270, 285, 300, 315, 330, 345, 360,
>    375, 390, 405, 420, 435, 450, 465, 480, 495, 510, 525, 540, 555, 570, 585, 600, 615, 630, 645, 660, 675, 690, 705, 720, 735, 750, 765, 780, 795, 810, 825, 840, 855,
>    870, 885, 900, 915, 930, 945, 960, 975, 990, 1005, 1020, 1035, 1050, 1065, 1080, 1095, 1110, 1125, 1140, 1155, 1170, 1185, 1200, 1215, 1230, 1245, 1260, 1275, 1290,
>    1305, 1320, 1335, 1350, 1365, 1380, 1395, 1410, 1425, 1440, 1455, 1470, 1485, 1863, 2801, 2902}
> 
> The last_out variable, which needs to match _next_out[tip] for us to exit the loop, is equal to the second-to-last item in the array:
> 
> (gdb) p last_out
> $46 = 2801
> 
> It seems like there might be an off-by-one error here, but I can't quite tell.  It definitely appears that we're not augmenting _tip properly.  The _target array looks like this:
> 
> (gdb) p _target
> $48 = std::vector of length 3004, capacity 3004 = {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100,
>    100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
>    100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101,
>    102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100,
>    100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100,
>    100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100, 100, 100, 100,
>    100, 100, 100, 100, 100, 101, 102, 100, 100, 100, 100, 100...}
> 
> I'll continue to debug, but any help you can give would be appreciated, as I'm still not entirely sure what the expected behavior is that should guarantee that we get to the augment step.
> 
> Thank you,
> 
> David
> 
> 
>> On Sep 28, 2017, at 10:50 AM, Lobron, David <dlobron at akamai.com> wrote:
>>
>> 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
>>
>>
>>
>>
>