EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Mathematical Programming
- Computational Biology, Bioinformatics and Medicine
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers