A PARALLEL INTERIOR-POINT METHOD AND ITS APPLICATION TO FACILITY LOCATION-PROBLEMS

We present a parallel interior point algorithm to solve block structur ed linear programs. This algorithm can solve block diagonal linear pro grams with both side constraints (common rows) and side variables (com mon columns). The performance of the algorithm is investigated on unca pacitated, capacitated and stochastic facility location problems. The facility location problems are formulated as mixed integer linear prog rams. Each subproblem of the branch and bound phase of the MIP is solv ed using the parallel interior point method. We compare the total time taken by the parallel interior point method with the simplex method t o solve the complete problems, as well as the various costs of reoptim isation of the non-root nodes of the branch and bound. Computational r esults on two parallel computers (Fujitsu AP1000 and IBM SP2) are also presented in this paper.