Main Content

调整整数线性规划

改变遗留选项以改进求解过程

注意

通常，您可以更改 MILP 的表示以使其更易于求解。有关如何更改表示的建议，请参阅 Williams [1]。

运行 'legacy' intlinprog 算法一次后，您可能需要更改一些选项并重新运行它。您可能希望看到的变化包括：

  • 运行时间更短

  • 较低的最终目标函数值（更好的解）

  • 最终间隙较小

  • 更多或不同的可行点

以下是最有可能有助于解过程的选项变更的一般建议。按以下顺序尝试这些建议：

  1. 为了获得更快更准确的解，请将 CutMaxIterations 选项从默认的 10 增加到更高的数字，例如 25。这可以加快解的速度，但也可能减慢求解问题的速度。

  2. 为了获得更快、更准确的解，请将 CutGeneration 选项更改为 'intermediate' 或 'advanced'。这可以加快解的速度，但会占用更多的内存，并会使解的速度变慢。

  3. 为了获得更快、更准确的解，请将 IntegerPreprocess 选项更改为 'advanced'。这会对解过程产生很大的影响，无论有益还是有害。

  4. 为了获得更快、更准确的解，请将 RootLPAlgorithm 选项更改为 'primal-simplex'。通常这种变化是没有好处的，但偶尔也会有好处。

  5. 为了尝试找到更多或更好的可行点，请将 HeuristicsMaxNodes 选项从其默认的 50 增加到更高的数字，例如 100。

  6. 为了尝试找到更多或更好的可行点，请将 Heuristics 选项更改为 'intermediate' 或 'advanced'。

  7. 为了尝试找到更多或更好的可行点，请将 BranchRule 选项更改为 'strongpscost' ，或者，如果该选择无法改善解，则更改为 'maxpscost'。

  8. 为了更快地解，请将 ObjectiveImprovementThreshold 选项从其默认值零增加为正值，例如 1e-4。然而，这种变化可能导致 intlinprog 找到更少的整数可行点或不太准确的解。

  9. 为了尝试更快地停止求解器，请将 RelativeGapTolerance 选项更改为比默认 1e-4 更高的值。类似地，为了尝试获得更准确的答案，请将 RelativeGapTolerance 选项更改为较低的值。这些改变并不总能改善结果。

有些“整数”解不是整数

通常，解 x(intcon) 中一些假定为整数值的分量并不是精确的整数。 intlinprog 将整数 IntegerTolerance 范围内的所有解值视为整数。

要将所有假定整数四舍五入为精确整数，请使用 round 函数。

x(intcon) = round(x(intcon));

小心

四舍五入可能会导致解变得不可行。舍入后检查可行性：

max(A*x - b) % see if entries are not too positive, so have small infeasibility
max(abs(Aeq*x - beq)) % see if entries are near enough to zero
max(x - ub) % positive entries are violated bounds
max(lb - x) % positive entries are violated bounds

大型分量不是整数值

当解分量的绝对值超过 2.1e9 时， intlinprog 并不强制要求其值为整数。当您的解包含此种分量时，intlinprog 会发出警告。如果您收到此警告，请检查该解，确认该解中应为整数值的分量是否接近整数。

不允许使用较大的系数

intlinprog 不允许问题的分量（例如 f 或 ub 中的系数）的绝对值超过 1e20（对于 "legacy" 算法则为 1e25），或者 A 或 Aeq 的分量的绝对值超过 1e15。如果您尝试对这样的问题运行 intlinprog，intlinprog 会出错。

如果出现此错误，有时您可以扩展问题以获得较小的系数：

  • 对于 f 中过大的系数，尝试将 f 乘以一个小的缩放因子。

  • 对于过大的约束系数，尝试将所有边界和约束矩阵乘以相同的小缩放因子。

参考

[1] Williams, H. Paul. Model Building in Mathematical Programming, 5th Edition. Wiley, 2013.