Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems

Moira MacNeil () and Merve Bodur ()
Additional contact information
Moira MacNeil: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 1, 297-314

Abstract: Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in R K such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G . The so-called discretization assumptions reduce the search space of the realization to a finite discrete one, which can be explored via the branch-and-prune (BP) algorithm. Given a discretization vertex order in G , the BP algorithm constructs a binary tree where the nodes at a layer provide all possible coordinates of the vertex corresponding to that layer. The focus of this paper is on finding optimal BP trees for a class of discretizable DGPs. More specifically, we aim to find a discretization vertex order in G that yields a BP tree with the least number of branches. We propose an integer programming formulation and three constraint programming formulations that all significantly outperform the state-of-the-art cutting-plane algorithm for this problem. Moreover, motivated by the difficulty in solving instances with a large and low-density input graph, we develop two hybrid decomposition algorithms, strengthened by a set of valid inequalities, which further improve the solvability of the problem. Summary of Contribution: We present a new model to solve a combinatorial optimization problem on graphs, MIN DOUBLE, which comes from the highly active area of distance geometry and has applications in a wide variety of fields. We use integer programming (IP) and present the first constraint programming (CP) models and hybrid decomposition methods, implemented as a branch-and-cut procedure, for MIN DOUBLE. Through an extensive computational study, we show that our approaches advance the state of the art for MIN DOUBLE. We accomplish this by not only combining generic techniques from IP and CP but also exploring the structure of the problem in developing valid inequalities and variable fixing rules. Our methods significantly improve the solvability of MIN DOUBLE, which we believe can also provide insights for tackling other problem classes and applications.

Keywords: distance geometry; discretization order; integer programming; constraint programming; decomposition algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1039 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:1:p:297-314

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().