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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.