0

考虑 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 提供的解决方案是否准确？

编辑

根据下面 Erwin Kalvelagen 的回答，对于这个特定问题，CBC 解决方案应该是最佳的。但是，我在后续的可疑行为中运行。

我认为 c_is 是 N 个 IID 随机变量，均匀分布在 0 和 1 之间。对于小 N，从定性上讲，解决方案看起来像 0 和 1 的随机序列：x = {0,1,0,0,... ., 1,0,1}。随着 N 的增加 (N >~ 100)，解的最后一个 bin 都设置为零：x = {0,1,0,0,1,...., 0,0,0,0,0 ,0,0}。这对我来说看起来很可疑，因为对于这个问题，没有什么能以如此突然的方式破坏最小值的对称性（参见上面的 c_i 定义）。我正在使用 此代码，它是CBC 用户指南中 minimum.cpp 的副本，问题存储在 此 mps 文件中。输出将最后的 ~ 40 个变量设置为零：

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

正如 Erwin Kalvelagen 所指出的，我怀疑问题是否与公差有关。

你知道解决这个问题的方法吗？

4

1 回答 1

2

不是那么简单的问题。

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

更新后获得更多信息。因此，让我们尝试使用 CBC.exe 的 MPS 文件。我认为是解决方案（最后一部分）：

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 似乎是正确的，我们最后没有全为零。显然，我无法重现您的问题。

于 2019-03-07T12:01:18.643 回答