compute_polytope_vertices does not work for large matrices

[paulpacaud]

Problem:

Using the exact same code as in the documentation, but using :
A: 114x14 matrix,
b: a 114x1 matrix,
the function compute_polytope_vertices(A,b) returns an empty array, like if it does not find any vertice of the polytope.
Yet, the two matrices used come from a real problem in which I am pretty sure A and b define a not-empty polytope.

Reproduce the problem:

A = np.array(
                [
                    [-2751, -2434, -2753, 3633, 1745, 273, 1941, -2848, -73, 1805, 1496, 1615, -2906, -2793],
                    [-2159, -2029, -2137, 3219, 1239, 81, 1488, -2141, -51, 1349, 1110, 1090, -2184, -2149],
                    [-976, -953, -963, -1641, 823, -1025, 3697, -956, -4, 2119, 735, -98, -967, -963],
                    [1079, 1075, 1074, 2226, -703, 1085, -3991, 1060, 5, -2225, -793, 372, 1073, 1073],
                    [-1079, -1075, -1074, -2226, 703, -1085, 3991, -1060, -5, 2225, 793, -372, -1073, -1073],
                    [1033, 1039, 1032, 2317, -580, 1017, -3778, 1017, 5, -2077, -752, 476, 1029, 1031],
                    [-1033, -1039, -1032, -2317, 580, -1017, 3778, -1017, -5, 2077, 752, -476, -1029, -1031],
                    [344, -217, 59, 4074, -5481, 476, -1039, 152, -1, -2287, -271, -8685, 169, 92],
                    [4830, 4446, 4714, -6473, -3006, -38, -3406, 4727, 119, -3150, -2589, -2743, 4818, 4742],
                    [-2645, -2889, -2681, -8515, 2621, -118, 1884, -2530, -47, 2029, 1147, 2962, -2581, -2652],
                    [2576, 2362, 2282, -5413, -1505, -103, -1288, 2163, 41, -1297, -882, -1595, 2225, 2266],
                    [430, 1586, 1676, -3653, -995, -126, -855, 1624, 29, -860, -597, -1054, 1704, 1683],
                    [865, -6537, -3019, 1819, -2655, 469, -728, -1735, 1, -1186, -275, -3653, -1512, -2592],
                    [-6085, -5890, -5983, -5640, 4596, -6947, 11761, -5951, -59, 9474, 7106, -213, -6020, -5991],
                    [974, 5915, 5032, -9482, -1643, -438, -1870, 4493, 69, -1747, -1373, -1492, 4616, 4912],
                    [1167, 6992, 5698, -9742, -1505, -511, -1879, 4962, 72, -1719, -1402, -1277, 5070, 5522],
                    [-1684, -1209, -1384, 7054, 2227, -166, 1289, -1393, -27, 1498, 737, 2689, -1441, -1400],
                    [-2222, -2748, -2457, -7019, -5186, -88, -4046, -2289, -103, -4070, -984, -5616, -2333, -2419],
                    [-869, 18201, -17551, 1705, 2053, 275, 1149, -10410, -39, 1335, 764, 2510, -5258, -9010],
                    [405, -6065, 12248, -827, -910, -158, -530, 4897, 19, -607, -360, -1102, 3050, 16631],
                    [224, -2666, 16105, -464, -485, -98, -290, 3932, 11, -328, -199, -584, 1659, 26096],
                    [-272, 4655, 12242, 559, 638, 96, 364, -559, -12, 420, 244, 776, -2375, -37504],
                    [373, -6784, -26190, -768, -891, -126, -505, -613, 17, -584, -337, -1087, 3401, -49448],
                    [570, -10076, -26656, -1175, -1351, -198, -768, 133, 25, -886, -514, -1645, 5122, -46987],

                    [-373, 6784, 26190, 768, 891, 126, 505, 613, -17, 584, 337, 1087, -3401, 49448],
                    [-473, 7946, 22635, 976, 1109, 170, 634, -1012, -22, 731, 426, 1348, -4167, 46460],
                    [-570, 10076, 26656, 1175, 1351, 198, 768, -133, -25, 886, 514, 1645, -5122, 46987],
                    [597, -9991, -18189, -1169, -1330, -223, -766, 17224, 27, -881, -519, -1614, 2299, -9249],
                    [-597, 9991, 18189, 1169, 1330, 223, 766, -17224, -27, 881, 519, 1614, -2299, 9249],
                    [478, -8222, -22763, -986, -1126, -169, -642, 675, 22, -741, -430, -1370, 0, 0],
                    [-478, 8222, 22763, 986, 1126, 169, 642, -675, -22, 741, 430, 1370, 0, 0],
                    [1653, 1846, 1735, 2696, 3484, 1661, 4226, 1672, 178, 4090, 6117, 3152, 1688, 1721],
                    [-6457, -7622, -6959, -12885, -17407, -5738, -21606, -6593, -990, -20704, -27702, -15512, -6683,
                     -6876],
                    [-4257, -5789, -4955, -17703, -11726, 10530, -8394, -4466, -167, -8638, -1404, -13078, -4597,
                     -4847],
                    [588, 470, 533, 179, -922, 1222, -1790, 560, -10, -1545, -4882, -534, 560, 541],
                    [-588, -470, -533, -179, 922, -1222, 1790, -560, 10, 1545, 4882, 534, -560, -541],
                    [-8913, -9574, -9467, -4749, -2558, 6891, -676, -9138, -163, -1081, 532, -3496, -9441, -9447],
                    [-9766, -10166, -10181, -4218, -1967, 9356, 75, -9926, -212, -396, 1287, -2993, -10207, -10176],
                    [-3914, -5870, -4994, -6461, -3861, 4834, -2554, -4283, -13, -2756, -1388, -4490, -4595, -4870],
                    [-3576, -9529, -6370, -4420, -3904, 94, -2186, -4068, 55, -2537, -1370, -4768, -4554, -5886],
                    [-2196, -9555, -7950, -2930, -2877, -118, -1604, -5076, 46, -1866, -1028, -3518, -6995, -7643],
                    [-573, -1818, 4836, -3332, -3025, -628, -1871, 6422, 69, -2094, -1297, -3604, 8263, 5719],
                    [-1201, -12437, -7255, -3219, -3395, -358, -1922, -925, 62, -2223, -1266, -4138, -835, -6032],
                    [-788, 2180, 4443, 215, 262, 2, 137, 10125, -4, 163, 85, 325, 1075, 4476],
                    [-92, 12983, 10039, 1303, 1654, 94, 875, 1627, -25, 1039, 557, 2048, -3009, 8437],
                    [14, 9036, 10430, 298, 531, -35, 245, 3243, -5, 308, 141, 677, -96, 9589],
                    [-181, 13821, 7727, 1450, 1825, 120, 974, 626, -29, 1153, 623, 2258, -3522, 5839],
                    [262, 9037, 23315, 256, 560, -135, 222, 18682, -1, 299, 106, 733, -16142, 24758],
                    [227, 8938, 23894, 297, 591, -119, 245, 17575, -3, 323, 124, 768, -15654, 29876],
                    [432, -2658, -47, -4573, -3411, 233, -1807, 838, 42, -2146, -1078, -4220, 1079, 269],

                    [-683, -2290, 4313, -2972, -2877, -554, -1735, 5943, 63, -1960, -1192, -3451, 7747, 5196],
                    [-575, 13860, 23596, 1870, 2106, 234, 1182, 13994, -38, 1371, 779, 2573, 48845, 26067],
                    [9030, 5959, 7296, -3859, -4443, -17143, -6047, 8207, 638, -5499, -6617, -3599, 7860, 7473],
                    [9030, 5960, 7296, -3860, -4443, -17144, -6047, 8208, 638, -5499, -6617, -3599, 7861, 7474],
                    [-7094, -11508, -13483, -3590, -3259, -87, -1914, -14290, 51, -2180, -1236, -3934, -14657, -13775],
                    [869, -18201, 17551, -1705, -2053, -275, -1149, 10410, 39, -1335, -764, -2510, 5258, 9010],
                    [680, 918, 787, 582, -3044, 246, -796, 726, 6, -2954, -304, 2206, 732, 771],
                    [-2081, -3089, -2539, -579, 12025, -318, 1943, -2295, -33, 3945, 952, -3701, -2313, -2472],
                    [2081, 3089, 2539, 579, -12025, 318, -1943, 2295, 33, -3945, -952, 3701, 2313, 2472],
                    [406, 549, 470, 339, 3759, 145, -472, 432, 4, -1733, -182, 1343, 437, 460],
                    [-1404, -1978, -1660, -1236, -18567, -160, 4088, -1512, -33, -10910, 959, -6702, -1528, -1620],
                    [1091, 1157, 1110, 2501, -14607, 744, -2152, 1074, 8, -4701, -636, 15124, 1088, 1103],
                    [3122, 4358, 3676, 2295, 1608, 743, -3743, 3363, 48, -4391, -1603, 18961, 3394, 3592],
                    [-1836, -2404, -2086, -3466, -9729, -343, -20987, -1927, -110, -15928, 2273, -6802, -1952, -2046],
                    [-8134, -9434, -8695, -18002, -16233, -4982, -6438, -8284, -181, -7689, 9462, -18359, -8383, -8601],
                    [8134, 9434, 8695, 18002, 16233, 4982, 6438, 8284, 181, 7689, -9462, 18359, 8383, 8601],
                    [6486, 6884, 6648, 16459, 3034, 5784, -7101, 6472, 93, -4114, -7255, 7443, 6547, 6616],
                    [6211, 6202, 6192, 17375, -2208, 6584, -10303, 6114, 70, -7797, -7154, 2476, 6185, 6187],
                    [-750, -736, -741, -1642, 812, -783, 4103, -734, -2, 2064, 535, -144, -743, -741],
                    [-812, -764, -788, -1789, 1474, -966, 4321, -789, 3, 3129, 436, 167, -797, -790],
                    [-5866, -6537, -6151, -8547, -13973, -5537, -22713, -5939, 79, -22343, 1160, -11312, -5990, -6102],
                    [5866, 6537, 6151, 8547, 13973, 5537, 22713, 5939, -79, 22343, -1160, 11312, 5990, 6102],
                    [-3713, -4738, -4164, -9658, -13060, -253, -12245, -3862, -155, -11179, 9360, -12317, -3921, -4091],
                    [3713, 4738, 4164, 9658, 13060, 253, 12245, 3862, 155, 11179, -9360, 12317, 3921, 4091],
                    [5178, 5772, 5430, 7539, 12369, 4886, 17503, 5242, -69, 20015, -1023, 9994, 5287, 5387],
                    [4988, 6507, 5649, 6268, 11820, 1417, -6290, 5231, 84, -1563, -3041, 21078, 5290, 5543],
                    [-4988, -6507, -5649, -6268, -11820, -1417, 6290, -5231, -84, 1563, 3041, -21078, -5290, -5543],

                    [27, -516, -942, -55, -65, -10, -37, 21556, 1, -43, -25, -80, 169, -436],
                    [99, -2659, -4101, -716, -678, -255, -447, -13728, 20, -491, -330, -793, -2786, -4074],
                    [13604, 14405, 13924, 17915, 21082, 15357, 24375, 13632, -738, 25000, 25593, 19569, 13726, 13863],
                    [-13604, -14405, -13924, -17915, -21082, -15357, -24375, -13632, 738, -25000, -25593, -19569,
                     -13726, -13863],
                    [8345, 7908, 8133, 5906, 5149, 6088, 4298, 8256, -4403, 4360, 3646, 5554, 8231, 8162],
                    [-23391, -24200, -23674, -28499, -28737, -30569, -29212, -23305, -2144, -28476, -30499, -28476,
                     -23463, -23606],
                    [-28932, -27486, -28255, -20747, -18234, -21270, -15401, -28692, 946, -15617, -13229, -19584,
                     -28585, -28354],
                    [28932, 27486, 28255, 20747, 18234, 21270, 15401, 28692, -946, 15617, 13229, 19584, 28585, 28354],
                    [15217, 14571, 15132, 10852, 9656, 10621, 8234, 15584, -368, 8335, 7221, 10336, 15340, 15204],
                    [160, 206, 180, 181, 1085, 76, -251, 168, 1, 8246, -70, 533, 170, 177],
                    [-690, -797, -737, -942, -2419, -570, -643, -705, 6, -9549, 107, -1584, -711, -729],
                    [-103, -133, -117, -117, -702, -49, 163, -109, -1, 16456, 45, -345, -110, -115],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 14947, 0, 0, 0, 0],
                    [-43, -85, -62, 8, -1039, 59, 626, -51, -4, -10518, 81, -377, -51, -59],
                    [33, 17, 25, 86, -398, 82, 405, 29, -3, -12064, 37, -85, 29, 25],
                    [-662, -284, -461, -4067, 4609, -446, 1209, -509, -6, 2188, 412, 6618, -528, -479],
                    [738, -588, 99, 8135, -16298, 2324, -4947, 351, -18, -7975, -1113, -21603, 376, 179],
                    [662, 284, 461, 4067, -4609, 446, -1209, 509, 6, -2188, -412, -6618, 528, 479],
                    [-7783, -8589, -8122, -11137, -17317, -7679, -23045, -7863, 137, -28332, 11, -14235, -7928, -8062],
                    [6457, 7622, 6959, 12885, 17407, 5738, 21606, 6593, 990, 20704, 27702, 15512, 6683, 6876],

                    [8207, 9256, 8653, 14323, 17365, 8720, 20211, 8307, 827, 18972, 28760, 16081, 8401, 8576],
                    [557, 1736, 1086, 6408, 13189, -5173, 17235, 768, 198, 15165, -5768, 10971, 810, 1005],
                    [2837, 2496, 2675, 2929, -3907, 5194, -16064, 2744, -273, -12992, -29, -586, 2751, 2697],
                    [-792, 159, -361, 3484, 10186, -5899, 15759, -608, 185, 13635, -4592, 7779, -582, -426],
                    [-4360, -3743, -4068, -2003, 3769, -10184, 8155, -4201, -12, 6925, 12203, 1761, -4208, -4108],
                    [3359, 2692, 3048, 582, -4936, 8857, -8828, 3200, -13, -7588, -13422, -3056, 3200, 3092],
                    [7783, 8589, 8122, 11137, 17317, 7679, 23045, 7863, -137, 28332, -11, 14235, 7928, 8062],
                    [-8207, -9256, -8653, -14323, -17365, -8720, -20211, -8307, -827, -18972, -28760, -16081, -8401,
                     -8576],
                    [-557, -1736, -1086, -6408, -13189, 5173, -17235, -768, -198, -15165, 5768, -10971, -810, -1005],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100000],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -100000],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100000, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -100000, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100000, 100000],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -100000, -100000],
                    [100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000,
                     100000, 100000],
                    [-100000, -100000, -100000, -100000, -100000, -100000, -100000, -100000, -100000, -100000, -100000,
                     -100000, -100000, -100000]
                ]
            )

            b = np.array([17700000, 16900000, 24000000, 17500000, 24700000, 17400000, 24800000, 38000000, 67500000,
                          46100000, 39100000, 19300000, 99600000, 107400000, 46400000, 50200000,
                          25100000, 41900000, 257800000, 129100000, 121600000, 89400000, 158800000,
                          155300000, 104300000, 100200000, 108000000, 116700000, 134800000, 156500000,
                          106800000, 36200000, 89200000, 149100000, 26100000, 38300000, 64500000,
                          73100000, 79800000, 87400000, 82400000, 69900000, 135900000, 64400000,
                          103400000, 73600000, 114800000, 107300000, 103300000, 68600000, 71100000,
                          194800000, 60700000, 60700000, 79600000, 286600000, 23100000, 12400000,
                          62800000, 25600000, 69400000, 111400000, 142100000, 91600000, 89400000,
                          160600000, 108500000, 87000000, 27500000, 27800000, 98600000, 150800000,
                          92300000, 157100000, 116300000, 157100000, 66200000, 118800000, 28900000,
                          158700000, 67100000, 22800000, 56800000, 173900000, 63700000, 34200000,
                          19900000, 9900000, 23700000, 23900000, 23500000, 28300000, 35300000,
                          99500000, 32300000, 98400000, 171200000, 168800000, 165900000, 63700000,
                          151300000, 136600000, 103600000, 154400000, 91100000, 122500000, 100000000,
                          100000000, 100000000, 100000000, 0, 0, 0, 0])

            vertices = compute_polytope_vertices(A,b)

Question:
@stephane-caron and the developer team, do you have any idea how to solve this issue ?

[stephane-caron]

It seems indeed that cdd does not find any vertex. It could be that the set is empty, or the problem hits some numerical issue.

One small piece of advice: your NumPy arrays will have an integer datatype, but compute_polytope_vertices assumes floating-point numbers. One advice (not changing the outcome here) is to add dtype=np.float64 to the calls to np.array to make sure all numbers are treated as floating point scalars.

To go further, I'd recommend you dig into what the function is doing, that is, taking the code out and managing the pycddlib objects directly. For instance rather you can try another number type:

pypoman/pypoman/duality.py

Line 137 in e22a7a7

mat = cdd.Matrix(np.hstack([b, -A]), number_type="float")

I don't know whether that's the case but it may also be possible to get more verbose outputs from cdd to see why it returns no generator.

Hoping this helps!

[paulpacaud]

Thank you for your reply. Picking up on what you said, to enumerate vertices of a polytope, what's the difference between compute_polytope_vertices from pypoman and poly.get_generators() from pycddlib ?

[stephane-caron]

compute_polytope_vertices is an application of the more general get_generators() from cdd, where we further assume that the output is a polytope (get_generators works with general polyhedra, which can have both rays and vertices).