Jeremy Omer, INSA Rennes

Abstract

Discretizable distance geometry problems (DDGPs) constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In dimension K, a discretization order is such that each one of the vertices with rank greater than K + 1 has at least K adjacent predecessors, called references. Finding such vertex orders is an essential step to identify and solve DDGPs. Here we look for discretization orders that minimize one of two distinct indicators of the size of the search tree. With both indicators, the key is to have a small number of vertices with exactly K references. In the first part of the presentation, we will consider a generalization of this discretization problem and show that it is strongly NP-Hard with both indicators, even if K is fixed to any value larger than or equal to one. In the second part, I will talk about two different solution methods for this problem. One is a cutting plane algorithm based on an extended integer programming formulation. The other is a branch-and-bound algorithm making use of a previously developed greedy algorithm that is guaranteed to return a discretization order when one exists. Finally, I will discuss a numerical comparison of the different approaches on a benchmark based on distance geometry instances.

Video