Feasibility check for the distance geometry problem: an application to molecular conformations.
Saved in:
| Title: | Feasibility check for the distance geometry problem: an application to molecular conformations. |
|---|---|
| Authors: | Agra, Agostinho1 aagra@ua.pt, Figueiredo, Rosa2 rosa.figueiredo@univ-avignon.fr, Lavor, Carlile3 clavor@ime.unicamp.br, Maculan, Nelson4 maculan@cos.ufrj.br, Pereira, António1 antoniop@ua.pt, Requejo, Cristina1 crequejo@ua.pt |
| Source: | International Transactions in Operational Research. Sep2017, Vol. 24 Issue 5, p1023-1040. 18p. 1 Diagram, 3 Charts. |
| Subjects: | Feasibility studies, Distance geometry, Molecular conformation, Integer programming, Constraint programming |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of International Transactions in Operational Research is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 123283331 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Feasibility check for the distance geometry problem: an application to molecular conformations. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Agra%2C+Agostinho%22">Agra, Agostinho</searchLink><relatesTo>1</relatesTo><i> aagra@ua.pt</i><br /><searchLink fieldCode="AR" term="%22Figueiredo%2C+Rosa%22">Figueiredo, Rosa</searchLink><relatesTo>2</relatesTo><i> rosa.figueiredo@univ-avignon.fr</i><br /><searchLink fieldCode="AR" term="%22Lavor%2C+Carlile%22">Lavor, Carlile</searchLink><relatesTo>3</relatesTo><i> clavor@ime.unicamp.br</i><br /><searchLink fieldCode="AR" term="%22Maculan%2C+Nelson%22">Maculan, Nelson</searchLink><relatesTo>4</relatesTo><i> maculan@cos.ufrj.br</i><br /><searchLink fieldCode="AR" term="%22Pereira%2C+António%22">Pereira, António</searchLink><relatesTo>1</relatesTo><i> antoniop@ua.pt</i><br /><searchLink fieldCode="AR" term="%22Requejo%2C+Cristina%22">Requejo, Cristina</searchLink><relatesTo>1</relatesTo><i> crequejo@ua.pt</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Transactions+in+Operational+Research%22">International Transactions in Operational Research</searchLink>. Sep2017, Vol. 24 Issue 5, p1023-1040. 18p. 1 Diagram, 3 Charts. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Feasibility+studies%22">Feasibility studies</searchLink><br /><searchLink fieldCode="DE" term="%22Distance+geometry%22">Distance geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Molecular+conformation%22">Molecular conformation</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Constraint+programming%22">Constraint programming</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Transactions in Operational Research is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=123283331 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1111/itor.12283 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 18 StartPage: 1023 Subjects: – SubjectFull: Feasibility studies Type: general – SubjectFull: Distance geometry Type: general – SubjectFull: Molecular conformation Type: general – SubjectFull: Integer programming Type: general – SubjectFull: Constraint programming Type: general Titles: – TitleFull: Feasibility check for the distance geometry problem: an application to molecular conformations. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Agra, Agostinho – PersonEntity: Name: NameFull: Figueiredo, Rosa – PersonEntity: Name: NameFull: Lavor, Carlile – PersonEntity: Name: NameFull: Maculan, Nelson – PersonEntity: Name: NameFull: Pereira, António – PersonEntity: Name: NameFull: Requejo, Cristina IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 09696016 Numbering: – Type: volume Value: 24 – Type: issue Value: 5 Titles: – TitleFull: International Transactions in Operational Research Type: main |
| ResultId | 1 |
