A GPU-based Linear Programming Algorithm And Applications

Linear programming problem is a basic branch of operational research. It plays a very important role in many kinds of economic activities such as allocation of funds and task scheduling. It is mainly used to solve how to utilize existing resources to make the prospective goal achieving optimum. Although the existing linear programming problem algorithms are effective in solving many practical problems, they have to run a long time to find solutions to large scale problems. Parallel algorithm has advantages of reducing iteration times, speeding up the solving process.In recent years, the increasing demand of the multimedia and games industries for accelerating 3D rendering has driven the development of graphics processing unit (GPU). These consumer-level GPUs are cost-effective not only for game playing, but also for scientific computing. CUDA is a new GPU general programming model with the release of the unified shading architecture by NVIDIA Corporation. It provides a new parallel computation for researcher to use the GPU.A GPU-based parallel algorithm to solve large scale linear programming problem is proposed in this research. It aims to improve the computing efficiency when the linear programming problem becomes sufficiently large scale or more complicated. This parallel algorithm, based on Gaussian elimination, uses the GPU (Graphics Processing Unit) for computationally intensive tasks such as basis matrix operation, canonical form transformation and entering variable selection. At the same time, CPU is used to control the iteration. Experimental results show that the algorithm is competitive with CPU algorithm and can greatly reduce the computing time, so the GPU-based parallel algorithm is an effective way to solve large scale linear programming problem. Finally, the algorithm combines with emergency evacuation under leakage of gas dispersion and can meet the demands of time under sudden gas dispersion.