Decomposition and Parallelization of Linear Programming Algorithms

Karbowski, A

  • Progress in Automation, Robotics and Measuring Techniques;
  • Tom: 350;
  • Strony: 113-126;
  • 2015;

The paper assesses possible approaches to decomposition and parallelization of basic linear programming algorithms, including: Dantzig-Wolfe, Benders, augmented Lagrangian, revised simplex and primal-dual interior point methods. Quite surprisingly, the first three of them - of hierarchical optimization type - exhibit considerable advantages nowadays, in the era of multicore processors and accelerators of any type (GPU, FPGA, Xeon Phi, etc.).