EURO 2025 Leeds
Abstract Submission

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

Invited abstract in session TB-43: Continuous solvers, stream Software for Optimization.

Tuesday, 10:30-12:00
Room: Newlyn GR.07

Authors (first author is the speaker)

1. Kristin Braun
Analytics, Fraunhofer Institute for Integrated Circuits IIS
2. Marcus Bednara
Fraunhofer Institute for Integrated Circuits IIS
3. Martina Kuchlbauer
Fraunhofer Institute for Integrated Circuits IIS
4. Carsten Sigwarth
Fraunhofer Institute for Integrated Circuits IIS

Abstract

Linear programming plays a key role in mathematical optimization, forming the basis for solving a wide range of practical problems. Many real-world applications can be directly modeled as linear programs, while more complex problems, such as Mixed-Integer Programs (MIP) and Mixed-Integer Nonlinear Programs (MINLP), often rely on repeatedly solving linear relaxations. However, CPU-based methods face limitations when targeting extremely low computation times or substantial energy reductions, particularly in edge applications such as real-time robot control.

To address these challenges, we propose a dedicated hardware accelerator for the Simplex algorithm, developed using a hardware-software co-design approach. Specifically, we introduce the Simplex Processing Unit (SXPU), an accelerator for the computationally expensive pricing step in the Simplex method. Our design seamlessly integrates with the open-source HiGHS solver, accelerating the solution of large-scale LP relaxations in MIP and MINLP contexts. The SXPU is primarily designed for ASIC implementation to maximize performance and energy efficiency but also supports FPGA-based prototyping. It achieves significant speedups over software-based approaches, demonstrating its potential for high-performance, energy-efficient optimization in mathematical programming solvers.

Keywords

Status: accepted

Back to the list of papers