The first line on the Wikipedia page for basic feasible solutions reads, In the theory of linear programming, a basic feasible solution (BFS) is, intuitively, a solution with a minimal number of non-zero variables.

I do not understand this, I could always have the origin within a convex polyhedron, but it is not necessary that the origin is a vertex of my polyhedron, is it? What am I getting wrong here?

  • 1
    $\begingroup$ This is only intuition. I recommend reading a textbook or lecture notes. $\endgroup$ Apr 14 '20 at 21:51
  • $\begingroup$ The text I am reading also has similar statements. I must add that they mention this for linear programs in the equational form, if that helps. $\endgroup$
    – Legolas
    Apr 14 '20 at 21:53
  • 1
    $\begingroup$ A basic feasible solution is one where $n$ linearly independent inequalities are tight, where $n$ is the dimension. The corresponding equations define a 0-dimensional face of the polytope, in other words, a vertex. $\endgroup$ Apr 14 '20 at 21:54
  • 2
    $\begingroup$ You cannot expect to understand what a BFS is without a proper definition. The Wikipedia quote doesn’t include a definition. Can you add your definition of BFS? $\endgroup$ Apr 14 '20 at 21:55

Your Answer

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

Browse other questions tagged or ask your own question.