Since a MILP problem is not necessarily NP hard. How could I demonstrate that a MILP problem is actually NP hard? There exists some smart and easy method to do that? Many thanks!


closed as unclear what you're asking by Apass.Jack, Evil, Discrete lizard Apr 28 at 12:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ This, like for most problems in NP, depends on the problem and can be done with a reduction. Unless you specify the class of MILP problems you wish to show are NP-hard, we cannot really give a more specific answer. However, this may be related: cs.stackexchange.com/questions/89140/… $\endgroup$ – Discrete lizard Apr 26 at 14:56

In general, a general MILP was proved to be NP-Hard. This is a well-known proof and can be easily found in any textbook (or even on Wikipedia).
However, you can see one specific MILP problem as an 'instance' of the general MILP problem. Thus, you still need to show its complexity.

In fact, several MILP problems are NP-Hard:

  1. Elementary Shortest Path (if the graph has negative cycles)
  2. Degree-constrained Minimum Spanning Tree
  3. Vehicle Routing Problem

However, many others are shown to be solvable in polynomial-time:

  1. Job scheduling
  2. Minimum Spanning Tree
  3. Aircraft scheduling problem

You can demonstrate that a MILP problem is NP-Hard in the same way you do with any other optimization problem.

All you need to do is to reduce an NP-Hard optimization problem $\sigma$ to your MILP, construct a solution for MILP, and shows a polynomial-time transformation of your obtained solution to a solution of $\sigma$.

Sadly, there is no standard technique or proof method that can be applied to show the complexity of any MILP problems and you need to use your creativity (and mathematical skills, in many cases) to proof the complexity of your problem.

  • 1
    $\begingroup$ +1 Thanks, Iago! $\endgroup$ – David Richerby Apr 27 at 14:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.