Groupe d’études et de recherche en analyse des décisions

Vector space decomposition for linear programming

Jacques Desrosiers Professeur titulaire, Département de sciences de la décision, 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.