Apparent issue with ILP algorithm

[Isaac-D-Cohen]

My friend came up with an algorithm for the partition problem, and to test it, we implemented it in python and we’ve been checking its answers using prtpy. However, we noticed something strange. When we try our 1,000 value test case on prtpy using ilp like this:

answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=numbers, objective=prtpy.obj.MaximizeSmallestSum)

the answer appears to depend on the order the numbers were in. Here’s our 1,000 values:

[26364, 9592, 26314, 736, 9094, 6997, 12413, 26366, 4949, 11976, 24596, 11330, 455, 10306, 94, 17274, 7212, 14680, 5698, 13821, 8526, 13547, 27633, 22944, 29813, 26345, 16627, 22246, 26471, 29402, 24290, 5347, 16517, 10246, 26521, 2560, 4115, 9013, 27039, 7093, 28660, 23346, 24195, 32629, 9257, 9054, 1108, 11144, 18633, 15102, 27882, 5630, 17423, 30692, 6948, 15101, 3233, 6680, 6381, 31773, 29461, 15599, 28909, 24504, 5056, 1903, 17514, 19891, 32687, 12744, 31594, 25175, 450, 14733, 6303, 21306, 9653, 21410, 13424, 32532, 13181, 16574, 12916, 13352, 8813, 12604, 23784, 16457, 2546, 1771, 28268, 25115, 13998, 16253, 22370, 12170, 12693, 9051, 17819, 20878, 4631, 6473, 19895, 13141, 7530, 26169, 3620, 17779, 22291, 29229, 7266, 9257, 31133, 7872, 25595, 13404, 17228, 10086, 14051, 19794, 12125, 13428, 14673, 19058, 10090, 21192, 31415, 24523, 8234, 309, 20259, 3877, 30506, 29703, 3241, 10931, 12034, 18577, 28994, 31984, 8350, 6427, 7478, 23018, 11896, 1198, 3833, 25958, 8435, 31884, 32399, 24114, 8464, 21075, 13872, 26592, 1492, 2627, 15845, 479, 8603, 26666, 28178, 4613, 29982, 21856, 22887, 27429, 22172, 7974, 18257, 31688, 12832, 29989, 20889, 5439, 681, 25894, 28278, 15902, 19101, 6924, 18154, 23341, 23105, 26172, 30424, 15045, 7364, 11563, 12080, 11391, 1047, 28566, 23156, 13129, 31404, 965, 30492, 26086, 19187, 13186, 3646, 16424, 28614, 12769, 10345, 5124, 29873, 9408, 22564, 24301, 22756, 31312, 5217, 9316, 21394, 20978, 12820, 14661, 14665, 4930, 29316, 21896, 6672, 30422, 31233, 13817, 16564, 28782, 10702, 20345, 10215, 29576, 21773, 18843, 8879, 25848, 13063, 914, 31293, 28928, 11146, 5862, 26365, 19862, 25479, 17405, 8840, 27828, 2544, 7587, 29647, 15602, 20301, 18732, 5662, 3454, 20383, 23478, 5904, 6479, 26031, 10916, 4383, 23215, 4746, 12797, 9358, 14558, 19914, 7511, 18389, 22219, 18442, 5680, 32530, 10525, 25910, 23686, 19223, 30849, 8881, 6004, 24924, 18979, 15708, 18982, 10287, 9307, 18856, 7755, 13960, 25401, 8001, 25007, 30112, 105, 20447, 12387, 30044, 303, 32408, 26131, 13550, 2574, 6989, 1384, 14431, 9572, 16849, 2985, 9660, 24957, 17424, 7995, 31507, 20408, 5293, 8328, 6185, 7826, 708, 5740, 9733, 26037, 24243, 28084, 30373, 24322, 16166, 2499, 8931, 11033, 30748, 25090, 4429, 19763, 23670, 32273, 13321, 19710, 21876, 9632, 13995, 23631, 5325, 4738, 10348, 12507, 14231, 16705, 32672, 29473, 15923, 23057, 13021, 8557, 23151, 7019, 32293, 9109, 6051, 22038, 2204, 10951, 5413, 6748, 1011, 11578, 11176, 4402, 27808, 18838, 9525, 18138, 25106, 26009, 7334, 21767, 739, 21, 4713, 23933, 503, 15972, 11178, 19432, 22764, 28981, 18687, 14037, 6426, 15817, 32173, 20571, 11861, 30023, 11450, 23155, 19131, 30109, 7480, 22493, 19124, 26656, 5842, 20939, 10159, 13300, 11367, 18166, 21051, 16157, 17459, 23486, 19282, 7934, 26500, 21667, 19713, 30225, 8867, 15883, 29221, 24446, 26399, 18196, 652, 8587, 6600, 20344, 451, 21974, 23764, 14251, 2495, 5948, 3052, 27741, 24658, 32394, 18011, 27791, 3731, 18225, 31956, 31412, 19673, 15286, 3755, 9366, 11029, 29150, 17613, 21552, 11366, 17165, 20355, 8308, 15244, 2233, 16299, 10920, 16053, 4309, 7501, 11897, 14456, 748, 13455, 6059, 3086, 31007, 8735, 15026, 5289, 19964, 25643, 12492, 51, 30943, 1751, 12051, 19058, 7768, 3526, 19913, 30146, 32608, 9122, 18991, 9168, 20280, 7198, 19644, 15001, 32676, 8652, 24366, 27862, 23234, 21706, 13651, 31451, 16028, 28975, 17356, 4694, 32635, 14864, 11516, 31168, 19230, 19148, 10700, 4288, 11893, 18774, 842, 8481, 25097, 23518, 24117, 28133, 30864, 12522, 5783, 10707, 21670, 28218, 26866, 24288, 24083, 17612, 6636, 19638, 3297, 13751, 14024, 11321, 31510, 13160, 22737, 13826, 6865, 27282, 11441, 23386, 31202, 4884, 30822, 18264, 20402, 12191, 6159, 11874, 1638, 30260, 16392, 28800, 3150, 15822, 29212, 518, 23568, 984, 22682, 11217, 18979, 10742, 3418, 5101, 1671, 4950, 19832, 24676, 11490, 28656, 23202, 23330, 3160, 17091, 15518, 5592, 24194, 10044, 29104, 30062, 22134, 20762, 14299, 12226, 83, 26241, 14802, 30538, 10444, 32182, 20035, 14818, 31175, 1463, 9685, 9169, 13554, 26050, 11002, 18413, 26297, 21356, 28385, 28682, 18276, 9610, 31295, 22121, 32328, 3536, 3113, 3589, 21019, 15448, 30605, 29114, 8095, 20936, 16173, 12493, 9109, 11485, 17272, 17488, 14555, 12803, 27246, 8941, 14529, 4379, 31650, 6057, 6453, 27170, 28587, 28784, 20, 2311, 27286, 441, 12694, 12480, 21924, 731, 1971, 29184, 13645, 12218, 3470, 14534, 20634, 3949, 29745, 7486, 467, 24476, 21047, 14967, 18995, 27427, 16261, 1894, 21217, 4647, 14692, 23346, 18196, 22205, 25723, 10581, 19556, 7412, 29809, 17783, 13444, 18987, 28296, 2523, 6611, 5394, 6613, 1719, 11570, 5657, 31523, 12496, 12177, 8087, 4266, 29642, 16738, 30267, 20804, 27797, 9936, 3432, 32694, 27273, 30333, 14587, 15247, 12938, 10170, 28746, 31721, 7173, 22697, 6890, 15195, 10624, 6492, 20161, 19284, 14529, 8558, 10575, 4110, 1871, 1474, 16566, 26479, 30043, 13261, 30563, 4210, 17311, 28272, 23149, 4532, 10102, 23224, 24209, 4652, 31741, 1273, 17712, 20453, 22886, 19758, 12670, 22272, 11142, 11737, 10158, 15422, 28174, 28951, 27479, 24434, 26215, 22381, 16697, 21141, 1745, 17012, 2670, 28816, 11958, 4069, 14045, 13238, 19266, 9761, 21230, 16748, 3665, 20461, 1603, 3970, 492, 6200, 16311, 28300, 10863, 27878, 20872, 23262, 18557, 1812, 13079, 11893, 28448, 17765, 26058, 30756, 32726, 1903, 3152, 25098, 13731, 17514, 24036, 9460, 15970, 8356, 10625, 17448, 16042, 31695, 31846, 27781, 5641, 25916, 17714, 27445, 20588, 12521, 11916, 17380, 1090, 24997, 22812, 25335, 5051, 10975, 10318, 790, 21051, 9419, 11896, 2284, 11901, 16151, 16145, 22378, 19774, 25097, 28477, 5886, 4014, 11939, 1166, 3626, 2152, 5387, 4338, 24795, 16703, 6438, 23967, 32648, 22203, 31002, 1626, 16130, 22131, 22907, 28208, 4931, 4795, 9210, 29862, 4155, 1558, 4420, 1329, 22277, 8563, 25428, 29933, 27567, 11350, 21921, 30052, 13289, 28768, 7427, 6380, 4261, 13237, 16331, 275, 31673, 13183, 12440, 31324, 25456, 14813, 29714, 1464, 29389, 8772, 20, 5959, 12130, 51, 10902, 19225, 26163, 16970, 20562, 4178, 8691, 2232, 19356, 20453, 31590, 21050, 31026, 17991, 26923, 780, 24079, 17302, 10804, 10656, 10640, 23370, 25580, 17496, 25436, 9194, 28163, 24375, 1654, 30817, 17613, 10168, 5393, 11304, 32715, 21031, 6626, 964, 1131, 5255, 25694, 12695, 5848, 24373, 30952, 28000, 28379, 15110, 24053, 21970, 26417, 798, 30628, 23178, 11223, 25846, 5814, 23359, 12760, 32309, 9007, 15162, 20166, 11994, 11768, 990, 19168, 26953, 2735, 16797, 20120, 15310, 22448, 17370, 118, 13686, 2361, 16543, 12761, 25944, 17107, 23441, 1919, 13627, 8975, 1039, 21014, 24442, 2495, 11297, 23901, 17811, 2355, 6749, 31387, 14858, 997, 26147, 20360, 26007, 19970, 12621, 29927, 30845, 20532]

Suppose we store them in a python list called original_values.

>> len(original_values)
1000

>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)

>> len(answer[0])
491
>> len(answer[1])
509
>> sum(answer[0]) – sum(answer[1])
-3

Alright, now suppose we take the arrays from our answer and put them back together and try this again:

>> original_values = answer[0] + answer[1]
>> len(original_values)
1000
>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)

>> len(answer[0])
500
>> len(answer[1])
500
>> sum(answer[0]) – sum(answer[1])
-3

So it has given us a different answer, but the difference is still 3. So that makes sense. Now, let’s try this once more:

>> original_values = answer[0] + answer[1]
>> len(original_values)
1000
>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)

>> len(answer[0])
492
>> len(answer[1])
508
>> sum(answer[0]) – sum(answer[1])
-7

How could this be? Shouldn’t the same numbers result in the same difference?

Repeating this process further gives us other differences. I got -31 on the next round.

Another thing we tried was sorting the numbers first:

>> original_values = answer[0] + answer[1]
>> original_values.sort()
>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)

>> sum(answer[0]) – sum(answer[1])
-15

You can also try reverse sorting them:

>> original_values.sort()
>> original_values.reverse()
>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)
>> len(answer[0])
646
>> len(answer[1])
354
>> sum(answer[0]) – sum(answer[1])
-3

How can this be? Shouldn’t the same numbers always result in the same difference, regardless of the order in which they are entered?

[erelsgl]

Hi Isaac. This might be a bug in the ILP solver. But it is hard to debug such a large instance. Can you find the smallest instance that illustratese this issue?

[Isaac-D-Cohen]

Ok, I did a little testing and I'm not sure if this is the smallest, but it appears to occur at 15 with these numbers:

[7740, 489, 152, 3410, 9948, 7862, 8519, 3212, 8798, 4979, 2178, 5984, 2518, 3270, 7183]

>>> x = [7740, 489, 152, 3410, 9948, 7862, 8519, 3212, 8798, 4979, 2178, 5984, 2518, 3270, 7183]
>>> answer = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=x, objective=prtpy.obj.MaximizeSmallestSum)
>>> sum(answer1[0]) - sum(answer1[1])
-2
>>> x.sort()
>>> answer2 = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=x, objective=prtpy.obj.MaximizeSmallestSum)
>>> sum(answer2[0]) - sum(answer2[1])
-4

[Isaac-D-Cohen]

Ok, there's an example at 8:

[3984, 9928, 3636, 2852, 4957, 5366, 4456, 5905]

Here's the little script I've been using to find these:

#!/bin/python

from numpy.random import seed
from numpy.random import randint
import prtpy

seed(1)

for _ in range(1000):
    for i in range(1, 10):
        original_values = randint(0, 10000, i)
        answer1 = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)
        diff1 = abs(sum(answer1[0]) - sum(answer1[1]))
        original_values.sort()
        answer2 = prtpy.partition(algorithm = prtpy.partitioning.ilp, numbins=2, items=original_values, objective=prtpy.obj.MaximizeSmallestSum)
        diff2 = abs(sum(answer2[0]) - sum(answer2[1]))
        
        if diff1 != diff2:
            print("\n\nFound example at ", i, ":")
            print("One answer with a diff of ", diff1, ":")
            print(answer1[0])
            print(answer1[1])
            print("\nThe other answer with a diff of ", diff2, ":")
            print(answer2[0])
            print(answer2[1])

[erelsgl]

The example with 8 works fine on my computer (I get -284 in both cases), but I managed to reproduce the error with the example with 15. It seems to come from the integer programming engine used by prtpy. I opened an issue in python-mip: coin-or/python-mip#337 but it is probably also related to cbc: https://github.com/coin-or/Cbc