This question doesn't really have a definitive answer, but here it goes:

CP will probably work well when: your problem has substructures that can be represented/captured by global constraints; the constraints propagate well (i.e. filtering algorithm is strong; problem dependent); your knowledge about the problem allows you to write an intelligent and effective search heuristic (both variable and value selection). Also, practical applications in which it is difficult to find a feasible solution have benefited from the use of CP (e.g. award winning Dutch railway scheduling, MLB scheduling).

As "anonymous" points out, when the linear relaxation of a MIP is tight, one can expect good results. The addition of strong cutting planes and the existence of good primal heuristics also play an important role. Another reason one might try CP rather than MIP could be because the problem has "ugly" constraints that would be very hard to model using only linear inequalities.

In many cases, however, one needs to try both in order to find out which one works better. That being said, there are situations in which neither MIP nor CP provide good results. In those cases, one may consider combining them into a hybrid algorithm. But that is a different story...

I would suggest trying both and see what works. Usually, MILP formulations for which the LP relaxation is weak tend to be more difficult to solve (For instance, number partitioning, graph coloring ...). So, if you find the lower bound from your MILP formulation not moving at all, it may be a good idea to try a different MILP formulation or try CP. Disclaimer: I don't have much experience with constraint programming.

Hi, does any one know a good ...?