Integer programming is known to be NP-complete. We also know that each class in the polynomial hierarchy contains elements not contained in the ones below, so Integer programming is not complete for classes higher up in the hierarchy.
Is there a generalization of integer programming for each class in the polynomial hierarchy that is complete for that class?
I can suggest a way to get a complete problem for $\Sigma_1^P, \Sigma_3^P, \Sigma_5^P,\dots$ and $\Pi_2^P,\Pi_4^P,\dots$.
The standard way to obtain a complete problem for $\Sigma_k^P$ or $\Pi_k^P$ is as a TQBF instance with $k-1$ alternations of quantifiers. I'll modify this to use integer programming instead of Boolean satisfiability.
Specifically: Let $f$ be a Boolean formula, and consider satisfiability of
$$\exists X_1 \forall X_2 \exists X_3 \cdots . f(X_1,X_2,X_3,\cdots)$$
where each $X_i$ represents a group of Boolean variables. Then this problem is $\Sigma_k^P$-complete. Assume $k$ is odd, so the sequence of quantifiers ends with $\exists X_k$. Now if we replace $f$ with $S$, a system of linear inequalities over 0-or-1 binary integer variables, and let each $X_i$ be a (pairwise disjoint) group of such variables, then testing satisfiability of
$$\exists X_1 \forall X_2 \exists X_3 \cdots . S$$
is $\Sigma_k^P$-complete. (Why? Given a Boolean formula $f$, it is easy to translate it to a system $S$ with variables $X_1,\dots,X_k,Y$ so that, for every $X_1,\dots,X_k$, $\exists Y . S$ is satisfiable iff $f$ is satisfiable: use the translations in Express boolean logic operations in zero-one integer linear programming (ILP), and existentially quantify all new variables introduced. Now since the formula above ends in $\exists$, we can merge the $\exists Y$ into the final quantifier, without increasing the number of quantifier alternations. You can do a similar translation in the reverse order as well, using the Tseytin transform.) The same holds if you allow arbitrary integer variables (not necessarily binary) -- though in this case it is more challenging to prove that it is contained in $\Sigma_k^P$.
Notice that the problem you obtain for $\Sigma_1^P$ is just the classical problem of feasibility of an integer linear program (which is NP-complete). So this is a generalization of the NP-completeness of ILP.
For $\Pi_k^P$, do the same, but the quantifiers start with $\forall$ instead of $\exists$.
I don't know whether there is some way to extend this to work for $\Sigma_k^P$ when $k$ is even, or $\Pi_k^P$ when $k$ is odd. The sticking point I run into is inability to merge the $\exists Y$ into the final quantifier when the final quantifier is $\forall$.
