众所周知，精确的数学方法对于解决柔性作业车间问题的大型实例并不高效 .
在文献中常见的是关于FJS问题的MILP公式 . 我读到有趣的是将MILP模型用于涉及非精确方法的实验作为元启发式（GA，FA，TS等），因为它提供了下限和上限 .
我还读到，当找到可行的解决方案比最优解决方案更重要时，应该选择CP . 这是真实的陈述吗？
我还读到，当找到可行解决方案比最佳解决方案更重要时，应选择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 . “基于约束的调度的失败导向搜索” . PROC . 第12届AI和OR技术在组合优化问题约束规划中的集成国际 Session ，CPAIOR 2015
[2] W-Y . 库，C . 贝克 . “作业车间调度的混合整数规划模型：计算分析” . 计算机与运筹学 . 2016年
[3] P. Laborie，J . Rogerie，P . Shaw，P . Vilim . “IBM ILOG CP Optimizer for Scheduling” . 约束期刊，2018年
你说的是对的 .
对于某些类型的问题，很难构建一个有效的MILP模型来解决它们，并且最好通过元启发式解决它们 . 然而，如果LP可以以对问题提供紧密且非平凡的约束的方式构造，则可以验证良好的元启发式的解是否达到最优性或接近最优性 . 这意味着您可以（可能）仅使用线性编程和元启发式将某些类型的NP问题的某些实例解决为最优 .
至于CP，它非常善于发现问题是否可行（或证明它是不可行的） . CP可以用来找到最佳解决方案，但它并不是它的强项，而MILP通常在这方面做得更好 .
2 回答
我认为，随着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 . “基于约束的调度的失败导向搜索” . PROC . 第12届AI和OR技术在组合优化问题约束规划中的集成国际 Session ，CPAIOR 2015
[2] W-Y . 库，C . 贝克 . “作业车间调度的混合整数规划模型：计算分析” . 计算机与运筹学 . 2016年
[3] P. Laborie，J . Rogerie，P . Shaw，P . Vilim . “IBM ILOG CP Optimizer for Scheduling” . 约束期刊，2018年
你说的是对的 .
对于某些类型的问题，很难构建一个有效的MILP模型来解决它们，并且最好通过元启发式解决它们 . 然而，如果LP可以以对问题提供紧密且非平凡的约束的方式构造，则可以验证良好的元启发式的解是否达到最优性或接近最优性 . 这意味着您可以（可能）仅使用线性编程和元启发式将某些类型的NP问题的某些实例解决为最优 .
至于CP，它非常善于发现问题是否可行（或证明它是不可行的） . CP可以用来找到最佳解决方案，但它并不是它的强项，而MILP通常在这方面做得更好 .