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's gravatar image

accept rate: 0%

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%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%


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

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

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's gravatar image

accept rate: 8%


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... ♦
Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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



Asked: 30 Mar '14, 12:23

Seen: 1,538 times

Last updated: 02 Apr '14, 17:49

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