Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems
| Autor: | Merve Bodur, Moira MacNeil |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) FOS: Computer and information sciences Dimension (graph theory) General Engineering 010103 numerical & computational mathematics 0102 computer and information sciences 01 natural sciences 010201 computation theory & mathematics Simple (abstract algebra) Optimization and Control (math.OC) Computer Science - Data Structures and Algorithms Constraint programming Decomposition (computer science) FOS: Mathematics Data Structures and Algorithms (cs.DS) 0101 mathematics Realization (systems) Integer programming Mathematics - Optimization and Control Mathematics Integer (computer science) |
| DOI: | 10.48550/arxiv.1907.12468 |
| Popis: | 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 [Formula: see text] 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|