mathematical-optimization - 调度问题的 MIP 与 CP

Question

众所周知，精确的数学策略（如 MILP）对于灵活作业车间问题的大型实例效率不高。然而，现在仍然可以找到针对 FJS 问题的 MILP 公式的建议。这可能是因为使用 MILP 模型进行涉及非精确方法如元启发式（GA、FA、TS 等）的实验很有趣，因为它提供了下限。

我还读到，当找到可行的解决方案比最佳解决方案更重要时，应该选择 CP。这是一个真实的说法吗？

Answer 1

我还读到，当找到可行的解决方案比最佳解决方案更重要时，应该选择 CP。这是真实的？

我认为随着CP最近的进展，这种说法越来越不真实。特别是对于调度问题。例如，您提到了灵活的作业车间调度问题。在这个问题上，通用 CP 技术被用来改进和关闭许多经典基准测试的开放实例（通过找到更好的解决方案和找到更严格的下限）。参见例如 [1]。在本文中，相同的 CP 技术用于改进/关闭许多其他经典调度问题（特别是作业车间和 RCPSP 的几种变体）。

而且，是的，CP 可以提供一些下限。如果添加约束“objective < K”并且搜索证明这个问题是不可行的，那么 K 是一个下界。还需要注意的是，一些现代 CP 求解器使用线性松弛来指导搜索并提供一些下限。

您还可以查看 [2] 来比较多个 MIP 模型和 CP 模型在大量研究的作业车间调度问题中的性能。

如果您有兴趣更全面地了解如何将不同的 CP 技术集成到通用的基于 CP 的优化引擎中，那么还有这篇最近的文章 [3] ( http://ibm.biz/Constraints2018 )。

[1] P. Vilim、P. Laborie、P. Shaw。“基于约束的调度的故障导向搜索”。过程。第 12 届人工智能和 OR 技术在组合优化问题约束规划中的集成国际会议，CPAIOR 2015

[2] 怀俄明。库，C.贝克。“用于车间调度的混合整数规划模型：计算分析”。计算机与运筹学。2016 年。

[3] P. Laborie、J. Rogerie、P. Shaw、P. Vilim。“用于调度的 IBM ILOG CP 优化器”。约束杂志，2018

Answer 2

你说的是对的。

对于某些类型的问题，很难构建一个有效的 MILP 模型来解决它们，最好通过元启发式来解决它们。但是，如果 LP 可以以某种方式构建，以便为问题提供严格且非平凡的界限，那么就有可能验证一个好的元启发式的解决方案是否达到最优或接近最优。这意味着您可以（可能）仅使用线性规划和元启发式算法将某些类型的 NP 问题的某些实例解决到最优。

至于CP，它非常擅长发现一个问题是否可行（或证明它不可行）。CP可用于找到最佳解决方案，但它不是它的强项，MILP 通常在这方面做得更好。