# The simplest way to make TSP too hard for MIP

 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 De ... ♦ 3.6k●4●27●65 accept rate: 6% fbahr ♦ 4.6k●7●17 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 ... ♦

 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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