« search calendars« DIMACS Workshop on Optimization in Distance Geometry

« Advances and New Challenges on Branch-and-Prune Algorithm

June 27, 2019, 11:20 AM - 12:00 PM

Location:

DIMACS Center

Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.

Michael Souza, Federal University of Ceará

The Branch-and-Prune algorithm (BP) and its variations are among the most cited methods to solve molecular discretizable distance geometry problems (DMDGP). The BP-like algorithms represent the DMDGP by a graph whose nodes are ordered in such a way that a solution can be constructed iteratively. Previous results indicated that finding a BP-order was a NP-hard problem, but in this presentation we show that it can be done in polynomial time. An interesting property of DMDGP is that all solutions can be generated from any other applying partial reflections. We also introduce a new application of this result using it to reduce the number of float point operations required by BP to calculate a solution to DMDGP. Finally, we define a NP-hard problem whose solution identifies the minimal number operations needed to solve the DMDGP with BP algorithm.

The Branch-and-Prune algorithm (BP) and its variations are among the most cited methods to solve molecular discretizable distance geometry problems (DMDGP). The BP-like algorithms represent the DMDGP by a graph whose nodes are ordered in such a way that a solution can be constructed iteratively. Previous results indicated that finding a BP-order was a NP-hard problem, but in this presentation we show that it can be done in polynomial time. An interesting property of DMDGP is that all solutions can be generated from any other applying partial reflections. We also introduce a new application of this result using it to reduce the number of float point operations required by BP to calculate a solution to DMDGP. Finally, we define a NP-hard problem whose solution identifies the minimal number operations needed to solve the DMDGP with BP algorithm.