Novel Parallel Algorithms for a Class of Deterministic Linear Optimization Problems

The p-median problem and Intensity-Modulated Radiation Therapy (IMRT) treatment planning problems are very important practical applications in the area of optimization. Real-life instances of both problems are time-consuming to solve using traditional solution techniques. However, both problems can be involved in time-sensitive decision-making processes, in which rapid and accurate solutions are required. This study explores parallel computational algorithms and implementations for these two discrete optimization problems. Specifically, we address the use of Graphics Processing Unit (GPU) and Central Processing Unit (CPU) based algorithms that are specific to the needs of real-life applications. The p-median problem is often used to model many real-world situations, which is NP-hard. Although the polynomial algorithm is available when the number of median is fixed, large scale p-median problems are still very difficult to solve. Previous studies in using a GPU to solve the p-median problem in parallel are limited. We propose the design and implementation of the parallel Vertex Substitution (pVS) algorithm for the p-median problem based on high-performance, many-core GPUs. pVS is based on the best profit search algorithm, an implementation of Vertex Substitution (VS), that is shown to produce reliable solutions for the p-median problem. Numerical experiments show pVS achieved speed gains ranging from 10x to 57x over the traditional CPU-based Vertex Substitution. The Fluence Map Optimization (FMO) problem in IMRT can be modeled as a large-scale LP problem. Real-life FMO problem can be time-consuming to solve using traditional sequential LP solvers. We developed a GPU-based parallel linear programming solver (GPU LP solver) using the Bounded Variable Simplex algorithm with Steepest-edge pricing for large-scale sparse LP problems. This solver is designed for general linear programming problems and can be used in branch-and-bound techniques for mixed integer programming problems. We propose a parallel explicit matrix update method to replace transformation-based matrix update in sequential simplex. A special sparse matrix format is designed so as to improve the speed of sparse column selection and parallel matrix operations. We tested our GPU-based LP solver in two FMO problems and obtained 2x speedup compared to CPLEX 12.1. The Beam Angle Optimization (BAO) problem in IMRT is a Combinatorial Optimization Problem (COP), which is very difficult to obtain an optimal solution. Previous studies explored the theories and implementations of solution techniques for general COP problems. However, applications of such techniques to IMRT problems usually applies many approximations, which may impact the quality of the final solution. The parallelization of those techniques for BAO are also limited in the literature. We focused our research on CPU-based parallel algorithms in the applications of IMRT treatment planning using the Message Passing Interface (MPI). We developed an MPI-based Master-Worker framework for solving BAO problems using various types of algorithms including Genetic Algorithm and Simulated Annealing. The proposed framework separates integer variables from the MIP model and uses optimal LP solutions as evaluation functions. We developed a hybrid framework to communicate between algorithms in parallel. The results of numerical experiments demonstrate that this framework is 5x faster than traditional solution techniques and is able to obtain a clinic-standard treatment plan in a very short time.Industrial Engineering, Department o