Super Solutions of the Model RB

In many combinatorial optimization and decision problems, what people concern is to find solutions of minimal costs. In practice, however, such optimal solutions can be very brittle in that if the value of one variable becomes unavailable, repairing this solution leads to a great increase in its final cost. Therefore, the concept of super solution is introduced to formalize a solution with a certain degree of robustness or stability. To quantify the robustness, (a, b)-super solution was introduced to constraint programming in [3]. Specifically, an (a,b)-super solution is one in which if the values assigned to a variables are no longer available, the solution can be repaired by assigning these variables withanew values and at most b other variables. Over the past years, random models of constraint satisfaction problems (CSPs) have been intensively studied. Initially, four "standard" models known as models A, B, C and D [4, 2] have been introduced to generate random binary CSP instances.