# Why does the unit cube have $2^n$ basic feasible solutions?

A unit cube is defined by $$2n$$ constraints of the form:

$$\{ x \in \mathbb{R}^n | 0 \leq x_i \leq 1, i = 1... n \}$$

Why does this give $$2^n$$ basic feasible solutions?

I calculated the number of basic feasible solutions like so:

$$(2n) C (n)$$:

$$\frac{(2n)!}{n! (2n-n)!}$$

$$\frac{(2n)!}{n!^2}$$

This expression is not equal to $$2^n$$.

• What is a "basic feasible solution"? Is it, like, an actual solution to something? – Lee Mosher Sep 16 at 1:40

$$\binom{2n}{n}$$ is not the right quantity since we can't have $$x_i=0$$ and $$x_i=1$$ at the same time. Also, note the condition of independence of constraint in the definition of BFS.

For each variable, there are $$2$$ options, it is either $$0$$ or $$1$$, hence we have $$2^n$$ BFS for a unit cube.

• Exactly. The vertices (BFS) are simply the power group of the cardinality of variables – iarbel84 Sep 16 at 8:50

In conventional linear programming notation, you would add $$n$$ slack variables $$s_{i}$$ and write this as a system of $$n$$ linear equality constraints

$$x_{i} + s_{i}=1$$, $$i=1, 2, \ldots, n$$

with

$$x,s \geq 0$$.

It’s easy to see that exactly one of $$x_{i}$$ or $$s_{i}$$ will be basic for $$i=1, 2, \ldots, n$$ in any basic feasible solution. At least one of $$x_{i}$$ or $$s_{i}$$ must be greater than 0 (and thus basic) to satisfy the $$i$$th constraint. There are only $$n$$ basic variables, so if a pair of $$x_{i}$$ and $$s_{i}$$ were both basic, then you'd be left with $$n-2$$ basic variables to satisfy the remaining $$n-1$$ constraints.

There’s a correspondence between bases and $$n$$ digit binary numbers with the $$i$$th digit equal to 0 if $$x_{i}$$ is basic and 1 if $$s_{i}$$ is basic. It is well known that there are $$2^{n}$$ binary numbers with $$n$$ bits.

It is true that there are $$2n$$ choose $$n$$ potential bases, but many of these are infeasible.

In general, with $$m$$ equality constraints and $$n$$ non-negative variables there are $$m+n$$ choose $$m$$ possible bases, but some bases may be infeasible, and multiple bases may represent the same (degenerate) basic feasible solution. There is not a one-to-one correspondence between possible bases and basic feasible solutions.

You could also treat this as an LP with no linear equality constraints, lower bounds of 0 on each variable, and upper bounds of 1 on each variable. In that case, each variable would be nonbasic at either its lower or upper bound and there are $$2^{n}$$ combinations of the lower and upper bounds.