How do you decide whether MIP or CP is more appropriate? - OR-Exchange most recent 30 from http://www.or-exchange.com2010-09-09T20:40:13Zhttp://www.or-exchange.com/feeds/question/80http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://www.or-exchange.com/questions/80/how-do-you-decide-whether-mip-or-cp-is-more-appropriateHow do you decide whether MIP or CP is more appropriate?CLC2009-12-01T15:34:56Z2009-12-11T13:42:21Z
<p>What are some guidelines for deciding whether a MIP or CP approach is more appropriate for modeling an optimization problem? Or in what cases should CP be used instead of MIP?</p>
http://www.or-exchange.com/questions/80/how-do-you-decide-whether-mip-or-cp-is-more-appropriate/81#81Answer by anonymous for How do you decide whether MIP or CP is more appropriate?anonymous2009-12-01T21:44:23Z2009-12-01T21:44:23Z<p>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.</p>
http://www.or-exchange.com/questions/80/how-do-you-decide-whether-mip-or-cp-is-more-appropriate/82#82Answer by Tallys Yunes for How do you decide whether MIP or CP is more appropriate?Tallys Yunes2009-12-02T04:45:56Z2009-12-02T04:45:56Z<p>This question doesn't really have a definitive answer, but here it goes:</p>
<p>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).</p>
<p>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.</p>
<p>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...</p>
http://www.or-exchange.com/questions/80/how-do-you-decide-whether-mip-or-cp-is-more-appropriate/94#94Answer by ShahinG for How do you decide whether MIP or CP is more appropriate?ShahinG2009-12-11T08:06:54Z2009-12-11T13:42:21Z<p>Hi,
does any one know a good ...?</p>