Group for Research in Decision Analysis

# Vector space decomposition for linear programming

## Jacques Desrosiers – Professor, Department of Decision Sciences, HEC Montréal, Canada

This presentation describes a primal vector space decomposition algorithm for a linear program comprising $$m$$ equality constraints and $$n$$ bounded variables. Given a feasible basic solution, let $$B$$ be the index-set of the basic variables and identify the index-set $$F \subseteq B$$ of non-degenerate (or free) variables. Construct the residual problem and left-multiply by an invertible linear transformation $$\mathbf{T}^{-1}$$ the set of equality constraints. This splits $${\mathbb R}^m$$ in two orthogonal vector subspaces $$\mathbf{V}$$ and $$\mathbf{V}^\perp$$. This is followed by a Dantzig-Wolfe decomposition which naturally leads to the construction of the pricing problem.

Let $$\mathbf{\Lambda}$$ of dimension $$r$$ (resp. $$\mathbf{\Lambda}^\perp$$ of dimension $$m - r$$) be the vector subspace basis of $$\mathbf{V}$$ (resp. $$\mathbf{V}^\perp$$); then $$\mathbf{T}:= [\mathbf{\Lambda}, \mathbf{\Lambda}^\perp]$$. The domain of the pricing problem is a cone, that is, a homogeneous system composed of the $$m - r$$ constraints corresponding to $$\mathbf{V}^\perp$$ and the non-negativity restrictions on the variables. By adding a scaling constraint, its objective function optimizes $$\mu$$, the value of the minimum reduced cost. The master problem comprises all the other bounds on the variables and the remaining $$r$$ equality constraints. If $$\mu < 0$$, the pricing problem generates an extreme ray that belongs to $$\mathbf{V}$$, otherwise the current solution is optimal. Since the pricing problem borrows from the residual problem, its optimal solution actually identifies a possible improving direction. Because the step-size is then computed with respect to the master problem, we can see the exchange mechanism from one solution to the next as a two-step procedure: a direction identified by the pricing problem and the allowable step-size that finalizes the exchange in the master problem.

Let $$R \subseteq B$$ be the index-set of the basic columns spanned by $$\mathbf{\Lambda}$$ in the master problem. Depending on $$R$$, at least four properties can be attributed to this generic vector space decomposition algorithm.
(1) It may come up with degenerate pivots and may even not converge if $$F \subset R$$, as in the Primal Simplex method where $$R=B$$ (see Dantzig 1963).
(2) It ensures a non-degenerate pivot at every iteration if $$R \subseteq F$$, as in the Improved Primal Simplex algorithm (IPS) of Elhallaoui et al. (2011) for which $$R = F$$.
(3) It becomes strongly polynomial for the capacitated network flow problem, as in the Minimum Mean Cycle-Canceling algorithm (MMCC) of Goldberg and Tarjan (1989) for which $$R = \emptyset$$.
(4) It offers an efficient compromise for the linear relaxation of the set partitioning problem, as in the Dynamic Constraint Aggregation method (DCA) of Elhallaoui et al. (2005) where $$R \supseteq F$$ for fractional solutions but $$R = F$$ for integer solutions.

## References

• George B. Dantzig. Linear programming and extensions. Princeton University Press, New Jersey, 1963.
• Issmail Elhallaoui, Daniel Villeneuve, Françcois Soumis, and Guy Desaulniers. Dynamic aggregation of set partitioning constraints in column generation. Operations Research, 53(4):632-645, 2005. doi:10.1287/opre.1050.0222.
• Issmail Elhallaoui, Abdelmoutalib Metrane, Guy Desaulniers, and Françcois Soumis. An Improved Primal Simplex algorithm for degenerate linear programs. INFORMS Journal on Computing, 23:569-577, 2011. doi:10.1287/ijoc.1100.0425.
• Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM, 36(4):873-886, 1989. doi:10.1145/76359.76368.