Open Collections

Distributed linear programming with Apache Spark

University of British Columbia

For this thesis project, we have implemented Mehrotra's predictor-corrector interior point algorithm on top of Apache Spark for solving large-scale linear programming problems. Our large-scale solver (Spark-LP) is unique because it is open-source, fault-tolerant and can be used on commodity cluster of machines. As a result, Spark-LP provides an opportunity to solve large-scale problems at the lowest possible cost. We have assessed the performance and convergent results of our solver on self-generated, sparse and dense large-scale problems over small to medium-sized clusters, composed of 16 to 64 Amazon's Elastic Computing Cloud r3.xlarge instances. In conclusions, we have made important suggestions for breaking the current structural limitations so that our solver can be used on heterogeneous clusters containing CPUs and GPUs on JVM environment without the usual numerical limitations and overheads.

Text

2017-01-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59990

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/