2
3

I am trying to better understand the use case applicability between MIP (mixed integer programming) and CP (constraint programming).

Let's take a look at the Traveling Tournament Problem (TSP). Let's suppose we want to solve this as good as possible in 1 hour for a 1000 cities. Would you recommend MIP or CP?

For a pure TSP use case, you might use one or the other. But in the real world, a pure TSP use case hardly exist: there are always additional constraints, such as:

  • Some cities are worth more than others
  • Some edges between nodes cost a second resource (for example: extra money because a toll tunnel, time because of a lower speed limit, ...)
  • The salesman has to restock his sales items when he runs out, at a depot. Each city has an estimated number of sales.
  • ...

What kind of extra constraints (examples pls) would make you stop recommending one (MIP/CP) and start recommending the other?

What kind of constraints (examples pls) are practically doable for MIP? And what kind of constraints (examples pls) would you consider killer constraints for MIP? How big is the impact of the data size?

asked 04 Apr '11, 13:47

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k42765
accept rate: 6%

retagged 26 Nov '11, 14:15

fbahr's gravatar image

fbahr ♦
4.6k717

I think your question should be rephrased: these are all cases where you don't plan to solve the TSP to optimality, but you're looking for ways to find good heuristic solutions. CP can be used to construct good heuristics, but so can MIP, local search and other combinatorial optimization techniques.

(04 Apr '11, 16:25) Greg Glockner

I agree with Greg, MIP can be also find good heuristic solutions. If you look at the work done with Concorde (on pure TSP), you will see they can find good solutions fast. Modern MIP codes is more than the traditional B&B approach. That being said I understand were you are going with the question, but I think it is too simplistic and very problem/data dependent.

(04 Apr '11, 18:05) Bo Jensen ♦

@Greg I've adjusted question to make it clear I don't care that it's optimal: I just want the best technology for example for 1 hour for a 1000 cities.

(05 Apr '11, 07:22) Geoffrey De ... ♦

@Bo How can we make the question not too simplistic? The scientist in me is looking for cold, hard data (=examples). For example, in ITC2007 the CP solvers slaughtered the MIP solvers on exam rostering and course scheduling. But in the INRC2010 I've heard (not proven!) that the MIP solvers were usually better if the number of nurses/days was little (which was the case for the official data sets, but not the hint data sets).

(05 Apr '11, 07:27) Geoffrey De ... ♦

Time-window constraints tend to make the problem much harder. In fact, your third bullet makes me think of a vehicle routing problem (many routes leaving from a central, or multiple depots), and if you add time windows to the VRP then you get a pretty tough problem.

link

answered 04 Apr '11, 18:03

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k520
accept rate: 11%

So any constraint making the problem harder, pushes a problem's recommended technology out of MIP, into CP?

(05 Apr '11, 07:30) Geoffrey De ... ♦

And vica versa: less constraints (or just 1) pushes a problem's recommended technology to MIP? Is MIP always recommended for pure TSP, or does the data size matter?

(05 Apr '11, 12:16) Geoffrey De ... ♦

When I wrote my original answer, I did not mean that the presence of time windows makes it better for CP; I meant that it makes it harder for MIP (I think this is what your original question was asking). For an answer to your current question, see my answer to the question below:

http://www.or-exchange.com/questions/80/how-do-you-decide-whether-mip-or-cp-is-more-appropriate/82#82

(05 Apr '11, 14:07) Tallys Yunes ♦

That link makes a lot of sense. What's an example of an "ugly" constraint on top of TSP that would be hard (but not impossible as I understand it) to model in MIP?

(05 Apr '11, 15:12) Geoffrey De ... ♦
1

Excluding representability issues (such as trying to model a disjunction of linear systems with distinct recession cones), it's usually possible to model most things with MIP (linear or non-linear). Even if the constraint you're interested in requires adding extra variables (e.g. if you want x1,..., xn to have distinct values), one can typically find a MIP formulation that is correct. So the issue isn't really writing the model per se, it's solving that model. The scheduling-type constraints in TTP are a good example. They aren't ugly, but they're tough to handle (poor relaxation perhaps).

(05 Apr '11, 20:34) Tallys Yunes ♦
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:

×101
×71
×37
×26

Asked: 04 Apr '11, 13:47

Seen: 3,288 times

Last updated: 26 Nov '11, 14:15

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