The Edge-Strength (ES) problem is a graph labeling problem where the goal is to assign integer labels to the edges of a finite undirected graph in such a way that the maximum sum of labels between any two adjacent edges, known as edge-strength, is minimized. This work introduces the first methods to solve the ES problem exactly and approximately, including two constraint satisfaction problem (CSP) models and a simulated annealing (SAes) metaheuristic. The first CSP model is based on constrained optimization using the AllDifferent global constraint, while the second employs extensional constraints. Computational experiments on 40 standard topology graph instances demonstrate the effectiveness and robustness of these approaches. The CSP models provide exact solutions for smaller instances, while the SAes algorithm efficiently approximates solutions for larger and complex graphs. These contributions advance the state-of-the-art in solving the ES problem and pave the way for further research.