The Discretizable Distance Geometry Problem (DDGP) is a feasibility problem, based on determining total orders in graphs. We consider an optimality-based DDGP problem, where the goal is to find a discretization vertex order in the input graph that yields a branch-and-prune tree with the least number of branches. We propose an integer programming formulation and three constraint programming formulations that all significantly outperform the state of the art. Moreover, we develop two hybrid decomposition algorithms, strengthened by a set of valid inequalities, which further improve the solvability of the problem.