Code design as an optimization problem: from mixed integer programming to a high performance simplified randomized algorithm
José Barahona da Fonseca · International Conference on Artificial Intelligence · 2006
We begin to show that the design of optimum codes is a very difficult tasks by a set of preliminary brute force experiments where we generate all the possible optimum codes of a given length and minimum Hamming distance and then estimate the probability of finding one of these codes filling randomly the matrix that defines the code. Then we develop a novel approach to the code design problem based on the well known optimization technique of Mixed Integer Programming. Unfortunately our optimization software package limitation of 10 indexes imposes a limit of a maximum length 5 in the code to be designed. We show some results confirmed by the literature with this MIP model. Finally we develop a simplified randomized algorithm that surprisingly has better runtimes than the MIP model.