A symmetry-based splitting strategy for discretizable distance geometry problems

Felipe Fidalgo (), Douglas S. Gonçalves (), Carlile Lavor (), Leo Liberti () and Antonio Mucherino ()
Additional contact information
Felipe Fidalgo: Federal University of Santa Catarina
Douglas S. Gonçalves: Federal University of Santa Catarina
Carlile Lavor: University of Campinas
Leo Liberti: École Polytechnique
Antonio Mucherino: Université de Rennes 1

Journal of Global Optimization, 2018, vol. 71, issue 4, No 4, 717-733

Abstract: Abstract Discretizable distance geometry problems consist in a subclass of distance geometry problems where the search space can be discretized and reduced to a tree. Such problems can be tackled by applying a branch-and-prune algorithm, which is able to perform an exhaustive enumeration of the solution set. In this work, we exploit the concept of symmetry in the search tree for isolating subtrees that are explored only one time for improving the algorithm performances. The proposed strategy is based on the idea of dividing an original instance of the problem into sub-instances that can thereafter be solved (almost) independently. We present some computational experiments on a set of artificially generated instances, with exact distances, to validate the theoretical results.

Keywords: Protein structure determination; Partial reflection; Decomposition; Branch-and-prune (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0610-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:71:y:2018:i:4:d:10.1007_s10898-018-0610-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0610-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().