MIP 与 CP 的调度问题
MIP vs CP for scheduling problems
众所周知，诸如 MILP 之类的精确数学策略对于灵活作业车间问题的大型实例而言效率不高。然而，现在仍然可以找到针对 FJS 问题的 MILP 公式的建议。这可能是因为将 MILP 模型用于涉及非精确方法作为元启发式（GA、FA、TS 等）的实验很有趣，因为它提供了下界。
我还读到，当找到可行解比最优解更重要时，应该选择 CP。这是真的吗？
你说的差不多吧
对于某些类型的问题，很难构建一个有效的 MILP 模型来解决它们，最好用元启发式方法来解决它们。但是，如果 LP 的构建方式可以为问题提供紧密且 non-trivial 的约束，那么就可以验证良好的元启发式的解决方案是否达到最优或 near-optimality。这意味着您可以（可能）仅使用线性规划和元启发式方法将某些类型的 NP 问题的某些实例求解到最优。
对于CP来说，它非常擅长发现一个问题是否可行（或者证明它不可行）。 CP 可以用于寻找最优解，但这不是它的强项，MILP通常在这方面做得更好。
I also read that CP should be chosen when finding a feasible solution is more important than an optimal solution. This is true?
我觉得随着最近CP的进步，这种说法越来越不成立了。特别是对于调度问题。例如，您提到了灵活的 job-shop 调度问题。在这个问题上，通用 CP 技术用于改进和关闭经典基准测试的许多开放实例（通过找到更好的解决方案和找到更严格的下限）。参见例如 [1]。在本文中，相同的 CP 技术用于 improve/close 许多其他经典调度问题（特别是 job-shop 和 RCPSP 的几个变体）。
而且，是的，CP 可以提供一些下限。如果加上约束“objective < K”，并且搜索证明这个问题不可行，那么 K 就是一个下界。还需要注意的是，一些现代 CP 求解器使用线性松弛来指导搜索并提供一些下限。
您还可以查看 [2]，比较针对大量研究的 job-shop 调度问题的几种 MIP 模型和 CP 模型的性能。
如果您有兴趣更全面地了解如何将不同的 CP 技术集成到通用 CP-based 优化引擎中，还有这篇最近的文章 [3] (http://ibm.biz/Constraints2018 ).
[1] P. Vilim、P. Laborie、P. Shaw。 “Failure-directed 搜索 Constraint-based 日程安排”。过程。第 12 届 AI 和 OR 技术在组合优化问题约束规划中的集成国际会议, CPAIOR 2015
[2]W-Y。库，C. 贝克。 “作业车间调度的混合整数规划模型：计算分析”。计算机与运筹学。 2016.
[3] P.Laborie、J.Rogerie、P.Shaw、P.Vilim。 “用于调度的 IBM ILOG CP 优化器”。约束期刊，2018
众所周知，诸如 MILP 之类的精确数学策略对于灵活作业车间问题的大型实例而言效率不高。然而，现在仍然可以找到针对 FJS 问题的 MILP 公式的建议。这可能是因为将 MILP 模型用于涉及非精确方法作为元启发式（GA、FA、TS 等）的实验很有趣，因为它提供了下界。
我还读到，当找到可行解比最优解更重要时，应该选择 CP。这是真的吗？
你说的差不多吧
对于某些类型的问题，很难构建一个有效的 MILP 模型来解决它们，最好用元启发式方法来解决它们。但是，如果 LP 的构建方式可以为问题提供紧密且 non-trivial 的约束，那么就可以验证良好的元启发式的解决方案是否达到最优或 near-optimality。这意味着您可以（可能）仅使用线性规划和元启发式方法将某些类型的 NP 问题的某些实例求解到最优。
对于CP来说，它非常擅长发现一个问题是否可行（或者证明它不可行）。 CP 可以用于寻找最优解，但这不是它的强项，MILP通常在这方面做得更好。
I also read that CP should be chosen when finding a feasible solution is more important than an optimal solution. This is true?
我觉得随着最近CP的进步，这种说法越来越不成立了。特别是对于调度问题。例如，您提到了灵活的 job-shop 调度问题。在这个问题上，通用 CP 技术用于改进和关闭经典基准测试的许多开放实例（通过找到更好的解决方案和找到更严格的下限）。参见例如 [1]。在本文中，相同的 CP 技术用于 improve/close 许多其他经典调度问题（特别是 job-shop 和 RCPSP 的几个变体）。
而且，是的，CP 可以提供一些下限。如果加上约束“objective < K”，并且搜索证明这个问题不可行，那么 K 就是一个下界。还需要注意的是，一些现代 CP 求解器使用线性松弛来指导搜索并提供一些下限。
您还可以查看 [2]，比较针对大量研究的 job-shop 调度问题的几种 MIP 模型和 CP 模型的性能。
如果您有兴趣更全面地了解如何将不同的 CP 技术集成到通用 CP-based 优化引擎中，还有这篇最近的文章 [3] (http://ibm.biz/Constraints2018 ).
[1] P. Vilim、P. Laborie、P. Shaw。 “Failure-directed 搜索 Constraint-based 日程安排”。过程。第 12 届 AI 和 OR 技术在组合优化问题约束规划中的集成国际会议, CPAIOR 2015
[2]W-Y。库，C. 贝克。 “作业车间调度的混合整数规划模型：计算分析”。计算机与运筹学。 2016.
[3] P.Laborie、J.Rogerie、P.Shaw、P.Vilim。 “用于调度的 IBM ILOG CP 优化器”。约束期刊，2018