Four Different MILP Models to Generate Optimal Error Correcting Codes, Or How a Much Greater MILP Model is Much More Efficient

In this paper we present four Mixed Integer Linear Programming (MILP) models to generate optimal error correcting codes over a given alphabet A with a given length (the number of characters of each word) L and minimum Hamming distance d, and in some cases imposing words with a constant weight (the number of characters different than zero), w. From the experience with a initial nonlinear model we rapidly reach the conclusion that even for small codes the solver got trapped in a suboptimal solution which is associated to a local optimum of the objective variable, the number of words of the error correcting code. So we linearized the model to guarantee that the solver will converge always to the global optimum. The second approach is the more straightforward but it implies the use of so many indexes as the double of the length of the code. In the second approach, with a more complex model, we reach a solution where the number of indexes is equal to the length of the code and in a third approach we developed an alternative very tricky approach where we keep constant the number of words and maximize the minimum Hamming distance. We compare the four MILP solutions with some code generation problems and we reach the conclusion that the second approach is the best MILP model. Nevertheless even with this solution when the length of the words increases, and so the search space explodes, the runtimes got prohibitive even when we impose the constraint of constant weight words or constant composition words, in the case of ternary codes.