It is known that exact mathematical strategies such MILP are not efficient for large instances of the flexible job shop problem. However, still, nowadays it is possible to find proposals of MILP formulations for the FJS problem. It may be due to the fact 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 bounds.
I also read that CP should be chosen when finding a feasible solution is more important than an optimal solution. Is that a true statement?
I also read that CP should be chosen when finding a feasible solution is more important than an optimal solution. This is true?
I think that this statement is becoming less and less true with the recent progress of CP. Especially for scheduling problems. For instance you mention the flexible job-shop scheduling problem. On this problem, generic CP techniques were used to improve and close many of the open instances of the classical benchmarks (both by finding better solutions and by finding tighter lower bounds). See for instance [1]. In this article, the same CP techniques are used to improve/close many other classical scheduling problems (in particular several variants of job-shop and 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. “Failure-directed Search for Constraint-based Scheduling”. Proc. 12th International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2015
[2] W-Y. Ku, C. Beck. “Mixed Integer Programming Models for Job Shop Scheduling: a Computational Analysis”. Computers & Operations Research. 2016.
[3] P. Laborie, J. Rogerie, P. Shaw, P. Vilim . “IBM ILOG CP Optimizer for Scheduling”. Constraints journal, 2018