1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$"? $\endgroup$
    – Noah Stein
    Jan 26, 2014 at 17:17
  • $\begingroup$ 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. $\endgroup$ Jan 26, 2014 at 17:51
  • 1
    $\begingroup$ Does this fit in anywhere with "bilevel programming"? $\endgroup$
    – Suvrit
    Jan 26, 2014 at 22:31
  • $\begingroup$ Please use at least one top-level tags (the ones with two letter prefix) $\endgroup$
    – user9072
    Jan 26, 2014 at 23:20
  • $\begingroup$ @Suvrit: I did not have bilevel programming in mind and would thus have to check for any relations to bilevel programming. $\endgroup$ Jan 27, 2014 at 11:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.