Why using linear integer programming (ILP) though it is NP-Complete?

Question

The question may be stupid but it really confuses me for a long time.

I read a lot of papers in wireless sensor network. Many researchers model their problems into the form of ILP. However, ILP is NP-Complete so it is not efficient for solving a problem.

So why people write their problems into the form of ILP? Do they do that to make their problem clear to see and easy to understand? Or do I make some mistakes understanding the relations between ILP and NPC?

I am really appreciated that you can help me to solve this question.

Answer 1

Although the question might be considered off-topic, there are basically a few points to address.

1. You are right that general integer linear programming is NP-hard.
2. If a specific problem needs to be solved and general integer linear programming is the most specific way to formulate it, then nothing can be done about it; some problems are just hard to solve.
3. In some cases, it is possible to use the LP relaxation instead, either as a heuristic or some approximation ratio can be proven.

The key point here is that integer linear programming is a widespread formalism for expressing problems. Basically I understand your question as the follwing one.

"Why do people use a model that is algorithmically hard to solve to describe practical problems?"

Well, if that shortcoming could be circumvented in general, it would be a good idea to express every problem there is in terms of sorting, which is algorithmically easy.

Answer 2

NP-hard refers to the complexity of algorithms in the worst case. For most NP-hard problems, we have effective algorithms (heuristic or exact) that perform well most of the time, even if they do not perform well in the worst case. ILP is therefore a very useful tool in practice, even if there are some problems that it doesn't do well on.

I have a hammer. There are some jobs that my hammer is just no good for, or would take a very long time on. But it's still a very useful tool, because it can do a lot of jobs for me very well.

ILP is, in many ways, the same thing.