A Study Of Constraint Consistency And Solving Technology Based On Residual Supports

Attention on the research of Constraint Satisfaction Problem (CSP) has beenincreasing in recent years. As an important abstract model of real world’s problems,CSP is used in many fields, such as scheduling, hardware design and certification,molecular biology and natural language processing. There are three parts in a CSP: afinite set of variables, a finite set of domain associated with variables and a finite setof constraints among variables. A solution of one CSP is that every variable has avalue from its domain and constraints among these variables should be satisfied. Tofind one or more solutions to a CSP is NP-hard. However, many solving algorithmsfor CSPs have been proposed in decades. MAC (Maintaining arc consistency)Algorithm is one of the most widely used algorithms, which is based on theBacktracking Search. In order to improve the efficiency of solutions, consistencytechnology, which is an important preprocessing to CSPs, is embedded intoprocedures of solving.Some values in variables’ domain are removed by consistency technology asthey are impossible to be part of the solution. In this way, the searching space of thesolving are reduced greatly, and much redundant search is avoided as well.Arc consistency is one kind of the oldest and most famous consistencytechnology. This paper is about the study of solving algorithms of CSP based on arcconsistency. A new arc consistency algorithm is proposed on its unique properties.When it is embedded into MAC, a new solving algorithm comes out. Our work is asfollows:(1) The concept of residual supports was proposed in AC3rm by ChristopheLecoutre and Fred Hemery. In AC3rm, a residual support, or residue, is a support thathas been stored during a previous execution of the procedure which determines if a value is supported by a constraint. When the value of a variable needs to find asupport, its residual which is more likely to be a valid support will be checked first. InACrmE, the improved algorithm we proposed, the residue is kept in suppR. At thesame time, we exploit multidirectionality of supports in constraints, and introduce anew array, denoted suppL, to store supports. The new array will store every validsupport in constraint checking. When checking the consistency of a variable, everyvalue in its domain must to be tested whether it has at least one support. The residuewill be checked first. If it is invalid, supports in the array suppL will be tested. If theyare all invalid, we have to return to the variable’s domain and search for a new validsupport from scratch. As the possibility of being valid supports is decreasing in thesethree stages, much work on constraint checking could be reduced.(2)In solving algorithms for CSPs, variable ordering heuristics attract muchattention. And we give a new algorithm combining variable and value orderingheuristics-----MACrmE. ACrmE plays a central part in MACrmE. The supports inMACrmE’s array suppL may be all valid. There may be several arrays in differentconstraints for one variable’s value. The sum of all the value’s arrays size, denotedcount, to a certain extent reflects the possibility of the value being a part of the finalsolution. The greater the sum is, the higher the probability. So our value orderingheuristic is based on count. If one value’s count is bigger than others’ in the variable’sdomain, it is thought to be more important. And it has priority to be assigned to thisvariable. At last, the experimental results clearly show that our new algorithm hashigher efficiency.