0
$\begingroup$

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$.

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

$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Exactly. The vertices (BFS) are simply the power group of the cardinality of variables $\endgroup$ – iarbel84 Sep 16 at 8:50
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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