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

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.