Что инструменты там для разрезания PSD? [закрытый]

Не такой простой вопрос.

Метод ветвей и границ CBC гарантирует, что лучшего целочисленного решения не существует. Таким образом, «доказанное оптимальное» утверждение верно.

Однако есть много численных проблем: решатель MIP и базовый решатель LP используют много допусков. Это означает, что заявленное решение не является на 100% правильным: оно может быть немного недостижимым. Этого следует ожидать при использовании стандартной арифметики с плавающей запятой. Для большинства моделей это не проблема на практике, но иногда мы видим модели с очень большими константами big-M, которые просто дают плохие результаты. Кроме того, вы можете увидеть двоичные переменные, принимающие значения, такие как 0,99999 или 1,000001. Что еще хуже: округление окончательного решения может сделать решение неосуществимым.

Ваша модель выглядит как бинарная модель ранца. Как правило, они ведут себя очень хорошо, и если константы не являются разумными, я бы доверял решению CBC и его утверждению, что это проверенное оптимальное решение.

Мой тест:

----     11 PARAMETER a  

i1   0.172,    i2   0.843,    i3   0.550,    i4   0.301,    i5   0.292,    i6   0.224,    i7   0.350,    i8   0.856
i9   0.067,    i10  0.500,    i11  0.998,    i12  0.579,    i13  0.991,    i14  0.762,    i15  0.131,    i16  0.640
i17  0.160,    i18  0.250,    i19  0.669,    i20  0.435,    i21  0.360,    i22  0.351,    i23  0.131,    i24  0.150
i25  0.589,    i26  0.831,    i27  0.231,    i28  0.666,    i29  0.776,    i30  0.304,    i31  0.110,    i32  0.502
i33  0.160,    i34  0.872,    i35  0.265,    i36  0.286,    i37  0.594,    i38  0.723,    i39  0.628,    i40  0.464
i41  0.413,    i42  0.118,    i43  0.314,    i44  0.047,    i45  0.339,    i46  0.182,    i47  0.646,    i48  0.561
i49  0.770,    i50  0.298,    i51  0.661,    i52  0.756,    i53  0.627,    i54  0.284,    i55  0.086,    i56  0.103
i57  0.641,    i58  0.545,    i59  0.032,    i60  0.792,    i61  0.073,    i62  0.176,    i63  0.526,    i64  0.750
i65  0.178,    i66  0.034,    i67  0.585,    i68  0.621,    i69  0.389,    i70  0.359,    i71  0.243,    i72  0.246
i73  0.131,    i74  0.933,    i75  0.380,    i76  0.783,    i77  0.300,    i78  0.125,    i79  0.749,    i80  0.069
i81  0.202,    i82  0.005,    i83  0.270,    i84  0.500,    i85  0.151,    i86  0.174,    i87  0.331,    i88  0.317
i89  0.322,    i90  0.964,    i91  0.994,    i92  0.370,    i93  0.373,    i94  0.772,    i95  0.397,    i96  0.913
i97  0.120,    i98  0.735,    i99  0.055,    i100 0.576


----     11 PARAMETER c  

i1   0.051,    i2   0.006,    i3   0.401,    i4   0.520,    i5   0.629,    i6   0.226,    i7   0.396,    i8   0.276
i9   0.152,    i10  0.936,    i11  0.423,    i12  0.135,    i13  0.386,    i14  0.375,    i15  0.268,    i16  0.948
i17  0.189,    i18  0.298,    i19  0.075,    i20  0.401,    i21  0.102,    i22  0.384,    i23  0.324,    i24  0.192
i25  0.112,    i26  0.597,    i27  0.511,    i28  0.045,    i29  0.783,    i30  0.946,    i31  0.596,    i32  0.607
i33  0.363,    i34  0.594,    i35  0.680,    i36  0.507,    i37  0.159,    i38  0.657,    i39  0.524,    i40  0.124
i41  0.987,    i42  0.228,    i43  0.676,    i44  0.777,    i45  0.932,    i46  0.201,    i47  0.297,    i48  0.197
i49  0.246,    i50  0.646,    i51  0.735,    i52  0.085,    i53  0.150,    i54  0.434,    i55  0.187,    i56  0.693
i57  0.763,    i58  0.155,    i59  0.389,    i60  0.695,    i61  0.846,    i62  0.613,    i63  0.976,    i64  0.027
i65  0.187,    i66  0.087,    i67  0.540,    i68  0.127,    i69  0.734,    i70  0.113,    i71  0.488,    i72  0.796
i73  0.492,    i74  0.534,    i75  0.011,    i76  0.544,    i77  0.451,    i78  0.975,    i79  0.184,    i80  0.164
i81  0.025,    i82  0.178,    i83  0.061,    i84  0.017,    i85  0.836,    i86  0.602,    i87  0.027,    i88  0.196
i89  0.951,    i90  0.336,    i91  0.594,    i92  0.259,    i93  0.641,    i94  0.155,    i95  0.460,    i96  0.393
i97  0.805,    i98  0.541,    i99  0.391,    i100 0.558


----     11 PARAMETER b                    =       10.000  

----     27 Cplex solution

----     27 VARIABLE x.L  

i1  1.000,    i2  1.000,    i12 1.000,    i19 1.000,    i25 1.000,    i28 1.000,    i52 1.000,    i53 1.000
i58 1.000,    i64 1.000,    i68 1.000,    i75 1.000,    i79 1.000,    i81 1.000,    i83 1.000,    i84 1.000
i87 1.000,    i94 1.000


----     27 VARIABLE z.L                   =        1.448  objective

----     31 CBC solution

----     31 VARIABLE x.L  

i1  1.000,    i2  1.000,    i12 1.000,    i19 1.000,    i25 1.000,    i28 1.000,    i52 1.000,    i53 1.000
i58 1.000,    i64 1.000,    i68 1.000,    i75 1.000,    i79 1.000,    i81 1.000,    i83 1.000,    i84 1.000
i87 1.000,    i94 1.000


----     31 VARIABLE z.L                   =        1.448  objective

ОБНОВЛЕНИЕ после получения дополнительной информации. Итак, давайте попробуем файл MPS с CBC.exe. Я вижу решение (последняя часть):

156 col157                              1              0.85936307
161 col162                              1               0.7537911
162 col163                              1              0.35518931
163 col164                              1             0.064355017
173 col174                              1              0.90182764
188 col189                              1              0.16457875
197 col198                              1             0.075497185

Таким образом, CBC кажется правильным, у нас нет всех нулей в конце. Очевидно, я не могу воспроизвести вашу проблему.