Code Design as an Optimization Problem: from Mixed Integer Programming to an Improved High Performance Randomized GRASP like Algorithm and from This One to an Improved Genetic Algorithm
José Barahona da Fonseca · 2006
We begin to show that the design of optimum codes is a very difficult task 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 the GAMS 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 high performance randomized algorithm that surprisingly has much better runtimes than the MIP model.