Dual-guided pivot rules for linear programming

par Jacques Desrosiers (HEC et GERAD Montréal)

jeudi 19 juin 2014, 09:00 → 10:00 Europe/Paris

XLIM Salle X.203

This paper describes a generic primal algorithm for linear programming guided by dual feasibility considerations. The resolution process moves from one solution to the next according to an exchange mechanism that 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, it is the selection of a convex combination of variables entering the basis. The most known special case is the Primal Simplex where all dual variables are fixed. Other special cases are, amongst others, the strongly polynomial Minimum Mean Cycle-Canceling algorithm for network flow problems for which all dual variables are optimized at every iteration, and the Improved Primal Simplex for which one fixes the dual variables associated with the non-degenerate variables, this choice yielding non-degenerate pivots only. Properties of this generic algorithm allow identifying subsets for the fixed dual variables that totally avoid degenerate pivots. Ultimately, we propose an interpretation in terms of a dynamic Dantzig-Wolfe decomposition from which emanates a vector space decomposition algorithm.