A Linear optimization problem consists of a linear objective function to be maximized or minimized and linear constraints in the form of inequalities or equalities. Many problems can be reduced to linear optimization problems, such as minimum cost network flow. A common algorithm for solving linear optimization problems is the simplex method. Due to the nature of a region enclosed by linear constraints, the feasible region for a linear optimization problem with n variables is a polytope in n dimensions. The Simplex Method finds the optimal solution by searching the vertices of the polytope, moving along edges which increase/decrease the objective function. Vertices are identified by a basis of decision variables; non-basic variables must be zero. A basis uniquely defines a vertex of the polytope, and each iteration of the algorithm pivots a new variable into the basis and pivots out an old one.

For small instances, the simplex method can be performed by hand by performing arithmetic operations on the system of inequalities. For any practical application, it is performed on a matrix to represent the inequalities. This modification to the algorithm is called the revised simplex method, which takes advantage of the structure of the matrix to increase efficiency. A full description of the algorithm can be found in one of the references, but I’ll run over some of the advantages for using the revised simplex method.

Linear programs have a tendency to have matrices which are very sparse, as each constraint typically only applies to a small subset of the variables. For example, in a network flow problem, the constraints would force the sum of the flow into a node to equal the flow out. Hence for any given node, the number of edges it is incident to is a significant minority of the total edges, leading to many zeros in the matrix.

The revised Simplex Method performs most of its computation with a basis matrix, a matrix containing only the columns corresponding to the basis variables. Often, the number of variables is greater than the number of constraints (e.g. more edges than nodes in a flow network), hence performing operations on the basis matrix is much faster than manipulating the whole thing. Additionally, each iteration of the algorithm solves two systems of equations using the basis matrix and its transpose. This can be done as described in class through factorization of the matrix. The following iteration has a basis matrix that differs only by one column, hence factoring the new basis matrix is considerably easier than starting from scratch.

References:

http://en.wikipedia.org/wiki/Simplex_method

http://www.cise.ufl.edu/~davis/Morgan/chapter2.htm