# 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.