ABSTRACT
Institute for Informatics and Telecommunications, HEPIA, University of Applied Sciences of Western Switzerland – Geneva, Switzerland
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 10.2 Simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
10.2.1 Linear programming model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 10.2.2 Standard simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 10.2.3 Revised simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 10.2.4 Heuristics and improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.3 Branch-and-bound algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.3.1 Integer linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.3.2 Branch-and-bound tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.3.3 Branching strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 10.3.4 Node selection strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 10.3.5 Cutting-plane methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
10.4 CUDA considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10.4.1 Parallel reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10.4.2 Kernel optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
10.5 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 10.5.1 Standard simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 10.5.2 Revised simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 10.5.3 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.6 Performance model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 10.6.1 Levels of parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 10.6.2 Amount of work done by a thread . . . . . . . . . . . . . . . . . . . . . . 238 10.6.3 Global performance model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 10.6.4 A kernel example: steepest-edge . . . . . . . . . . . . . . . . . . . . . . . . . 239 10.6.5 Standard simplex GPU implementation model . . . . . . . . . 240
10.7 Measurements and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 10.7.1 Performance model validation . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 10.7.2 Performance comparison of implementations . . . . . . . . . . . 241
10.8 Conclusion and perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
The simplex method [4] is a well-known optimization algorithm for solving linear programming (LP) models in the field of operations research. It is part of software often employed by businesses for finding solutions to problems such as airline scheduling problems. The original standard simplex method was proposed by Dantzig in 1947. A more efficient method, named the revised simplex, was later developed. Nowadays its sequential implementation can be found in almost all commercial LP solvers. But the always increasing complexity and size of LP problems from the industry, drives the demand for more computational power. In this context, parallelization is the natural idea to investigate [17]. Already in 1996, Thomadakis and Liu [23] implemented the standard method on a massive parallel computer and obtained an increase in performances when solving dense or large problems.
