69. Maximal Hamming packing search: contact graph-based model MILP improvements
Invited abstract in session WC-3: Mixed Integer Programming I, stream Discrete Optimization.
Wednesday, 10:00 - 11:30Room: C 104
Authors (first author is the speaker)
| 1. | Péter Naszvadi
|
| Department of Quantum Optics and Quantum Information, HUN-REN Wigner Research Centre for Physics | |
| 2. | Mátyás Koniorczyk
|
| Department of Quantum Optics and Quantum Information, HUN-REN Wigner Research Centre for Physics |
Abstract
We consider mixed Hamming packings: maximal subsets of a given Hamming space over a mixed alphabet keeping that every selected codeword pair has a minimum 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 particular results for a number of particular instances: in case of binary-ternary problems we obtain best known results in competitive computational time.
Keywords
- Mixed integer nonlinear optimization
- Complexity and efficiency of optimization algorithms
- Nature inspired methods and algorithms
Status: accepted
Back to the list of papers