# Finding all basic feasible solutions in a linear program

Given the following constraints

$$\begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ x_1&&&-&x_3&&&\le 2\\ x_1&+&x_2&&&-&x_4&\le 3\\ x_i&&&&&&&\in\mathbb{R}_{\ge 0} \end{split}$$

I want to find all basic feasible solutions. They are the extreme points of the convex polyhedra induced by these constraints. However, to solve these system we introduce as many slack variables as we have inequalities. This leads us to

$$\begin{split} x_1 &+&x_2&+&x_3&+&x_4&+&s_1&&&&&&&&= 10 \\ x_1&-&x_2&&&&&&&&+&s_2&&&&&=0\\ x_1&&&-&x_3&&&&&&&&+&s_3&&&= 2\\ x_1&+&x_2&&&-&x_4&&&&&&&&+&s_4&= 3\\ \hat{x}_i&&&&&&&&&&&&&&&&\in\mathbb{R}_{\ge 0} \end{split}$$

Now, a basic feasible solution would be $$\hat{x}\equiv (x_1,x_2,x_3,x_4\;|\;s_1,s_2s_3,s_4)=(0,0,0,0\;|\;10,0,2,3)^T$$ However,

1. How do I find all basic feasible solutions from this starting basic feasible solution?
2. These basic feasible solutions are basic feasible solutions for the modified system. How do I get basic feasible solutions for the original problem?
• Are the $x$'s real or integer ? – Claude Leibovici Feb 15 '14 at 12:32
• @ClaudeLeibovici - The x's are real. – 0xbadf00d Feb 15 '14 at 12:41
• Your second question is the easy part: just ignore all the slack variables. (For example, the basic feasible solution you provided, $(0,0,0,0\;|\;10,0,2,3)^T$, corresponds to $(0,0,0,0)$).) – Théophile Jan 21 '15 at 21:49

## 2 Answers

(I have some doubts that this answer is correct, but leave it here for discussion.)

1. With real variables you probably have an infinite number of basic feasible solutions.

2. The solution you show is a basic feasible solution for the original problem, with all variables equal to zero. To get a feasible solution for your original problem, with nonzero problem variables: Do the Simplex phase II for some times. In the first step you take in a problem variable as a basic variable. Then after another the other variables. Probably your optimal solution has some zero problem variables.

Why do you want to have all basic feasible solutions?

• That's not true. If there are $n$ variables and $m$ constraints, then there are at most $\binom nm$ basic feasible solutions. – Math1000 Feb 25 '15 at 1:45
• Ok, I think you are right, for non degenerate problems. I must confess, that I don't understand this fully, but: I think this problem is degenerate, because it has a basic solution with a basic variable which is zero. And degenerate problems have more basic feasible solutions. – JaBe Feb 25 '15 at 18:38
• I think you have it the other way around. You can have more than one basis corresponding to a given BFS (in which case that BFS would be degenerate), but that means there would be fewer than $\binom nm$ BFS, not more. – Math1000 Feb 25 '15 at 18:48
• But when you have more than one Basis, the BFS are not linear independent? Or is the BFS is more about the objective function value? In this example, there is no objectice function... I'm a little bit confused about the exact Definition of a BFS, or what differates one BFS from the other? – JaBe Feb 25 '15 at 19:53

The basic feasible solutions of what you call "original problem" are exactly the same as the basic feasible solutions of the modified system: by adding slack variables you do not change the solution set; you just embed it in a higher dimensional space.

The problem of findig all basic feasible solutions of a polyhedron is called Vertex Enumeration Problem. In order to find all vertices, you may first obtain an arbitrary one, call it your root solution, and then build a solution tree by searching for its neighbors, its neighbors' neighbors, and so on. Each time you obtain a neighboring solution, you will have to check whether it is one that you already obtained; in which case you abandon the corresponding branch.

Avis and Fukuda adapted the Criss-Cross Algorithm to make such a search particularly efficient. They also report their search to take polynomially bounded time, so your problem might have much less feasible basic solutions than all of its ${8\choose4}$ arbitrary basic solutions.