14ème JEAN, 23 mars 2017
Jeremy OMER
:
Discrétisation du problème de distance géométrique : complexité et résolution exacte.
The distance geometry problem (DGP) consists in searching for embeddings of a positively weighted undirected graph in a given euclidean space. Stated otherwise, for some given k, it searches for a set of points of R^k, such that the weights of the edges are the same as the euclidean distances between the corresponding pairs of points. A large number of instances of the DGP can be discretized and solved by enumeration using a branch-and-prune approach. This presentation focuses on the process of discretization, which has strong connections with classical problems of combinatorial optimization such as the travelling salesman and the linear ordering problems. We first formalize the discretization problem and show that it is NP-complete. We then compare two compact and one extended integer programming formulations. Although excellent primal bounds can be computed by a greedy heuristic, the integer programming approach cannot prove optimality for instances with more than an approximate hundred vertices. We thus design a specific branch-and-bound algorithm, which reveals to be better adapted to the problem.
