Determine basic feasible solutions in LP

Question

Consider a linear programming problem \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*} Assuming the constraints form a polyhedron, is there any way we can group the constraints such that each group of constraints give one basic feasible solution. For example, in the figure below, there are 4 constraints forming a polyhedron and four basic feasible solutions. Is there a simple way we can quickly determine all groups of constraints that give basic feasible solutions without computing out intersection points and then testing feasibility. For example, how do we know constraints 1 and 2, instead of 1 and 4 (although they are also independent), form a group because they give a basic feasible solution without having to compute out their intersection pints and then test feasibility to see this? Can we see this from the properties of matrix A directly (independency is apparently one of the required factors)?

Any comments or reference suggestions are highly appreciated!

Answer 1

Finding a single basic feasible solution is just as hard as solving a linear program. (That's because, from duality, minimizing $c^{\mathsf T}x$ subject to $Ax \le b$ is equivalent to finding vectors $x$ and $u$ such that $Ax \le b$, $u^{\mathsf T}A = c^{\mathsf T}$, and $u^{\mathsf T}b = c^{\mathsf T}x$.)

Finding all the basic feasible solutions is even harder than that. First of all, in general, there can be exponentially many basic feasible solutions. In such cases, our standard for an efficient algorithm is not one that efficiently generates all of them - that's impossible! Rather, we could ask for:

• An algorithm that generates all $N$ basic feasible solutions for a size-$n$ problem in $N \cdot \operatorname{poly}(n)$ time.
• More ambitiously, an algorithm that generates all solutions with $\operatorname{poly}(n)$ time between each solution and the next.

As far as I know, the second thing is still out of our reach, but here's how we can do the first thing. Starting from a single basic feasible solution, you can use the simplex method with no objective function to find all valid pivots, and get the "adjacent" basic feasible solutions. This lets you explore all the corners of your feasible region using, say, breadth-first search.

See also this answer on the operations research StackExchange for more detail.