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.
> 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.
RépondreSupprimerI think you should not worry. If you are interested in what happens in OR, you already know that CP is definetely part of the interesting stuff. I mainly do LP, never tried CP, and I still read your blog :)
I think the last edition of that book is 1999. This might be seen best as a sign of how poor the understanding was 13 years ago. I think it is much better now!
RépondreSupprimerThank you Mike, you are probably right. CP was still very young at that time (and it still is compared to math programming). It's true that the period of 95-05 was very rich for CP.
RépondreSupprimerI agree with the above comments. I'd like to add that I come "from the OR side" and I "discovered" the existance of CP only because of Williams' book (we are talking aroun 2000). And you will be surprised to learn that it made me want to learn more about CP! It would be nice if there were more publications making the link (and you mgiht want to have a look at Prof Williams web page: http://personal.lse.ac.uk/williahp/pub_general.htm). Actually, if someone has any link...
RépondreSupprimer