# unimodular vs NP hard

 1 Dear All, I have a MIP (mixed interger programming model) network interdiction problem ( Ref: Deterministic Network Interdiction, K.R. Wood). It is proved to be NP hard. In the model there are contraints that come from the maxflow problem. I have implemted the model and when I solve the LP relxation of the problem I get a solution same as that of the MIP. I am stumped. I am confused as to where to start looking. I looked at my implementation and it looks correct. So my question is can the unimodularity property of the max flow problem in the orignial MIP play a role? And it it true that a NP hard problem cannot be unimodular? Please help me here, I have been thinking about this for more than two weeks now. Than you in advance asked 30 Mar '14, 12:23 satish 21●1●5 accept rate: 0%

 5 To answer the last question first: it cannot happen that you ''always'' get integer solutions from the LP relaxation when your problem is NP-hard (unless P=NP) as this would contradict complexity theory. So, the matrix of your MIP (a) either is not (totally) unimodular, or (b) the MIP does not model your (general) NP-hard problem. It can happen that your problem is "well-behaving" in the sense that you "often" see integer solutions for the LP relaxation. The structure of the matrix may play a role (when "part" of it is "easy"); the instances may be another reason. They may encode a special structure which models a special case of your NP-hard problem, and the special case may be, in fact, polytime solvable. To check the latter, you may start searching the lit for polytime solvable special cases. answered 30 Mar '14, 12:40 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16% 1 Thank you Marco, I completely agree with you. So in the model I have added linerization constriants. So the BigM comes into play. When my BigM is 1 it LP =MIP but when I increase BigM I non interger solutions. Does this tell you something? (30 Mar '14, 12:49) satish 1 It is not terribly surprising to see integer solutions to the LP when M=1 (and not for larger M). The real wisdom is how large doors M need to be to make your model valid? In most applications, you need M much larger than unity. (30 Mar '14, 19:05) Paul Rubin ♦♦
 1 It is not because the problem class is NP hard that a given problem instance cannot be solved using a polynomial time algorithm. In your case, you can be lucky an have easy instances to solve because they re unimodular. What would be striking is if any instance of your NP hard problem is unimodular. That would be striking because it would imply P=NP. answered 02 Apr '14, 07:44 jfpuget 2.5k●3●10 accept rate: 8% 1 Particular instances might be easy to solve because the objective happens to correspond to an optimal solution to the LP relaxation that happens to be integer. That doesn't mean that every extreme point of the LPR will be integer. Also, it's possible that small instances could be TU but larger instances would not. Further, it's possible that some subset of instances with a particular structure are TU, but more general instances are not. (02 Apr '14, 17:49) Matthew Salt... ♦
 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:

×71
×8
×4
×1