I just found a book “Model Building in Mathematical Programming” by H. Paul Williams on the desktop of a colleague. I opened it out of curiosity… One page (page 16 is dedicated to CP). Probably the author wanted to be exhaustive and mention CP but honestly I would prefer he forgot to speak about it ;-)
“The methods used (in CP) are mathematically less sophisticated”
This kind of sentence should be avoided when you speak about a domain that you probably don’t know much especially when two sentences later you explain forward checking for alldiff and forget to mention the matching+scc algorithm of J-C Régin used in every CP Solvers. The author clearly ignores all the mathematical algorithms that are used inside global constraints (just to name a few: Network Flow Constraint, Bounded Knapsack, (soft)-GCC, …). Ok, all the global constraints did not exist at the time of publication of the book but GCC, cost-gcc, already existed.
“CP is mainly useful where a problem has no objective function. It lacks the ability to prove optimality (apart from by complete enumeration).”
Not true of course. B&B has been adapted for CP long time ago. When the variable you want to minimize in the scope of a global constraint you can get very good lower bounds to prune you B&B search tree (see my previous post: yes we can optimize). The author probably ignores that CP is the state of the art exact method to optimize scheduling problems for instance. By the way, I personally find that filtering algorithm for scheduling (edge finding, not-first not-last …) are quite sophisticated ;-)
I have the feeling that this kind of very short review of CP in a well-known OR book can be really disastrous for CP. The reader who reads this and doesn’t know CP yet will surely not try to learn more about it. It this would be very sad because it’s really a fun, interesting and sophisticated approach to solve combinatorial optimization problems. Any way, this book is surely excellent to learn how to build mathematical programming, which it’s main objective.