New formulations for the Kissing Number Problem

Sergei Kucherenko; Pietro Belotti; Leo Liberti; Nelson Maculan

doi:10.1016/j.dam.2006.05.012

New formulations for the Kissing Number Problem

Sergei Kucherenko
, Pietro Belotti
, Leo Liberti
, Nelson Maculan

Imperial College London
Carnegie Mellon University
Instituto de Biofisica da UFRJ

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	1837-1841
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	155
Issue number	14
DOIs	https://doi.org/10.1016/j.dam.2006.05.012
Publication status	Published - 1 Sept 2007

Keywords

Global optimization
Multi-level Single Linkage
NLP
Sphere packing
Stochastic algorithm
Variable Neighbourhood Search

Access to Document

10.1016/j.dam.2006.05.012

Cite this

@article{69d42fa46e554be183cad21966ccd0af,

title = "New formulations for the Kissing Number Problem",

abstract = "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.",

keywords = "Global optimization, Multi-level Single Linkage, NLP, Sphere packing, Stochastic algorithm, Variable Neighbourhood Search",

author = "Sergei Kucherenko and Pietro Belotti and Leo Liberti and Nelson Maculan",

year = "2007",

month = sep,

day = "1",

doi = "10.1016/j.dam.2006.05.012",

language = "English",

volume = "155",

pages = "1837--1841",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

number = "14",

}

TY - JOUR

T1 - New formulations for the Kissing Number Problem

AU - Kucherenko, Sergei

AU - Belotti, Pietro

AU - Liberti, Leo

AU - Maculan, Nelson

PY - 2007/9/1

Y1 - 2007/9/1

N2 - 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.

AB - 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.

KW - Global optimization

KW - Multi-level Single Linkage

KW - NLP

KW - Sphere packing

KW - Stochastic algorithm

KW - Variable Neighbourhood Search

U2 - 10.1016/j.dam.2006.05.012

DO - 10.1016/j.dam.2006.05.012

M3 - Article

AN - SCOPUS:34547681743

SN - 0166-218X

VL - 155

SP - 1837

EP - 1841

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 14

ER -

New formulations for the Kissing Number Problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this