Optimization Online


Constraint Programming Approaches to the Discretizable Molecular Distance Geometry Problem

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

Abstract: The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow to discretize the search space of DGP instances. In this paper, we study the Discretizable Molecular Distance Geometry Problem whose feasible solutions provide a discretization scheme for the DGP. We propose three constraint programming formulations as well as a set of checks for proving infeasibility, domain reduction techniques, symmetry breaking constraints and valid inequalities. Our computational results indicate that our formulations outperform the state-of-the-art integer programming formulations, both for feasible and infeasible instances.

Keywords: Molecular distance geometry, discretization order, DMDGP, constraint programming

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Other )


Download: [PDF]

Entry Submitted: 07/29/2019
Entry Accepted: 07/29/2019
Entry Last Modified: 07/31/2019

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