EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

532. Distance geometry without the graph

Invited abstract in session TA-4: Topics in Mixed Integer Programming and Nonconvex Optimization, stream MINLP.

Tuesday, 8:30-10:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Leo Liberti
CNRS LIX, Ecole Polytechnique

Abstract

The Distance Geometry Problem (DGP) is as follows: draw a weighted graph in a K-dimensional Euclidean space (K given) so that vertices are points and edges are segments with the same length as their weights. In many applications the input is not quite a graph, but simply a list of distance values without their adjacencies. Thus, the assignment of distance values to graph edges must be carried out concurrently to the realization in the K-dimensional space. This is known as the unassigned DGP (uDGP). There is a natural MINLP formulation for the uDGP, which is very hard to solve even for tiny instances. We present alternative formulations as well as relaxations, restrictions, and other approximating reformulations.

Keywords

Status: accepted


Back to the list of papers