Combinatorial optimization algorithms for the design of codes: a survey

Code design problems are central in information theory and have applications in different fields ranging from telecommunications to bioinformatics. In this paper we survey the results achieved in the last decades for different types of codes, covering constant weight binary codes, quaternary codes and permutation codes. The focus of the survey is mainly on approaches based on combinatorial optimization and graph theory that have gained popularity in the last decade and are likely to play a central role in the codes design research in the forthcoming years, possibly in a fashion where the new ideas are hybridized with the older contributions.