Parallelization of an interior point algorithm for linear programming

Abstract

Bu çalışmada, Karmarkar-tipi bir doğrusal programlama optimizasyon algoritması olan Mehrotra'nın predictor-corrector iç nokta algoritmasının paralelleştirilmesi sunulmaktadır. Algoritmanın içerdiği işlem tipleri belirlenmiş ve her işlem tipi için paralel algoritmalar sunulmuştur. Karmarkar-tipi algoritmaların işlem ağırlığını oluşturan büyük simetrik doğrusal denklem kümelerinin çözümü detaylı incelenmiştir. Birçok ileri ve geri çözüm algoritması test e- dilmiş, bir biriktirmeli geri çözüm algoritması geliştirilmiştir. Seyrek matris- vektör çarpımı ve faktörizasyon işlemlerinin dağıtımı için sezgisel bin-packing algoritmaları kullanılmıştır. Performans sonuçlan en iyi olan algoritmalar doğrusal programlama problemlerinin çoklu bilgisayarlarda paralel çözümü için bir sistem geliştirilmesinde kullanılmıştır. Dizayn kıstasları ve uygulama de tayları tartışılmış, bazı performans sonuçları sunulmuştur. Anahtar Kelimeler: Doğrusal Programlama, İç Nokta Algoritmaları, Dağı- tık Sistemler, Paralel İşleme.

In this study, we present the parallelization of Mehrotra's predictor-corrector interior point algorithm, which is a Karmarkar-type optimization method for linear programming. Computation types needed by the algorithm are identi fied and parallel algorithms for each type are presented. The repeated solution of large symmetric sets of linear equations, which constitutes the major com putational effort in Karmarkar-type algorithms, is studied in detail. Several forward and backward solution algorithms are tested, and buffered backward solution algorithm is developed. Heurustic bin-packing algorithms are used to schedule sparse matrix- vector product and factorization operations. Algo rithms having the best performance results are used to implement a system to solve linear programs in parallel on multicomputers. Design considerations and implementation details of the system are discussed, and performance results are presented from a number of real problems. Keywords: Linear Programming, Interior Point Algorithms, Distributed Systems, Parallel Processing.