  


Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems
Moira MacNeil (m.macneilmail.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 Kdimensional space such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The socalled discretization assumptions reduce the search space of the realization to a finite discrete one which can be explored via the branchandprune (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 stateoftheart 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 ) Citation: Download: [PDF] Entry Submitted: 07/27/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  