Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

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

Consider the following set.

$S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$

$S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer between 0 and $2^n-1$ and $y$ is its binary representation. I'm interested in the convex hull of $S_n$; you can call it $P_n$.

Has $P_n$ been studied before? Does it admit a compact extended formulation?

share|cite|improve this question
up vote 6 down vote accepted

I think $S_n$ can be written in terms of inequalities in the obvious way. Let $$ Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}. $$

I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{0, 1\}^n$ induced by picking $y_i = 1$ with probability $y^*_i$, independently for each $i$. If $y$ is sampled from that distribution, then, by linearity of expectation, $$ \mathbb{E}\ x = \mathbb{E} \sum_{i = 0}^{n-1}{2^i y_i} = \sum_{i = 0}^{n-1}{2^i y^*_i} = x^*. $$ Therefore $(x^*, y^*)$ is in the convex hull of $S_n$, which proves $Q_n \subseteq S_n$.

BTW, this didn't really use anything special about $S_n$. Whenever you have the convex hull of the set $\{(x, y): y \in S, x = Ay\}$, and the convex hull of $S$ has a concise extended formulation, the same thing will work. The main point is that $x$ is a linear function of $y$. Here we used the fact that the cube $[0, 1]^n$ has a very easy formulation in terms of inequalities.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.