### A Decomposition Algorithm and its Parallelism for
Block Diagonal Linear Program

### Using an Affine Interior Point Mathod

#### Ziluan Wei Li Wu

**Abstract**

A block diagonal linear program is considered: $Min \sum_{i=1}^{l+1}
c_i^T **x**_i$ with constraints $B_i**x**_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_i**x**_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.