Speaker
Description
Extremal combinatorial structures bear fundamental relevance in coding theory and various other applications. Their study consists in solving hard computational problems. Many of these are good candidates for to be solved on Ising-based quantum annealers for their limited size. Compared to other common benchmark problem classes these are not based on pseudorandomness, and most primal solution improvements can contribute several disciplines including mathematics, combinatorics, or physics.
We consider mixed Hamming packings: maximal subsets of a given Hamming space over a mixed alphabet keeping that every selected codeword pair has at least a minimum fixed given distance, using mixed integer programming models. There are many known and efficient approaches to the problem in the literature, including clique-reformulation, specific exhaustive search algorithms, etc. Our contribution is based on mixed integer programming which was not frequently used before as it was not competitive with other methods. We overcome this issue by introducing a reduction technique and further constraints based on structural properties. In particular, we introduce a presolving column reduction technique based on our idea of adopting the notion of contact graphs motivated by the Tammes-problem.
We prove that for every mixed Hamming-space over alphabets having minimal cardinality 3, there is a maximal Hamming-packing in them with a connected contact graph with minimal vertex degree at least 2. As a corollary of this lemma we can introduce a new type of linear constraints for the MILP model, which significantly simplify the solution. We present computational results for a number of particular instances: in case of binary-ternary problems we obtain best known results in competitive computational time. Preliminary results calculated using quantum annealers will also be presented.
