线性规划求解器CBC似乎对相同问题（及代码）给出不同目标的“最优”解
我运行了完全相同的Python笔记本两次（使用的是PULP_CBC_CMD这个求解器，它是pulp自带的），结果如下。
如果同一个求解器用同样的数据和代码在另一次运行中找到了更好的结果，那怎么能说这个解决方案是“最优”的呢？
有没有什么想法？
这是否和随机种子有关？
为了让大家明白，我想解决的问题是：拿一组28个整数，把它们分成4个集合，使得每个集合内的整数和尽可能接近28个整数总和除以4的结果。
第一次运行的结果（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
由于单个帖子有30K字符的限制，第二部分的其他解决方案作为回答发布。
编辑：实际上，第二部分被管理员删除了。所以这个问题不完整；抱歉，我确实提供了所有必要的信息，但它被审查了。
2 个回答
1
你在使用CBC求解器解决同一个问题时，发现“最佳”解的变化，这种情况在混合整数线性规划（MILP）求解器中是很常见的。这种现象可以归因于几个与MILP求解器的特性和计算环境相关的因素。以下是一些关键点：
数值精度：MILP求解器使用浮点运算，这可能会引入一些小的数值误差。这些误差可能导致求解器在不同的运行中以不同的方式探索解空间，尤其是在处理紧约束或目标值相近的情况下。
启发式和搜索策略：CBC和其他求解器使用多种启发式方法来指导寻找最佳解的过程。这些启发式方法的决策可能会因为求解器状态或输入的微小变化而有所不同，从而导致探索不同的解路径。
多线程影响：在多线程模式下运行时，线程之间的相互作用可能会影响求解器的行为。线程执行顺序的不确定性可能导致解空间的探索出现变化，从而影响求解器的输出。
随机化：一些求解器在其启发式算法中引入了随机化。除非明确设置随机种子为相同，否则这可能导致不同的起始点或探索路径，从而产生不同的解。
为了在多次运行中获得更一致的结果，可以考虑以下调整：
- 设置特定的种子：如果求解器支持，指定一个固定的随机种子，以确保在使用随机选择的算法部分中行为是确定的。
- 调整容差：收紧求解器与最优性和可行性相关的容差设置。这可以使求解器对什么是最佳解的判断更加一致。
- 限制为单线程：在单线程模式下运行求解器可以消除多线程带来的变化，虽然可能会导致求解时间变长。
需要注意的是，你遇到的目标值的小差异在MILP解中通常是可以接受和预期的。并不总是需要完全可重复，但如果对你的应用来说这很重要，上述策略可以帮助你获得更一致的结果。
1
有几个想法...
首先，对于你提到的两个解决方案，报告的最佳值距离解决方案的界限（也就是零）小于1e-5，这个信息在求解器的输出中可以看到（大约在第十行“连续解 0 ...”）。
据我所知，大多数求解器对零、数值误差、最优性等都有大约1e-5的容忍度。所以，从求解器的角度来看，这两个解决方案实际上是一样的。它并没有在其他运行中“找到更好的解”，而是达到了相同的最佳值。
那么问题的第二部分是“为什么这个结果不可重复？”你提供的代码不够完整，无法完全回答这个问题。正如评论中提到的，多线程处理确实值得怀疑，你可以很容易地在CBC中更改参数，强制使用单线程的方法。此外，你可能是以一种非确定性的方式构建数据，比如使用无序集合、Python对象等，但从你的问题描述来看，这种可能性似乎不大。