We study solution-space structure and solution-finding algorithms of a representative hard random constraint satisfaction problem with growing domains known as Model RB. Using rigorous methods, we show that solutions are grouped into disconnected clusters before the theoretical satisfiability phase transition point. Using the cavity method, it is shown that the entropy density obtained by belief propagation (BP) on random Model RB instances, which corresponds well to the analytical results, vanishes as the control parameter (constraint tightness) approaches the satisfiability threshold. From an algorithmic point of view, we find that reinforced BP, which performs much better than all existing algorithms, allows us to find solutions efficiently for instances in the regime that is very close to the satisfiability transition. These results also can shed light on the effectiveness of BP reinforcement on problems with a large number of states.

• Received 28 June 2011

DOI:https://doi.org/10.1103/PhysRevE.85.016106