TY - GEN

T1 - Technical Note: From the Generation of New Optimal and Quasi-Optimal Constant Weight Ternary Codes Obtained with a MILP Model to a New Definition of the Johnson Bound

AU - Fonseca, José Barahona da

PY - 2021

Y1 - 2021

N2 - In this paper we improve almost all lower bounds of ternary codes with minimum Hamming distance d=3 and words with constant weight, w, varying between 3 and 5, and length, n, varying between 5 and 10 published in [1] using a Mixed Integer Linear Programming (MILP) model and implemented with the Cplex [2] algorithm. In almost all cases we obtained the optimal solution. In all very few cases where we did not obtain the optimal solution the so called Best Possible Integer Solution given by the Cplex algorithm coincided with the Johnson Bound [1]. We also verified that our results improved almost all the ones published in [3]. Finally we describe the Mixed Integer Linear Model that we used and, for our knowledge, it is the first MILP model to obtain ternary optimal codes published in the literature. We also mention the previous two MILP models that failed to obtain good results or even converge to any solution. As main research vectors for future work we identify the mathematical demonstration of the empirical evidence of the equivalence between the Johnson bound and the Cplex output Best Possible Integer Solution of our MILP model and the use of our MILP model by Cplex developers as a benchmark to improve this MILP models Solver.

AB - In this paper we improve almost all lower bounds of ternary codes with minimum Hamming distance d=3 and words with constant weight, w, varying between 3 and 5, and length, n, varying between 5 and 10 published in [1] using a Mixed Integer Linear Programming (MILP) model and implemented with the Cplex [2] algorithm. In almost all cases we obtained the optimal solution. In all very few cases where we did not obtain the optimal solution the so called Best Possible Integer Solution given by the Cplex algorithm coincided with the Johnson Bound [1]. We also verified that our results improved almost all the ones published in [3]. Finally we describe the Mixed Integer Linear Model that we used and, for our knowledge, it is the first MILP model to obtain ternary optimal codes published in the literature. We also mention the previous two MILP models that failed to obtain good results or even converge to any solution. As main research vectors for future work we identify the mathematical demonstration of the empirical evidence of the equivalence between the Johnson bound and the Cplex output Best Possible Integer Solution of our MILP model and the use of our MILP model by Cplex developers as a benchmark to improve this MILP models Solver.

M3 - Conference contribution

BT - ELECO 2021, 25-27 November

ER -