Grundlösung

Grundlösung is a term used in German mathematics and optimization with different historical usages, but it is most commonly encountered in the context of linear programming as a basic (or fundamental) solution.

In linear programming, a Grundlösung (often called a basis solution or basic solution in English) refers to a solution obtained by selecting a set B of m linearly independent columns from the constraint matrix A for a system of equations Ax = b with x ≥ 0. One forms x by setting all non-basic variables (those not in B) to zero and solving for the basic variables x_B = A_B^{-1} b. If the resulting x_B is nonnegative, the solution is a basic feasible solution, which geometrically corresponds to a vertex (extreme point) of the feasible polyhedron. A Grundlösung can be degenerate when some basic variables equal zero, even though a nontrivial basis is used; in degeneracy multiple bases may map to the same vertex.

In optimization practice, Grundlösungen are the states the simplex method moves between as it traverses adjacent vertices by exchanging a basic variable with a non-basic one. The number of basic variables equals the number of equations (the rank of A). When a feasible region is nonempty, an optimal solution to a linear program exists among Grundlösungen, typically at an extreme point.

Terminology varies: many German texts use Basislösung (basis solution) for the same concept, while Grundlösung appears in older or field-specific literature. The exact term may depend on historical context and the preferred vocabulary of the subdiscipline.