Making the Breakout Algorithm Complete Using Systematic Search

1 Introduction

The breakout algorithm is an efficient, local search algorithm for solving Constraint Satisfaction Problems (CSPs). The roots of the algorithm go back to [Minton et al., 1992] and to [Morris, 1993]. [Minton et al., 1992], developed, a local search algorithm, called min-conflict heuristic, which itera­ tively repairs a given assignment until all conflicts are elimi­ nated. One drawback of the method is that it can get caught in local, non solution minima. Morris eliminated this draw­ back by extending the algorithm with a breakout method, which allows to escape from local, non solution-minima. The strengths of the breakout algorithm are simplicity, robustness, low memory requirement and high efficiency for solving un­ der constrained problems. [Minton et al., 1992] demonstrated the performance superiority of the min-conflict heuristic by solving large-scale scheduling problems; it performed by or­ ders of magnitude better than traditional backtracking tech­ niques. However, the major weak point of the algorithm is its incompleteness.

In this paper we present a hybrid algorithm that is complete where we combine a local search algorithm, the breakout algorithm, with a complete search algorithm, backtracking. The combination of the two algorithms compensates each others weakness to deal with under and tightly constrained problems. We discover that the algorithm combination also leads to synergies. The weight information from the breakout algorithm can locate and order hard or unsolvable subprob­ lems and guide backtracking by a fail-first variable order. In addition, we introduce a weight sum constraint that can be used to identify unsolvable subproblems of a certain size.

2 The Scheme

When a problem contains an unsolvable subproblem, we ob­ serve that the average constraint weight of a constraint be­ longing to an unsolvable subproblem is higher than the aver­ age constraint weight of the problem. In addition, the smaller the unsolvable subproblem, the higher the average constraint weight. This observation is supported by Lemma 1:

Lemma 1: After increasing the weights n times, the sum of the constraint weights Wpk of an unsolvable subproblem Pk with k constraints must be greater than or equal to n + k.

Proof: If a subproblem is unsolvable, then in every break­ out step, one or more of the subproblem constraints is always violated, thus every time the algorithm is caught in a local non solution minimum, one or more of the corresponding weights must be increased. The lower bound of w p k can be derived by assuming that in every breakout step only one constraint is violated.

By applying Lemma I we can define a weight sum con­ straint, which is extremely useful for tracing unsolvable sub­ problems of different sizes.

Definition 1 (Weight sum constraint for an unsolvable subproblem Pk): According to Lemma 1, in an unsolvable subproblem Pk consisting of k constraints after n breakout steps, the following condition

is satisfied, where c; are all the constraints of the constraint set Cpk of the subproblem Pk.

The weight sum constraint is a powerful tool for pruning the search for unsolvable subproblems. For example, if we search for an unsolvable subproblem of size 3, we only have to consider the constraints whose weight sum is greater n+3.

We also observe that the average constraint weight of an unsolvable subproblem of size k is higher than that of an un­ solvable subproblem of size k + s (s > 0). This is due to the fact that violations cycle over the constraint graph and the less constraints are available, the greater the average con­ straint weight value. This is demonstrated in Figure 1, con­ taining two unsolvable subproblems of size 3 and 6. After n= 1 00 breakout steps, the average constraint weight of the subproblem of size 3 is approximately n/3 + 1 =34 and for the subproblem of size 6, it is n/6 + 1 = 18. Sorting the vari­ ables according to increasing constraint weights, orders the subproblem of size 3 before the subproblem of size 4, and thus separates the two.

These observations inspired us to use the constraint weight information for localizing potentially unsolvable subprob­ lems and to derive a fail-first variable ordering heuristic for backtracking. In this heuristic, variables are sorted so that the constraints with the highest weights are treated first.

2.1 Hybrid Solver BOBT

We have implemented this scheme into a hybrid algorithm (BOBT), where we combine the breakout algorithm (BO) with backtracking (BT). In this algorithm, we first execute BO and terminate if no solution is available after a bounded number of breakout steps. Then we derive a fail-first vari­ able order from the constraint weights and the graph structure and start backtrack search. BT will then either prove that the problem is unsolvable, or return a solution. This method guar­ antees the completeness of the hybrid algorithm. In the case where we find an unsolvable subproblem, we terminate the al­ gorithm and give a failure explanation by returning the min­ imal unsolvable subproblem. The minimal unsolvable sub­ problem is computed from the unsolvable subproblem using the technique described in [Faltings, 2002].

3 Experiments and Results

For testing the scheme, we generated a large set of 10,000 random graph 3-colouring problems according to the method described in [Davenport et.al. 1995]. The generated problem graphs consisted of 30 variables with a connectivity of 2-6. The ratio of solvable to unsolvable problems is 1: 1. Figure 2 shows the results of the experiments. We show the num­ ber of constraint checks for the three algorithms, BO, BT and BOBT on a logarithmic scale over the graph connectivity. For unsolvable problems, we bound the maximum number of it­ erations for the BO to 4.37 · 10 5 .

4 Conclusion

The main contribution of this paper is the presented hybrid scheme that combines the breakout algorithm with a system­ atic search method, backtracking, and results in a new algo­ rithm that is complete. In the scheme we use the constraint weight information of the breakout algorithm to identify hard and unsolvable subproblems of increasing sizes and derive in combination with the graph structure a fail-first variable or­ der for a backtracking algorithm. With our results we prove, that the new hybrid search scheme performs extremely well. BOBT needs orders of magnitude less constraint checks than BO and BT. In the future we plan to extend the scheme by identifying the ordered set of all unsolvable sub problems in order to perform a spectral analysis that gives us the distribu­ tion of unsolvable subproblems for random graph colouring problems.