My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\sum{c_ix_i}), x_i\in\{0,1\}$$ $$\sum{\alpha_{ij}x_j} \le b_i$$
can be formulated without the discreteness constraint by introducing additional variables $y_i$ that are associated with the $x_i$ and, by adding solutions to optimization problems as further constraints
$$\max(2^n\sum{y_i}+\sum{c_ix_i}), x_i\in[0,1]$$ $$\sum{\alpha_{ij}x_j} \le b_i$$ $$y_j\le\max(x_j,1-x_j)$$ with $n$ sufficiently high.
now, it is known that ordinary Linear Programming is in $\mathcal{P}$ and Integer Linear Prgramming is $\mathcal{NP}$-complete.
Let's define a Linear Program to be a Nested Linear Program of order $0$ and an Integer Linear Program as a Nested Linear Program of order $1$, then a Nested Linear Program of order $n$ is one that has a linear cost function and constraints that can be formulated via the optimal solution of Nested Linear Programs of lower order.
Question:
What is the complexity class of a Nested Linear Program of order $n$?
Edit
There seems to be the need to explain, why I used $y_j\le\max(x_j,1-x_j)$, which is not convex instead of $y_j\le\min(x_j,1-x_j)$, which would be convex.
The reason is that the $\max$-formulation together with the condition that $0\le x_j\le1$ and the high weights for the $y_j$ ensures that $x_j\in\{0,1\}$ which would not be the case for the $\min$-formulation.
