7
2

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?

asked 01 Dec '09, 15:34

CLC's gravatar image

CLC
7112
accept rate: 0%


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...

link

answered 02 Dec '09, 04:45

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k520
accept rate: 11%

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.

link

answered 01 Dec '09, 21:44

anonymous's gravatar image

anonymous
691411
accept rate: 8%

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

link

answered 11 Dec '09, 08:06

ShahinG's gravatar image

ShahinG
281213
accept rate: 0%

edited 11 Dec '09, 13:42

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k51633

2

This is a question, not an answer! Go to the home page and post the question instead.

(11 Dec '09, 13:42) Michael Trick ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×127
×71
×37

Asked: 01 Dec '09, 15:34

Seen: 5,841 times

Last updated: 11 Dec '09, 13:42

OR-Exchange! Your site for questions, answers, and announcements about operations research.