A Decomposition Algorithm and its Parallelism for Block Diagonal Linear Program

Using an Affine Interior Point Mathod

Ziluan Wei       Li   Wu


A block diagonal linear program is considered: $Min \sum_{i=1}^{l+1} c_i^T x_i$ with constraints $B_ix_i=b_i, x_i >=0, i=1,2,...,l$, and $\sum_{i=1}^{l+1} A_i x_i=b$. A decomposition algorithm and its parallel computation are proposed in this paper. The algorithm starts from a strictly feasible solution, a vector $u_{l+1}$ of prices (Lagrange multipliers) with the compling constraints $\sum_{i=1}^{l+1} A_i x_i=b$ and directive vectors $ u_i$ for $B_ix_i=b_i, x_i >=0, i=1,2,...,l$ are generated. Then, a coordinating program with lower and upper bounds is obtained from the directive vectors by linear transformation. Finally, a new strictly interior feasible point can be computed by solving the coordinate system. The algorithm is convergent under certain assumptions. The parallelism of the algorithm can be easily implemented on the parallel computer since the directive vectors and the coordinating program can be generated and solved parallelly on different processors. Numerical experience show the effectiveness of the parallel method.