Accelerating Linear Programming Performance: A Hardware-Software Co-Design Approach for the Simplex Method

Linear programming problems play a key role in mathematical optimization. A wide variety of practical applications can be modeled as a linear optimization problem and also more complex problems are usually solved by repeatedly solving linear subproblems. CPU-based methods face limitations when we aim to reach very small computation times or substantial reductions in energy consumption for edge applications such as robot control. To address these challenges, we propose a dedicated hardware accelerator for the Simplex algorithm, that we developed using a hardware-software co-design approach. In detail, we develop a hardware accelerator (Simplex Processing Unit, SXPU) for the computationally expensive pricing step in the Simplex algorithm. Our accelerator is mainly targeting at ASIC technology but is also suitable for implementation on FPGA for prototyping. It can handle realistic problem sizes and yields significant improvements in computation time compared to a software-based approach, demonstrating its potential for high-performance and energy-efficient optimization.