New linear codes with prescribed group of automorphisms found by heuristic search

In this paper, we present a new heuristic algorithm for solving certain systems of Diophantine inequalities. A variant which involves Monte-Carlo search is also applyable to more general problems. Our goal was the construction of point sets in PG$(k-1,q)$ with fixed cardinality and small maximal intersection number with the lines. These points sets correspond to $k$-dimensional linear codes over $\mathbb F_q$ with high minimum distance. We obtained them by prescribing a certain nontrivial subgroup of GL$(k,q)$ to be contained in their automorphism group. Following a method which was first introduced by Kramer and Mesner in the 1970s, this allows a strong reduction in the size of the corresponding Diophantine systems. Doing so we found a lot of new record breaking linear codes for the cases $q = 2, 3, 4, 5, 7, 8, 9$ from which at least $6$ are optimal.