The widespread use of optimization methods in the design phase of District Heating Networks is currently limited by the availability of scalable optimization approaches that accurately represent the network. In this paper, we compare and benchmark two different approaches to non-linear topology optimization of District Heating Networks in terms of computational cost and optimality gap. The first approach solves a mixed-integer non-linear optimization problem that resolves the binary constraints of pipe routing choices using a combinatorial optimization approach. The second approach solves a relaxed optimization problem using an adjoint optimization approach, and enforces a discrete network topology through penalization. Our benchmark shows that the relaxed penalized problem has a polynomial computational cost scaling, while the combinatorial solution scales exponentially, making it intractable for practical-sized networks. We also evaluate the optimality gap between the two approaches on two different District Heating Network optimization cases. We find that the mixed-integer approach outperforms the adjoint approach on a single-producer case, but the relaxed penalized problem is superior on a multi-producer case. Based on this study, we discuss the importance of initialization strategies for solving the optimal topology and design problem of District Heating Networks as a non-linear optimization problem.