Точное ли решение, возвращаемое CBC-решателем? - PullRequest
Новая
       43

Точное ли решение, возвращаемое CBC-решателем?

0 голосов
/ 05 марта 2019

Рассмотрим целочисленную задачу оптимизации для N переменных

min_x [sum_i c_i x_i]

с ограничением

sum_i c_i x_i> = C,

, где C = sum_i c_i / 2 и x_i = {0,1}.

Если после оптимизации model.isProvenOptimal () возвращает 1, является ли решение, предоставленное CBC точным ?

Редактировать

Согласно ответу Эрвина Кальвелагена, приведенному ниже, для этой конкретной проблемы решение CBC должно быть оптимальным. Тем не менее, я бегу в подозрительном поведении.

Я взял c_is как N IID случайных величин, равномерно распределенных между 0 и 1. Для малых N решение выглядит, качественно говоря, как случайная последовательность 0 и 1: x = {0,1,0,0, ...., 1,0,1}. При увеличении N (N> ~ 100) все последние ячейки решения обнуляются: x = {0,1,0,0,1, ...., 0,0,0,0,0 , 0,0}. Это выглядит очень подозрительно для меня, потому что для этой проблемы нет ничего, что нарушает симметрию минимума таким резким способом (см. Определение выше для c_i). Я использую этот код , который является копией Minimum.cpp из Руководства пользователя CBC , и проблема сохраняется в этом файле mps . Выход имеет последние ~ 40 переменных, установленных на ноль: 

x[160] = 0
x[161] = 1
x[162] = 0
x[162] = 0
...
x[198] = 0
x[199] = 0

Я подозреваю, может ли проблема быть связана с допусками, как отметил Эрвин Кальвелаген.

Знаете ли вы, как обойти эту проблему?

1 Ответ

2 голосов
/ 07 марта 2019

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

Метод ветвей и границ 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 кажется правильным, у нас нет всех нулей в конце. Очевидно, я не могу воспроизвести вашу проблему.

...