Open Journal of Mathematical Optimization

Cycle-based formulations in Distance Geometry
Leo Liberti1; Gabriele Iommazzo2; Carlile Lavor3; Nelson Maculan4
1 LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris, 91128 Palaiseau, France
2 Zuse Institute Berlin, Berlin, 14195, Germany
3 IMECC, University of Campinas, Brazil
4 COPPE, Federal University of Rio de Janeiro (UFRJ), Brazil
Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 1, 16 p.

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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.18
Classification: 90C26, 51K05
Keywords: Mathematical Programming, cycle basis, protein conformation
Leo Liberti 1; Gabriele Iommazzo 2; Carlile Lavor 3; Nelson Maculan 4

1 LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris, 91128 Palaiseau, France
2 Zuse Institute Berlin, Berlin, 14195, Germany
3 IMECC, University of Campinas, Brazil
4 COPPE, Federal University of Rio de Janeiro (UFRJ), Brazil
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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] E. Amaldi; L. Liberti; F. Maffioli; N. Maculan Edge-swapping algorithms for the minimum fundamental cycle basis problem, Math. Methods Oper. Res., Volume 69 (2009), pp. 205-223 | DOI | MR | Zbl

[2] J. Aspnes; T. Eren; D. Goldenberg; S. Morse; W. Whiteley; R. Yang; B. Anderson; P. Belhumeur A theory of network localization, IEEE Trans. Mobile Comput., Volume 5 (2006) no. 12, pp. 1663-1678 | DOI

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

[4] N. Beeker; S. Gaubert; C. Glusa; L. Liberti 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] P. Belotti; J. Lee; L. Liberti; F. Margot; A. Wächter Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., Volume 24 (2009) no. 4, pp. 597-634 | DOI | MR | Zbl

[6] A. Berg; T. Jordán 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] M. Bukatin; R. Kopperman; S. Matthews; H. Pajoohesh Partial metric spaces, Am. Math. Mon., Volume 116 (2009) no. 8, pp. 708-718 | DOI | MR | Zbl

[8] A. Cassioli; B. Bordeaux; G. Bouvier; A. Mucherino; R. Alves; L. Liberti; M. Nilges; C. Lavor; T. Malliavin 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] R. Connelly Generic Global Rigidity, Discrete Comput. Geom., Volume 33 (2005), pp. 549-563 | DOI | MR | Zbl

[11] C. D’Ambrosio; L. Liberti 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] C. D’Ambrosio; Ky Vu; C. Lavor; L. Liberti; N. Maculan 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] N. Deo; G. M. Prabhu; M. S. Krishnamoorthy Algorithms for Generating Fundamental Cycles in a Graph, ACM Trans. Math. Softw., Volume 8 (1982) no. 1, pp. 26-42 | DOI | MR | Zbl

[14] G. Dias; L. Liberti 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] Y. Ding; N. Krislock; J. Qian; H. Wolkowicz Sensor network localization, Euclidean distance matrix completions, and graph realization, Optim. Eng., Volume 11 (2010), pp. 45-66 | DOI | MR | Zbl

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

[17] T. Eren; D. Goldenberg; W. Whiteley; Y. Yang; A. Morse; B. Anderson; P. Belhumeur Rigidity, Computation, and Randomization in Network Localization, IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies, 2004, pp. 2673-2684

[18] R. Fourer; D. Gay The AMPL Book, Duxbury Press, 2002

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

[20] S. Gortler; A. Healy; D. Thurston Characterizing generic global rigidity, Am. J. Math., Volume 132 (2010) no. 4, pp. 897-939 | DOI | MR | Zbl

[21] A. Hagberg; D. Schult; P. Swart 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] F. Harary Graph Theory, Addison-Wesley Publishing Group, 1969 | DOI

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

[24] J. D. Horton 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] IBM ILOG CPLEX 12.9 User’s Manual (2019)

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

[27] T. Kavitha; C. Liebchen; K. Mehlhorn; D. Michail; R. Rizzi; T. Ueckerdt; K. Zweig Cycle bases in graphs: characterization, algorithms, complexity, and applications, Comput. Sci. Rev., Volume 3 (2009), pp. 199-243 | DOI | Zbl

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

[29] C. Lavor; L. Liberti; N. Maculan 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] C. Lavor; L. Liberti; N. Maculan; A. Mucherino The discretizable molecular distance geometry problem, Comput. Optim. Appl., Volume 52 (2012), pp. 115-146 | DOI | MR

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

[32] L. Liberti 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] L. Liberti Distance Geometry and Data Science, Top, Volume 28 (220), pp. 271-339 | DOI | MR | Zbl

[34] L. Liberti; G. Iommazzo; C. Lavor; N. Maculan 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] L. Liberti; C. Lavor Euclidean Distance Geometry: An Introduction, Springer, 2017 | DOI

[36] L. Liberti; C. Lavor 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] L. Liberti; C. Lavor; J. Alencar; G. Abud 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] L. Liberti; C. Lavor; N. Maculan; F. Marinelli 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] L. Liberti; C. Lavor; N. Maculan; A. Mucherino Euclidean distance geometry and applications, SIAM Rev., Volume 56 (2014) no. 1, pp. 3-69 | DOI | MR | Zbl

[40] L. Liberti; C. Lavor; A. Mucherino; N. Maculan Molecular distance geometry methods: from continuous to discrete, Int. Trans. Oper. Res., Volume 18 (2010), pp. 33-51 | DOI | MR

[41] L. Liberti; N. Mladenović; G. Nannicini 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] L. Liberti; K. Vu Barvinok’s naive algorithm in distance geometry, Oper. Res. Lett., Volume 46 (2018), pp. 476-481 | DOI | MR | Zbl

[43] C. Liebchen; R. Rizzi 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] L. Lovász; M. Plummer On minimal elementary bipartite graphs, J. Comb. Theory, Ser. B, Volume 23 (1977), pp. 127-138 | DOI | MR | Zbl

[45] T. Malliavin; A. Mucherino; C. Lavor; L. Liberti Systematic exploration of protein conformational space using a distance geometry approach, J. Chem. Infor. Mod., Volume 59 (2019), pp. 4486-4503 | DOI

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

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

[48] K. Paton 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] G. van Rossum et al. Python Language Reference, version 3 (2019)

[50] J. Saxe 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] G. Schaeffer 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] S. Seshu; M. B. Reed Linear Graphs and Electrical Networks, Addison-Wesley Publishing Group, 1961

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

[54] M. Tawarmalani; N. V. Sahinidis 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: