Optimization Online


Discretization vertex orders in distance geometry

Andrea Cassioli (andrea.cassioli***at***mosek.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Carlile Lavor (clavor***at***ime.unicamp.br)
Leo Liberti (leoliberti***at***gmail.com)

Abstract: When a weighted graph is an instance of the Distance Geometry Problem (DGP), certain types of vertex orders (called discretization orders) allow the use of a very efficient, precise and robust discrete search algorithm (called Branch-and-Prune). Accordingly, finding such orders is critically important in order to solve DGPs in practice. We discuss three types of discretization orders, the complexity of determining their existence in a given graph, and the inclusion relations between the three order existence problems. We also give three mathematical programming formulations of some of these ordering problems.

Keywords: molecular conformation, protein, DDGP, DMDGP, re-order, Branch-and-Prune

Category 1: Combinatorial Optimization (Other )

Category 2: Applications -- Science and Engineering (Biomedical Applications )

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 08/23/2014
Entry Accepted: 08/23/2014
Entry Last Modified: 08/28/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society