I see that certain studies are comparing MIP and constraint programming (CP) performances. And generally, they claim that CP outperforms MIP. But I believe that it is not completely true. Because while comparing, MIP models don't have LB/UB, symmetry breaking constraints and variable dimensions are accepted from maximum points. In summary, MIP models do not have model performance improvement things. How can MIP models be compared with CP objectively? Are there alternatives to experimental comparison?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ how can even MIP models be compared "objectively"? [a good bound may not translate into fast solving]; for the MIP/CP comparison it may be very problem dependent, see also these posts: or.stackexchange.com/questions/176/…, stackoverflow.com/questions/45531175/difference-lp-mip-and-cp $\endgroup$– Marco LübbeckeJul 26, 2020 at 19:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I'm not sure that talking about a comparison of MIP models and CP models makes sense, in part because I think that CP models tend to be solver-specific. MIP models tend to have a standard set of "features": linear (or maybe convex quadratic) constraints; linear (or maybe quadratic) objective functions; and of course variables (integer or continuous). With CP, your model is likely to be expressed at least in part in terms of "global constraints", and I suspect those are rather solver-specific (other than the ubiquitous "all different" constraint). So I'm afraid that any comparison of MIP and CP "models" will inevitably drag in the solvers being used.
Another issue is the criterion for evaluating the models (and solvers). Beyond correctness (the model is free of errors) and ease of creation (largely a matter of user expertise), there is just solution time. Solution time drags the solver back into the picture, and also raises the question of the criterion for success (provably optimality, solution better than some cutoff value, ...). My impression is that MIP models tend to have tighter bounds than CP models, and from my experience there are problems where a CP solver gets a "good" solution faster than a MIP solver but the MIP solver proves optimality faster (because its better bounds allow it to avoid exploring more of the solution space than the CP solver can avoid).
Thus I don't see a way around experimental comparisons, which must look at the solver as well as the model. I agree those comparisons are tricky to do correctly, both due to the effort put into things like mitigating symmetry or avoiding "big M" constraints on the MIP side while properly exploiting global constraints on the CP side and because there are many parameters the user can set with either type of solver. All of which, I think, suggests that we should maybe just not run around making claims about a MIP model being better or worse than a CP model.
