Efficient exact maximum-likelihood decoding and minimum-distance computation for binary linear codes (RWTH Aachen)

PI: Dr. A. Tillmann
Researchers: C. Puchert (RWTH Aachen)
Funding: Excellence Initiative of the German federal and state governments [StUpPD_350-18]
Duration: 2018 – 2019

This project took a closer look at the state-of-the-art branch & cut algorithms for the exact optimal solution of the maximum-likelihood
decoding and minimum-distance computation problems for binary linear codes. In the course of the project, a novel hybrid solver was developed that combines standard methods with modelling aspects rooted in matroid theory, and the open question of computational intractability of separating forbidden-set inequalities associated with redundant parity-checks was settled and an exact IP model to solve this RPC separation problem was proposed.

The project work was conducted at RWTH Aachen while the PI was with the Chair of Operations Research.