I ran the exact same python notebook twice (using the PULP_CBC_CMD solver that comes with pulp), and I got the results I pasted below.
How can a solution be called 'optimal' if the very same solver with the very same data and code finds a better one on another run?
Any ideas?
Is there any effect of seeding?
For context, the problem I am trying to solve is: take a list of 28 integers, and partition them into 4 sets, such that the sum of integers within each set is as close as possible to the sum of all 28 integers divided by 4.
First run (obj = 0.00000254):
{3: [21614, 1344708, 819, 7109, 1239808, 16028],
1: [22716, 8948, 136944, 925193, 147896, 824564, 72221, 460833, 30955],
2: [255182, 1898763, 108042, 368270],
4: [556354, 173237, 64301, 1021326, 17467, 2953, 52942, 1855, 739627]}
[2630086, 2630270, 2630257, 2630062]
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - /opt/conda/lib/python3.9/site-packages/pulp/solverdir/cbc/linux/64/cbc /tmp/da872918615345b7a86ca39a8b3bc02a-pulp.mps -sec 31536000 -ratio 0 -threads 4 -timeMode elapsed -branch -printingOptions all -solution /tmp/da872918615345b7a86ca39a8b3bc02a-pulp.sol (default strategy 1)
At line 2 NAME MODEL
At line 3 ROWS
At line 41 COLUMNS
At line 614 RHS
At line 651 BOUNDS
At line 764 ENDATA
Problem MODEL has 36 rows, 116 columns and 344 elements
Coin0008I MODEL read with 0 errors
seconds was changed from 1e+100 to 3.1536e+07
ratioGap was changed from 0 to 0
threads was changed from 0 to 4
Option for timeMode changed from cpu to elapsed
Continuous objective value is 0 - 0.00 seconds
Cgl0004I processed model has 36 rows, 113 columns (112 integer (112 of which binary)) and 344 elements
Cbc0038I Initial state - 6 integers unsatisfied sum - 1.04778
Cbc0038I Pass 1: suminf. 0.00000 (0) obj. 0.01798 iterations 15
Cbc0038I Solution found of 0.01798
Cbc0038I Relaxing continuous gives 0.01798
Cbc0038I Before mini branch and bound, 106 integers at bound fixed and 0 continuous
Cbc0038I Full problem 36 rows 113 columns, reduced to 8 rows 4 columns
Cbc0038I Mini branch and bound improved solution from 0.01798 to 0.0171438 (0.02 seconds)
Cbc0038I Round again with cutoff of 0.0154204
Cbc0038I Pass 2: suminf. 0.11345 (2) obj. 0.0154204 iterations 10
Cbc0038I Pass 3: suminf. 0.55654 (2) obj. 0.0154204 iterations 13
Cbc0038I Pass 4: suminf. 0.33529 (2) obj. 0.0154204 iterations 26
Cbc0038I Solution found of 0.0154204
Cbc0038I Relaxing continuous gives 0.0121357
Cbc0038I Before mini branch and bound, 86 integers at bound fixed and 0 continuous
Cbc0038I Full problem 36 rows 113 columns, reduced to 10 rows 17 columns
Cbc0038I Mini branch and bound improved solution from 0.0121357 to 0.00239173 (0.02 seconds)
Cbc0038I Round again with cutoff of 0.00190538
Cbc0038I Pass 5: suminf. 0.72114 (4) obj. 0.00190538 iterations 1
Cbc0038I Pass 6: suminf. 1.59976 (4) obj. 0.00190538 iterations 19
Cbc0038I Pass 7: suminf. 1.44700 (4) obj. 0.00190538 iterations 3
Cbc0038I Pass 8: suminf. 0.87390 (5) obj. 0.00190538 iterations 8
Cbc0038I Pass 9: suminf. 1.08860 (5) obj. 0.00190538 iterations 30
Cbc0038I Pass 10: suminf. 1.08860 (5) obj. 0.00190538 iterations 9
Cbc0038I Pass 11: suminf. 1.75188 (5) obj. 0.00190538 iterations 19
Cbc0038I Pass 12: suminf. 1.09723 (5) obj. 0.00190538 iterations 14
Cbc0038I Pass 13: suminf. 1.74326 (5) obj. 0.00190538 iterations 15
Cbc0038I Pass 14: suminf. 1.57602 (6) obj. 0.00190538 iterations 27
Cbc0038I Pass 15: suminf. 0.97726 (3) obj. 0.00190538 iterations 10
Cbc0038I Pass 16: suminf. 1.31945 (4) obj. 0.00190538 iterations 15
Cbc0038I Pass 17: suminf. 1.00000 (3) obj. 0.00190538 iterations 11
Cbc0038I Pass 18: suminf. 1.00000 (4) obj. 0.00190538 iterations 7
Cbc0038I Pass 19: suminf. 1.00000 (3) obj. 0.00190538 iterations 7
Cbc0038I Pass 20: suminf. 1.50131 (6) obj. 0.00190538 iterations 18
Cbc0038I Pass 21: suminf. 1.28415 (6) obj. 0.00190538 iterations 10
Cbc0038I Pass 22: suminf. 0.89528 (6) obj. 0.00190538 iterations 22
Cbc0038I Pass 23: suminf. 0.80563 (6) obj. 0.00190538 iterations 6
Cbc0038I Pass 24: suminf. 1.91357 (6) obj. 0.00190538 iterations 15
Cbc0038I Pass 25: suminf. 1.48191 (6) obj. 0.00190538 iterations 5
Cbc0038I Pass 26: suminf. 1.02968 (5) obj. 0.00190538 iterations 21
Cbc0038I Pass 27: suminf. 0.79997 (4) obj. 0.00190538 iterations 13
Cbc0038I Pass 28: suminf. 1.26200 (5) obj. 0.00190538 iterations 13
Cbc0038I Pass 29: suminf. 1.24116 (4) obj. 0.00190538 iterations 7
Cbc0038I Pass 30: suminf. 1.02968 (5) obj. 0.00190538 iterations 22
Cbc0038I Pass 31: suminf. 2.26316 (6) obj. 0.00190538 iterations 22
Cbc0038I Pass 32: suminf. 1.00000 (4) obj. 0.00190538 iterations 13
Cbc0038I Pass 33: suminf. 1.00000 (4) obj. 0.00190538 iterations 4
Cbc0038I Pass 34: suminf. 1.00000 (4) obj. 0.00190538 iterations 8
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 55 integers at bound fixed and 0 continuous
Cbc0038I Full problem 36 rows 113 columns, reduced to 17 rows 45 columns
Cbc0038I Mini branch and bound improved solution from 0.00239173 to 0.000440971 (0.05 seconds)
Cbc0038I Round again with cutoff of 0.00030168
Cbc0038I Pass 34: suminf. 0.87645 (5) obj. 0.00030168 iterations 3
Cbc0038I Pass 35: suminf. 1.62905 (5) obj. 0.00030168 iterations 13
Cbc0038I Pass 36: suminf. 1.60230 (5) obj. 0.00030168 iterations 6
Cbc0038I Pass 37: suminf. 0.90319 (5) obj. 0.00030168 iterations 11
Cbc0038I Pass 38: suminf. 1.41443 (5) obj. 0.00030168 iterations 22
Cbc0038I Pass 39: suminf. 1.41443 (5) obj. 0.00030168 iterations 9
Cbc0038I Pass 40: suminf. 1.41968 (5) obj. 0.00030168 iterations 14
Cbc0038I Pass 41: suminf. 1.32352 (5) obj. 0.00030168 iterations 9
Cbc0038I Pass 42: suminf. 1.29678 (5) obj. 0.00030168 iterations 3
Cbc0038I Pass 43: suminf. 1.89067 (5) obj. 0.00030168 iterations 14
Cbc0038I Pass 44: suminf. 1.86393 (5) obj. 0.00030168 iterations 6
Cbc0038I Pass 45: suminf. 1.32352 (5) obj. 0.00030168 iterations 14
Cbc0038I Pass 46: suminf. 2.09959 (6) obj. 0.00030168 iterations 23
Cbc0038I Pass 47: suminf. 1.53810 (5) obj. 0.00030168 iterations 6
Cbc0038I Pass 48: suminf. 0.97696 (5) obj. 0.00030168 iterations 13
Cbc0038I Pass 49: suminf. 1.50406 (5) obj. 0.00030168 iterations 14
Cbc0038I Pass 50: suminf. 0.90055 (4) obj. 0.00030168 iterations 23
Cbc0038I Pass 51: suminf. 0.90055 (4) obj. 0.00030168 iterations 8
Cbc0038I Pass 52: suminf. 0.92729 (4) obj. 0.00030168 iterations 15
Cbc0038I Pass 53: suminf. 1.66723 (5) obj. 0.00030168 iterations 21
Cbc0038I Pass 54: suminf. 1.10337 (5) obj. 0.00030168 iterations 12
Cbc0038I Pass 55: suminf. 1.77263 (5) obj. 0.00030168 iterations 20
Cbc0038I Pass 56: suminf. 1.23211 (5) obj. 0.00030168 iterations 12
Cbc0038I Pass 57: suminf. 1.25885 (5) obj. 0.00030168 iterations 13
Cbc0038I Pass 58: suminf. 1.66527 (6) obj. 0.00030168 iterations 24
Cbc0038I Pass 59: suminf. 1.00000 (4) obj. 0.00030168 iterations 14
Cbc0038I Pass 60: suminf. 1.00000 (4) obj. 0.00030168 iterations 4
Cbc0038I Pass 61: suminf. 1.00000 (4) obj. 0.00030168 iterations 10
Cbc0038I Pass 62: suminf. 1.72469 (6) obj. 0.00030168 iterations 31
Cbc0038I Pass 63: suminf. 0.71967 (6) obj. 0.00030168 iterations 13
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 35 integers at bound fixed and 0 continuous
Cbc0038I Full problem 36 rows 113 columns, reduced to 25 rows 68 columns
Cbc0038I Mini branch and bound improved solution from 0.000440971 to 7.02486e-05 (0.09 seconds)
Cbc0038I Round again with cutoff of 4.2174e-05
Cbc0038I Pass 63: suminf. 0.90419 (5) obj. 4.2174e-05 iterations 0
Cbc0038I Pass 64: suminf. 1.63379 (5) obj. 4.2174e-05 iterations 13
Cbc0038I Pass 65: suminf. 1.63005 (5) obj. 4.2174e-05 iterations 6
Cbc0038I Pass 66: suminf. 0.90793 (5) obj. 4.2174e-05 iterations 11
Cbc0038I Pass 67: suminf. 0.97496 (5) obj. 4.2174e-05 iterations 21
Cbc0038I Pass 68: suminf. 0.89601 (4) obj. 4.2174e-05 iterations 9
Cbc0038I Pass 69: suminf. 0.89975 (4) obj. 4.2174e-05 iterations 15
Cbc0038I Pass 70: suminf. 1.03907 (5) obj. 4.2174e-05 iterations 26
Cbc0038I Pass 71: suminf. 1.03907 (5) obj. 4.2174e-05 iterations 8
Cbc0038I Pass 72: suminf. 1.61501 (5) obj. 4.2174e-05 iterations 16
Cbc0038I Pass 73: suminf. 1.41908 (5) obj. 4.2174e-05 iterations 17
Cbc0038I Pass 74: suminf. 0.76351 (5) obj. 4.2174e-05 iterations 14
Cbc0038I Pass 75: suminf. 1.22855 (5) obj. 4.2174e-05 iterations 21
Cbc0038I Pass 76: suminf. 0.90127 (4) obj. 4.2174e-05 iterations 21
Cbc0038I Pass 77: suminf. 0.90127 (4) obj. 4.2174e-05 iterations 6
Cbc0038I Pass 78: suminf. 0.90500 (4) obj. 4.2174e-05 iterations 16
Cbc0038I Pass 79: suminf. 0.53118 (6) obj. 4.2174e-05 iterations 34
Cbc0038I Pass 80: suminf. 0.52725 (6) obj. 4.2174e-05 iterations 9
Cbc0038I Pass 81: suminf. 1.78668 (6) obj. 4.2174e-05 iterations 19
Cbc0038I Pass 82: suminf. 1.13994 (6) obj. 4.2174e-05 iterations 6
Cbc0038I Pass 83: suminf. 1.45437 (6) obj. 4.2174e-05 iterations 17
Cbc0038I Pass 84: suminf. 0.93890 (6) obj. 4.2174e-05 iterations 6
Cbc0038I Pass 85: suminf. 1.54792 (6) obj. 4.2174e-05 iterations 15
Cbc0038I Pass 86: suminf. 0.98065 (5) obj. 4.2174e-05 iterations 7
Cbc0038I Pass 87: suminf. 1.12437 (5) obj. 4.2174e-05 iterations 21
Cbc0038I Pass 88: suminf. 0.98065 (5) obj. 4.2174e-05 iterations 18
Cbc0038I Pass 89: suminf. 0.39122 (6) obj. 4.2174e-05 iterations 25
Cbc0038I Pass 90: suminf. 0.38968 (6) obj. 4.2174e-05 iterations 14
Cbc0038I Pass 91: suminf. 1.61655 (6) obj. 4.2174e-05 iterations 19
Cbc0038I Pass 92: suminf. 1.02006 (5) obj. 4.2174e-05 iterations 15
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 42 integers at bound fixed and 0 continuous
Cbc0038I Full problem 36 rows 113 columns, reduced to 23 rows 62 columns
Cbc0038I Mini branch and bound did not improve solution (0.13 seconds)
Cbc0038I After 0.13 seconds - Feasibility pump exiting with objective of 7.02486e-05 - took 0.11 seconds
Cbc0012I Integer solution of 7.0248582e-05 found by feasibility pump after 0 iterations and 0 nodes (0.13 seconds)
Cbc0038I Full problem 36 rows 113 columns, reduced to 8 rows 15 columns
Cbc0031I 19 added rows had average density of 42.842105
Cbc0013I At root node, 19 cuts changed objective from 0 to 0 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 24 row cuts average 7.2 elements, 0 column cuts (0 active) in 0.022 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 880 row cuts average 105.3 elements, 0 column cuts (0 active) in 0.034 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.006 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.002 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 899 row cuts average 22.0 elements, 0 column cuts (0 active) in 0.047 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.012 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 342 row cuts average 28.0 elements, 0 column cuts (0 active) in 0.006 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 7.0248582e-05 best solution, best possible 0 (0.47 seconds)
Cbc0012I Integer solution of 3.6042127e-05 found by heuristic after 5499 iterations and 162 nodes (0.64 seconds)
Cbc0012I Integer solution of 2.5836032e-05 found by heuristic after 5558 iterations and 169 nodes (0.64 seconds)
Cbc0012I Integer solution of 2.5366718e-06 found by heuristic after 5716 iterations and 176 nodes (0.64 seconds)
Cbc0030I Thread 0 used 45 times, waiting to start 0.036746502, 250 locks, 0.00067687035 locked, 0.00014829636 waiting for locks
Cbc0030I Thread 1 used 50 times, waiting to start 0.027021646, 265 locks, 0.00063514709 locked, 0.00019264221 waiting for locks
Cbc0030I Thread 2 used 40 times, waiting to start 0.018216848, 215 locks, 0.00056695938 locked, 8.0823898e-05 waiting for locks
Cbc0030I Thread 3 used 45 times, waiting to start 0.083312035, 233 locks, 0.00053620338 locked, 6.1988831e-05 waiting for locks
Cbc0030I Main thread 0.16802382 waiting for threads, 370 locks, 0.00051784515 locked, 0.0001745224 waiting for locks
Cbc0001I Search completed - best objective 2.536671837402582e-06, took 5750 iterations and 180 nodes (0.74 seconds)
Cbc0032I Strong branching done 1998 times (11447 iterations), fathomed 10 nodes and fixed 111 variables
Cbc0035I Maximum depth 22, 37 variables fixed on reduced cost
Cuts at root node changed objective from 0 to 0
Probing was tried 500 times and created 120 cuts of which 0 were active after adding rounds of cuts (0.109 seconds)
Gomory was tried 500 times and created 4400 cuts of which 0 were active after adding rounds of cuts (0.172 seconds)
Knapsack was tried 500 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.032 seconds)
Clique was tried 500 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.009 seconds)
MixedIntegerRounding2 was tried 500 times and created 4495 cuts of which 0 were active after adding rounds of cuts (0.234 seconds)
FlowCover was tried 500 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.060 seconds)
TwoMirCuts was tried 500 times and created 1710 cuts of which 0 were active after adding rounds of cuts (0.029 seconds)
ZeroHalf was tried 5 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ImplicationCuts was tried 19 times and created 12 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: 0.00000254
Enumerated nodes: 180
Total iterations: 5750
Time (CPU seconds): 0.69
Time (Wallclock seconds): 0.75
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.69 (Wallclock seconds): 0.76
Part 2 with the other solution posted as an answer due to the 30 K character limitation of individual posts.
EDIT: Actually, part 2 was deleted by admins. So this question is incomplete; sorry, I did provide all the required information but it was censored.
A couple ideas...
First, for both of your solutions, the reported optimal value is less than 1e-5 epsilon from bound on the solution, which is zero as reported in the solver output (about the 10th line "Continuous solution 0 ...")
To my knowledge, most solvers have tolerances for zeros, numerical error, optimality, etc. around 1e-5 (ish). So, from the solver's perspective, these 2 solutions are the same. It has not "found a better one" on a different run. It has arrived at the same optimal value.
So then part 2 of the question is "why is this not reproducible?" There is not enough of your code posted to fully answer that. As pointed out in the comments, multi-threading is certainly suspect and you can easily change the params in CBC to force single threaded approach. It is also possible that you constructed the data in a non deterministic way using unordered collections, python objects, etc. but that doesn't seem likely from your problem description.