Is the solution returned by the CBC solver exact?

Question

Consider an integer optimization problem for N variables

min_x [sum_i c_i x_i ]

with constraint

sum_i c_i x_i >= C,

where C = sum_i c_i/2 and x_i = {0,1}.

If, after the optimization, model.isProvenOptimal() returns 1, is the solution provided by CBC exact?

Edit

According Erwin Kalvelagen's answrt below, for this specific problem the CBC solution should be optimal. However, I run in the follownig, suspicious behavior.

I took the c_is to be N IID random variables uniformly distributed between 0 and 1. For small N the solution looks, qualitatively speaking, like a random sequence of 0 and 1: x = {0,1,0,0,...., 1,0,1}. As N is increased (N >~ 100), the last bins of the solution are all set to zero: x = {0,1,0,0,1,...., 0,0,0,0,0,0,0}. This looks very suspicious to me, because for this problem there is nothing that breaks the symmetry of the minimum in such an abrupt way (see the definition above for c_i). I am using this code, which is a copy of minimum.cpp from the CBC User Guide, and the problem is stored in this mps file. The output is has the last ~ 40 variables set to zero:

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

I suspect whether the problem may be related to tolerances, as pointed out by Erwin Kalvelagen.

Do you know a way around this issue?

Answer 1

Not such as easy question.

The branch-and-bound method of CBC guarantees there is a no better integer solution. So the "proven optimal" claim is correct.

However there are many numerical issues: the MIP solver and underlying LP solver is using a lot of tolerances. This means a reported solution is not 100% correct: it may be a tiny little bit infeasible. This is to be expected when using standard floating point arithmetic. For most models this is not an issue in practice, but sometimes we see models with extremely large big-M constants that just give bad results. In addition, you can see binary variables assuming values like 0.99999 or 1.000001. To make things worse: rounding the final solution may make the solution infeasible.

Your model seems to be a binary knapsack model. They are typically very well behaved and unless the constants are not reasonable, I would trust the CBC solution and its claim that it is a proven optimal solution.

My test:

----     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

UPDATE after more information. So let's try the MPS file with CBC.exe. I see as solution (last part):

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

So CBC seems correct, we don't have all zeroes at the end. Obviously, I can't reproduce your problem.