Constraint optimization problems offer a way to obtain a global solution for a given problem. However, the promise of finding a global solution often comes at the cost of significant time and computational resources. Greedy search, local search, and cluster identification methods represent alternative approaches, which can quickly lead to local optima. In our previous work presented at the 16th International Conference on Agents and Artificial Intelligence (ICAART) 2024 [19], we introduced new methods to combine constraint programming with greedy search and clustering methods in the context of the traveling salesman problem. In this paper, we explore the advantages of incorporating greedy search and local search, which can be seen as a clustering technique in this case, into constraint optimization methods without forsaking the pursuit of a global solution. The global search process is initially designed to behave similarly to a greedy search or local search. Compared to [19], we now considered more diverse greedy and iterated local search techniques as a new clustering method. Our approach aims to achieve two key objectives: first, to accelerate the process of finding of an initial solution, and second, to ensure that this solution possesses a high level of optimality. Our approach is an enhancement of the general branch-and-bound method in constraint programming. Finally, we validate our results using the traveling salesman problem as a case study.