Optimization Online


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

Moira MacNeil (m.macneil***at***mail.utoronto.ca)
Merve Bodur (bodur***at***mie.utoronto.ca)

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 K-dimensional space 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 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.

Keywords: Distance geometry, discretization order, integer programming, constraint programming, decomposition algorithms

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Other Topics (Other )


Download: [PDF]

Entry Submitted: 07/27/2019
Entry Accepted: 07/27/2019
Entry Last Modified: 02/26/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society