Yet another breakout inspired infeasible subset detection in constraint satisfaction problem

摘要

In [1], Eisenberg and Faltings proposed a breakout [2] based hybrid approach to detect infeasible subset (IS) in constraint satisfaction problems. In this paper, we adopted this algorithm as a preprocessing procedure to reduce the over-constrained constraint satisfaction problem. Then a three procedures hybrid approach is employed to detect the irreducible infeasible subset (IIS) of identified IS. The approach consists of three procedures - critical constraint locating, critical constraint extending and critical constraint subsets satisfiability testing. The extent of the subproblem is based on the first located critical constraint and is ended while it cannot be satisfied by a Tabu Search incomplete search algorithm. Finally, the MAC (Maintaining Arc Consistency during search) method provides the infeasibility of the extracted subproblem. By adopting a hybrid approach, the tractability of satisfiability testing of real world applications becomes realistic. The experimental results demonstrate the effectiveness of the method.