Abstract
Discretizable distance geometry problems (DDGPs) constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. Finding such vertex orders is an essential step to identify and solve DDGPs. Here we look for discretization orders that minimize an indicator of the size of the search tree. This paper sets the ground for exact solution of the optimal discretization order problem by proposing two integer programming formulations and a constraint generation procedure for an extended formulation. We discuss some theoretical aspects of the problem and numerical experiments on protein-like instances of DDGP are also reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., Bourne, P.: The protein data bank. Nucleic Acids Res. 28, 235–242 (2000)
Cassioli, A., Gunluk, O., Lavor, C., Liberti, L.: Discretization vertex orders in distance geometry. Discrete Appl. Math. 197, 27–41 (2015)
Gonçalves, D.S., Mucherino, A.: Optimal partial discretization orders for discretizable distance geometry. Int. Trans. Oper. Res. 23(5), 947–967 (2016). doi:10.1111/itor.12249
Gouveia, L., Pesneau, P.: On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48(2), 77–89 (2006). doi:10.1002/net.20122
Grötschel, M., Jünger, M., Reinelt, G.: A Cutting plane algorithm for the linear ordering problem. Oper. Res. 32(6), 1195–1220 (1984). doi:10.1287/opre.32.6.1195. http://www.jstor.org/stable/170944. http://pubsonline.informs.org/doi/abs/10.1287/opre.32.6.1195
Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33(1), 43–60 (1985). doi:10.1007/BF01582010
Lavor, C., Lee, J., John, A.L.S., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. 6(4), 783–796 (2012). doi:10.1007/s11590-011-0302-6
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52(1), 115–146 (2012). doi:10.1007/s10589-011-9402-6
Liberti, L., Lavor, C., Maculan, N.: A branch-and-prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15(1), 1–17 (2008). doi:10.1111/j.1475-3995.2007.00622.x
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56, 3–69 (2014)
Miller, C., Tucker, A., Zemlin, R.: Integer programming formulations and the travelling salesman problems. J. ACM 7, 326–329 (1960)
Mucherino, A.: MD-jeep: a software for distance geometry. http://www.antoniomucherino.it/en/mdjeep.php
Saxe, J.B.: Embeddability of weighted graphs in \(k\)-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, Monticello, IL, pp. 480–489 (1979)
Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Inf. 6(2), 171–185 (1976). doi:10.1007/BF00268499
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Omer, J., Gonçalves, D.S. An integer programming approach for the search of discretization orders in distance geometry problems. Optim Lett 14, 439–452 (2020). https://doi.org/10.1007/s11590-017-1207-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-017-1207-9