Wil*_*aba 2 mathematical-optimization linear-programming constraint-programming mixed-integer-programming
It is known that exact mathematical strategies such MILP are not efficient for large instances of the flexible job shop problem.
It is common to see in the literature MILP formulations for the FJS problem. I read that it is interesting to use the MILP model for experiments involving non-exact methods as metaheuristics (GA, FA, TS, etc) since it provides lower and upper bounds.
我还读到，当找到可行的解决方案比最优解决方案更重要时，应该选择CP。这是真实的说法吗？
小智 5
我还读到，当找到可行的解决方案比最优解决方案更重要时，应该选择CP。这是真的？
我认为随着CP的最新进展，这种说法变得越来越不正确。特别是对于计划问题。例如，您提到了灵活的车间调度问题。在此问题上，使用了通用CP技术来改善和关闭许多经典基准测试的开放实例（通过找到更好的解决方案和找到更严格的下限）。参见例如[1]。在本文中，使用相同的CP技术来改善/关闭许多其他经典的调度问题（尤其是Job-shop和RCPSP的几种变体）。
And, yes, CP can provide some lower bounds. If you add the constraint “objective < K” and the search proves this problem is infeasible, then K is a lower bound. It is also to be noted that some modern CP solvers use linear relaxations to guide the search and provide some lower bounds.
You can also have a look at [2] for a comparison of the performance of several MIP models and a CP model for the massively studied job-shop scheduling problem.
And if you are interested in a more complete view of how different CP techniques can be integrated in a generic CP-based optimization engine, there is also this very recent article [3] (http://ibm.biz/Constraints2018).
[1] P. Vilim，P。Laborie和P.Shaw。“基于约束的计划的故障定向搜索”。进程 关于组合优化问题的约束编程中的AI和OR技术集成的第十二届国际会议，CPAIOR，2015年
[2] WY。Ku，C. Beck。“用于车间调度的混合整数编程模型：计算分析”。计算机与运筹学。2016。
[3] P. Laborie，J。Rogerie，P。Shaw，P。Vilim。“用于调度的IBM ILOG CP Optimizer”。约束期刊，2018年