Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/18405
Title: Feasibility check for the distance geometry problem: an application to molecular conformations
Author: Agra, Agostinho
Figueiredo, Rosa
Lavor, Carlile
Maculan, Nelson
Pereira, António
Requejo, Cristina
Keywords: Distance geometry problem
Graph embedding
Integer programming
Constraint programming
Issue Date: Sep-2017
Publisher: Wiley
Abstract: The distance geometry problem (DGP) consists in finding an embedding in a metric space of a given weighted undirected graph such that for each edge in the graph, the corresponding distance in the embedding belongs to a given distance interval. We discuss the relationship between the existence of a graph embedding in a Euclidean space and the existence of a graph embedding in a lattice. Different approaches, including two integer programming (IP) models and a constraint programming (CP) approach, are presented to test the feasibility of the DGP. The two IP models are improved with the inclusion of valid inequalities, and the CP approach is improved using an algorithm to perform a domain reduction. The main motivation for this work is to derive new pruning devices within branch-and-prune algorithms for instances occurring in real applications related to determination of molecular conformations, which is a particular case of the DGP. A computational study based on a set of small-sized instances from molecular conformations is reported. This study compares the running times of the different approaches to check feasibility.
Peer review: yes
URI: http://hdl.handle.net/10773/18405
DOI: 10.1111/itor.12283
ISSN: 1475-3995
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
AgraFigueiredoLavorMaculanPereiraRequejo-ITOR2017.pdfMain article531.57 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.