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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

20 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationELECO 2021, 25-27 November
Publication statusPublished - 2021

Fingerprint

Dive into the research topics of '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'. Together they form a unique fingerprint.

Cite this