Computational complexity and reductions to linear programming

Question

My question is rather general, but I have not been able to find a satisfactory answer for quite a long time, and I wonder if there has been a research concerning these issues.

I have come over a relatively large number of optimization problems, that can be expressed as a Linear Programming problem, or as an Integer Linear Programming problem. Also decision problems could be expressed as LP or ILP, with a constant objective function (i.e., concerning only (in)feasibility). If a problem can be expressed as LP, then it is certainly in $\mathbf{P}$, since Linear Programming problems can be solved in polynomial time. On the other hand, problems that cannot be expressed as LP, but only as ILP, usually are $\mathbf{NP}$-complete, despite the fact that this is not a valid proof of $\mathbf{NP}$-completeness (there could be a polynomial algorithm not based on LP solving the problem).

So my question is: is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)? Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP. Is there some known relation between their complexity and their expressibility in the form of some type of Nonlinear Programming problems? Are there any references dealing with similar problems?

Thank you in advance.

Answer 1

ILP is NP-complete. This has a few implications to your question.

Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP.

As long as you consider problems in NP, no, all problems in NP can be rewritten as ILP in polynomial time. If you consider problems not in NP, then they cannot be expressed in the form of LP or ILP because both LP and ILP are in NP.

is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)?

This is essentially asking which special cases of ILP can be solved in polynomial time. One of the fairly large classes of ILP which can be solved in polynomial time is ILP with totally unimodular constraint matrices; see Wikipedia. But if you want a very general result, it is unlikely that you get anything more than tautological statements such as “the optimization problem is in P if there is a polynomial-time algorithm to solve it.” Indeed, your question is formally equivalent to asking which problems in NP are in P, and obviously we do not know any necessary and sufficient characterization which is easy to check.