This paper describes a vector space decomposition algorithmic framework for linear programming guided by dual feasibility considerations. The resolution process moves from one basic solution to the next according to an exchange mechanism which is defined by a direction and a post-evaluated step size. The core component of this direction is obtained via the smallest reduced cost that can be achieved upon dividing the set of dual variables in two subsets: one being fixed whiles the other being optimized. From a primal perspective, such a pricing problem selects a convex combination of variables entering the basis. The direction is uniquely completed by identifying a posteriori affected variables, if any. The degenerate status of the current solution can be exploited in specific variants. This unified framework is presented in a generic format from which different variants can be extracted. These include several well known algorithms. The most known special case is the Primal Simplex algorithm where all dual variables are fixed: this results in the choice of a single entering variable, indeed a myopic strategy commonly leading to degenerate pivots. At the other extreme, we find the strongly polynomial Minimum Mean Cycle-Canceling algorithm for the capacitated network ow problem for which all dual variables are optimized at every iteration. Somewhere in between these two extremes lies another special case, the Improved Primal Simplex algorithm for which one fixes the dual variables associated with the nondegenerate basic variables and optimizes the rest. The two last variants both bestow a pricing problem providing necessary and suffcient optimality conditions. As a result, nondegenerate directions are also issued from these pricing steps. These directions move on the edges of the polyhedron for the latter while the former can identify interior directions by combining edge directions. Other properties are derived on different variants of this generic framework.
Citation
Submitted