Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

What is the complexity class of a Nested Linear Program of order $n$?

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.

share|cite|improve this question
I'm confused: the constraint $y_j\leq\max(x_j,1-x_j)$ is not convex (like $y_j\leq\min(x_j,1-x_j)$ would be). What do you mean "adding solutions to optimization problems as further constraints"? Put another way, could you give an illustrative example of a "Nested Linear Program of order $2$"? – Noah Stein Jan 26 '14 at 17:17
Noah, using the $y_j\le\max(x_J,1-x_j)$ of course isn't convex, but could be expressed by bilinear constraints. It is however the observation that such a bilinear constraint can be interpreted as one that contains a linear combination of variables that is constrained by the solution of a linear optimization problem, which leads to the question, whether the resulting nesting could be continued and what the consequences would be. To clarify: Nested Linear Programs are not Linear Programs. – Manfred Weis Jan 26 '14 at 17:51
Does this fit in anywhere with "bilevel programming"? – Suvrit Jan 26 '14 at 22:31
Please use at least one top-level tags (the ones with two letter prefix) – quid Jan 26 '14 at 23:20
@Suvrit: I did not have bilevel programming in mind and would thus have to check for any relations to bilevel programming. – Manfred Weis Jan 27 '14 at 11:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.