« Advances and New Challenges on Branch-and-Prune Algorithm
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.