Cycle-based formulations in Distance Geometry
The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension $K$, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematica...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2023-01-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204999084310528 |
|---|---|
| author | Liberti, Leo Iommazzo, Gabriele Lavor, Carlile Maculan, Nelson |
| author_facet | Liberti, Leo Iommazzo, Gabriele Lavor, Carlile Maculan, Nelson |
| author_sort | Liberti, Leo |
| collection | DOAJ |
| description | The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension $K$, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, the formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures. |
| format | Article |
| id | doaj-art-9330e8a848eb4fe6ac13b974bcafdbb8 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-9330e8a848eb4fe6ac13b974bcafdbb82025-02-07T14:02:56ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602023-01-01411610.5802/ojmo.1810.5802/ojmo.18Cycle-based formulations in Distance GeometryLiberti, Leo0Iommazzo, Gabriele1Lavor, Carlile2Maculan, Nelson3LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris, 91128 Palaiseau, FranceZuse Institute Berlin, Berlin, 14195, GermanyIMECC, University of Campinas, BrazilCOPPE, Federal University of Rio de Janeiro (UFRJ), BrazilThe distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension $K$, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, the formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/Mathematical Programmingcycle basisprotein conformation |
| spellingShingle | Liberti, Leo Iommazzo, Gabriele Lavor, Carlile Maculan, Nelson Cycle-based formulations in Distance Geometry Open Journal of Mathematical Optimization Mathematical Programming cycle basis protein conformation |
| title | Cycle-based formulations in Distance Geometry |
| title_full | Cycle-based formulations in Distance Geometry |
| title_fullStr | Cycle-based formulations in Distance Geometry |
| title_full_unstemmed | Cycle-based formulations in Distance Geometry |
| title_short | Cycle-based formulations in Distance Geometry |
| title_sort | cycle based formulations in distance geometry |
| topic | Mathematical Programming cycle basis protein conformation |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/ |
| work_keys_str_mv | AT libertileo cyclebasedformulationsindistancegeometry AT iommazzogabriele cyclebasedformulationsindistancegeometry AT lavorcarlile cyclebasedformulationsindistancegeometry AT maculannelson cyclebasedformulationsindistancegeometry |