License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.21
URN: urn:nbn:de:0030-drops-120950
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12095/
Go to the corresponding LIPIcs Volume Portal

Antypov, Dmytro ; Deligkas, Argyrios ; Gusev, Vladimir ; Rosseinsky, Matthew J. ; Spirakis, Paul G. ; Theofilatos, Michail

Crystal Structure Prediction via Oblivious Local Search

pdf-format:
LIPIcs-SEA-2020-21.pdf (0.9 MB)

Abstract

We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand, usually easy to implement, but they can be slow in practice. On the other hand, the more sophisticated approaches perform well in general, however almost all of them have a large number of parameters that require fine tuning and, in the majority of the cases, chemical expertise is needed in order to properly set them up. In addition, due to the chemical expertise involved in the parameter-tuning, these approaches can be biased towards previously-known crystal structures. Our contribution is twofold. Firstly, we formalize the Crystal Structure Prediction problem, alongside several other intermediate problems, from a theoretical computer science perspective. Secondly, we propose an oblivious algorithm for Crystal Structure Prediction that is based on local search. Oblivious means that our algorithm requires minimal knowledge about the composition we are trying to compute a crystal structure for. In addition, our algorithm can be used as an intermediate step by any method. Our experiments show that our algorithms outperform the standard basin hopping, a well studied algorithm for the problem.

BibTeX - Entry

@InProceedings{antypov_et_al:LIPIcs:2020:12095,
  author =	{Dmytro Antypov and Argyrios Deligkas and Vladimir Gusev and Matthew J. Rosseinsky and Paul G. Spirakis and Michail Theofilatos},
  title =	{{Crystal Structure Prediction via Oblivious Local Search}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12095},
  URN =		{urn:nbn:de:0030-drops-120950},
  doi =		{10.4230/LIPIcs.SEA.2020.21},
  annote =	{Keywords: crystal structure prediction, local search, combinatorial neighborhood}
}

Keywords: crystal structure prediction, local search, combinatorial neighborhood
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: The source code of this project can be found in https://bit.ly/2w4zG1L.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI