Criss-Cross Method

A standard form of the Linear Programming problem of maximizing a linear function over a Convex Polyhedron is to maximize ${\bf c}\cdot{\bf x}$ subject to ${\hbox{\sf m}}{\bf x} \leq {\bf b}$ and ${\bf x}\geq {\bf0}$, where m is a given $s\times d$ matrix, ${\bf c}$ and ${\bf b}$ are given $d$-vector and $s$-vectors, respectively. The Criss-cross method always finds a Vertex solution if an optimal solution exists.

See also Convex Polyhedron, Linear Programming, Vertex (Polyhedron)