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.

Revised:

Accepted:

Published online:

Keywords: Mathematical Programming, cycle basis, protein conformation

^{1}; Gabriele Iommazzo

^{2}; Carlile Lavor

^{3}; Nelson Maculan

^{4}

@article{OJMO_2023__4__A1_0, author = {Leo Liberti and Gabriele Iommazzo and Carlile Lavor and Nelson Maculan}, title = {Cycle-based formulations in {Distance} {Geometry}}, journal = {Open Journal of Mathematical Optimization}, eid = {1}, pages = {1--16}, publisher = {Universit\'e de Montpellier}, volume = {4}, year = {2023}, doi = {10.5802/ojmo.18}, language = {en}, url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/} }

TY - JOUR AU - Leo Liberti AU - Gabriele Iommazzo AU - Carlile Lavor AU - Nelson Maculan TI - Cycle-based formulations in Distance Geometry JO - Open Journal of Mathematical Optimization PY - 2023 SP - 1 EP - 16 VL - 4 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/ DO - 10.5802/ojmo.18 LA - en ID - OJMO_2023__4__A1_0 ER -

%0 Journal Article %A Leo Liberti %A Gabriele Iommazzo %A Carlile Lavor %A Nelson Maculan %T Cycle-based formulations in Distance Geometry %J Open Journal of Mathematical Optimization %D 2023 %P 1-16 %V 4 %I Université de Montpellier %U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/ %R 10.5802/ojmo.18 %G en %F OJMO_2023__4__A1_0

Leo Liberti; Gabriele Iommazzo; Carlile Lavor; Nelson Maculan. Cycle-based formulations in Distance Geometry. Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 1, 16 p. doi : 10.5802/ojmo.18. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.18/

[1] Edge-swapping algorithms for the minimum fundamental cycle basis problem, Math. Methods Oper. Res., Volume 69 (2009), pp. 205-223 | DOI | MR | Zbl

[2] A theory of network localization, IEEE Trans. Mobile Comput., Volume 5 (2006) no. 12, pp. 1663-1678 | DOI

[3] Cooperative localization for autonomous underwater vehicles, International Journal of Robotics Research, Volume 28 (2009) no. 6, pp. 714-728 | DOI

[4] Is the Distance Geometry Problem in NP?, Distance Geometry: Theory, Methods, and Applications (A. Mucherino; C. Lavor; L. Liberti; N. Maculan, eds.), Springer, 2013, pp. 85-94 | DOI | Zbl

[5] Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., Volume 24 (2009) no. 4, pp. 597-634 | DOI | MR | Zbl

[6] Algorithms for graph rigidity and scene analysis, Algorithms: Proceedings of the European Symposium on Algorithms (G. Di Battista; U. Zwick, eds.) (Lecture Notes in Computer Science), Volume 2832, Springer (2003), pp. 78-89 | MR | Zbl

[7] Partial metric spaces, Am. Math. Mon., Volume 116 (2009) no. 8, pp. 708-718 | DOI | MR | Zbl

[8] An algorithm to enumerate all possible protein conformations verifying a set of distance constraints, BMC Bioinformatics, Volume 16 (2015), pp. 23-38 | DOI

[9] Introduction to IPOPT: A tutorial for downloading, installing, and using IPOPT (2006)

[10] Generic Global Rigidity, Discrete Comput. Geom., Volume 33 (2005), pp. 549-563 | DOI | MR | Zbl

[11] Distance Geometry in linearizable norms, Geometric Science of Information (F. Nielsen; F. Barbaresco, eds.) (Lecture Notes in Computer Science), Volume 10589, Springer (2017), pp. 830-838 | DOI | MR | Zbl

[12] New error measures and methods for realizing protein graphs from distance data, Discrete Comput. Geom., Volume 57 (2017) no. 2, pp. 371-418 | DOI | MR | Zbl

[13] Algorithms for Generating Fundamental Cycles in a Graph, ACM Trans. Math. Softw., Volume 8 (1982) no. 1, pp. 26-42 | DOI | MR | Zbl

[14] Diagonally dominant programming in distance geometry, International Symposium in Combinatorial Optimization (R. Cerulli; S. Fujishige; R. Mahjoub, eds.) (Lecture Notes in Computer Science), Volume 9849, Springer (2016), pp. 225-236 | DOI | MR | Zbl

[15] Sensor network localization, Euclidean distance matrix completions, and graph realization, Optim. Eng., Volume 11 (2010), pp. 45-66 | DOI | MR | Zbl

[16] Matching, Euler tours, and the Chinese postman, Math. Program., Volume 5 (1973), pp. 88-124 | DOI | MR | Zbl

[17] Rigidity, Computation, and Randomization in Network Localization, IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies, 2004, pp. 2673-2684

[18] The AMPL Book, Duxbury Press, 2002

[19] A polynomial time algorithm to find the minimum cycle basis of a regular matroid, 8th Scandinavian Workshop on Algorithm Theory (2002)

[20] Characterizing generic global rigidity, Am. J. Math., Volume 132 (2010) no. 4, pp. 897-939 | DOI | MR | Zbl

[21] Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy2008) (G. Varoquaux; T. Vaught; J. Millman, eds.) (2008), pp. 11-15

[22] Graph Theory, Addison-Wesley Publishing Group, 1969 | DOI

[23] Embedding graphs in surfaces, J. Comb. Theory, Ser. B, Volume 36 (1984), pp. 65-84 | DOI | MR | Zbl

[24] A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph, SIAM J. Comput., Volume 16 (1987) no. 2, pp. 358-366 | DOI | MR | Zbl

[25] ILOG CPLEX 12.9 User’s Manual (2019)

[26] Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, Springer, 2013 no. 5 | DOI

[27] Cycle bases in graphs: characterization, algorithms, complexity, and applications, Comput. Sci. Rev., Volume 3 (2009), pp. 199-243 | DOI | Zbl

[28] Cuts, matrix completions and graph rigidity, Math. Program., Volume 79 (1997), pp. 255-283 | DOI | MR | Zbl

[29] Computational Experience with the Molecular Distance Geometry Problem, Global Optimization: Scientific and Engineering Case Studies (J. Pintér, ed.), Springer, 2006, pp. 213-225 | DOI | Zbl

[30] The discretizable molecular distance geometry problem, Comput. Optim. Appl., Volume 52 (2012), pp. 115-146 | DOI | MR

[31] A matroid view of key theorems for edge-swapping algorithms, Math. Methods Oper. Res., Volume 76 (2012), pp. 125-127 | DOI | MR | Zbl

[32] A new distance geometry method for constructing word and sentence vectors, WWW’20: Companion Proceedings of the Web Conference 2020, Volume 20, ACM Press (2020)

[33] Distance Geometry and Data Science, Top, Volume 28 (220), pp. 271-339 | DOI | MR | Zbl

[34] A cycle-based formulation of the Distance Geometry Problem, Proceedings of 18th Cologne-Twente Workshop (C. Gentile et al., eds.) (AIRO Springer Series), Volume 4, Springer (2020)

[35] Euclidean Distance Geometry: An Introduction, Springer, 2017 | DOI

[36] Open research areas in distance geometry, Open Problems in Optimization and Data Analysis (A. Migalas; P. Pardalos, eds.) (Springer Optimization and Its Applications), Volume 141, Springer, 2018, pp. 183-223 | DOI | MR | Zbl

[37] Counting the number of solutions of ${}^{K}$DMDGP instances, Geometric Science of Information (F. Nielsen; F. Barbaresco, eds.) (Lecture Notes in Computer Science), Volume 8085, Springer (2013), pp. 224-230 | DOI | MR | Zbl

[38] Double Variable Neighbourhood Search with smoothing for the Molecular Distance Geometry Problem, J. Glob. Optim., Volume 43 (2009), pp. 207-218 | DOI | MR | Zbl

[39] Euclidean distance geometry and applications, SIAM Rev., Volume 56 (2014) no. 1, pp. 3-69 | DOI | MR | Zbl

[40] Molecular distance geometry methods: from continuous to discrete, Int. Trans. Oper. Res., Volume 18 (2010), pp. 33-51 | DOI | MR

[41] A good recipe for solving MINLPs, Hybridizing metaheuristics and mathematical programming (V. Maniezzo; T. Stützle; S. Voß, eds.) (Annals of Information Systems), Volume 10, Springer (2009), pp. 231-244

[42] Barvinok’s naive algorithm in distance geometry, Oper. Res. Lett., Volume 46 (2018), pp. 476-481 | DOI | MR | Zbl

[43] A greedy approach to compute a minimum cycle basis of a directed graph, Inf. Process. Lett., Volume 94 (2005), pp. 107-112 | DOI | MR | Zbl

[44] On minimal elementary bipartite graphs, J. Comb. Theory, Ser. B, Volume 23 (1977), pp. 127-138 | DOI | MR | Zbl

[45] Systematic exploration of protein conformational space using a distance geometry approach, J. Chem. Infor. Mod., Volume 59 (2019), pp. 4486-4503 | DOI

[46] A multiplicative weights update algorithm for MINLP, EURO J. Comput. Optim., Volume 5 (2017), pp. 31-86 | DOI | MR | Zbl

[47] Exploiting symmetry properties of the discretizable molecular distance geometry problem, J. Bioinfor. Comput. Biol., Volume 10 (2012), 1242009, 15 pages | DOI

[48] An Algorithm for Finding a Fundamental Set of Cycles of a Graph, Commun. ACM, Volume 12 (1969) no. 9, pp. 514-518 | DOI | Zbl

[49] et al. Python Language Reference, version 3 (2019)

[50] Embeddability of weighted graphs in $k$-space is strongly NP-hard, Proceedings of 17th Allerton Conference in Communications, Control and Computing, 1979, pp. 480-489

[51] Random sampling of large planar maps and convex polyhedra, STOC’99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing, ACM Press (1999), pp. 760-769 | Zbl

[52] Linear Graphs and Electrical Networks, Addison-Wesley Publishing Group, 1961

[53] Angular synchronization by eigenvectors and semidefinite programming, Appl. Comput. Harmon. Anal., Volume 30 (2011), pp. 20-36 | DOI | MR | Zbl

[54] Global Optimization of Mixed Integer Nonlinear Programs: A Theoretical and Computational Study, Math. Program., Volume 99 (2004), pp. 563-591 | DOI | MR | Zbl

*Cited by Sources: *