New formulations for the Kissing Number Problem

Determining the maximum number of D-dimensional spheres of radius r that can be adjacent to a central sphere of radius r is known as the Kissing Number Problem (KNP). The problem has been solved for two, three and very recently for four dimensions. We present two nonlinear (nonconvex) mathematical programming models for the solution of the KNP. We solve the problem by using two stochastic global optimization methods: a Multi Level Single Linkage algorithm and a Variable Neighbourhood Search. We obtain numerical results for two, three and four dimensions.