Research On Constraint Propagation And Consistency Algorithms For Constraint Programming

Constraint programming is an important branch of artificial intelligence.It provides a whole set of solutions from modeling to solving combinatorial optimization problems.Backtracking search algorithm is a complete method to solve constraint programming problems.Its characteristic is that it can give the solution of the problem or prove that it has no solution without limiting the time and space.The backtracking search algorithm continuously selects variables for instantiation and propagates the instantiation through constraint propagation.Constraint propagation filters variable values by performing consistency algorithms.A reasonable constraint propagation method schedules the filtering algorithm to reach a certain level of consistency state,which can effectively help the search algorithm reduce the search space.Thus,the purpose of improving the solution efficiency is achieved.Currently,the main serial constraint propagation methods are arc-oriented,constraint-oriented,and variable-oriented propagation modes.And subject to the complex synchronization problem,the research about parallel constraint propagation is more difficult and the research results are less.The consistency technique removes some variable values that will not appear in the solution after rigorous reasoning.Compared with other combinatorial optimization problem-solving techniques,the consistency technique is a characteristic technique in the direction of constraint programing.Currently,the mainstream consistency techniques include(Generalized)Arc Consistency((G)AC),Max-restricted Path Consistency(Max RPC),and Singleton Arc Consistency(SAC),etc.;mainstream higher-order consistency techniques include Pairwise Consistency(PWC)and Full Pairwise Consistency(f PWC),etc...Different consistency has different pruning capabilities.We distinguish this ability of the consistency by"strong"or"weak".Often,the stronger the consistency,the longer it takes to compute or achieve.Conversely,the shorter the time required.Therefore,proposing efficient consistency and consistency algorithms has been a hot research topic in this direction.In addition,the selection of the problem modeling scheme,the variable instantiation order heuristic,and the partitioning and encoding of the constraint network are also important issues to be considered for improving the solving process efficiency.In this paper,starting with optimizing of constraint propagation,the scheduling mechanism of constraint propagation,the concept and algorithm of consistencises are deep researched.By introducing new theories and data structures,the existing constraint propagation scheme is improved,and then new consistency concepts and algorithms are proposed.The research in this paper aims to improve the execution efficiency of constraint propagation and consistency algorithms,and thus the efficiency of solving constraint programming problems,and the main research contents are as follows:1.An improved method of variable-oriented constraint propagation algorithm is proposed.Arc-oriented,variable-oriented,and constraint-oriented propagation schemes are three classical constraint propagation schemes.Reducing redundant propagation is an important means to optimize constraint propagation.In this paper,we improve the timestamp method and optimize the variable-oriented propagation scheme using a two-stage propagation scheme,which can identify and exclude more redundant propagation.Experimental results show that the efficiency of the constraint propagation algorithm is improved.2.Two parallel constraint propagation schemes:static submission and dynamic submission are proposed.At present,due to the synchronization problem of complex data structures,there are few research on parallel constraint propagation and parallel consistency.This paper presents a new concept and algorithm of parallel consistency based on multi-core CPU computing architecture.The constraint propagation is performed concurrently by using the potential parallel computing capability of multi-core processors without changing the current computing equipment.The proposed parallel consistency ensures the correctness of the parallel constraint propagation algorithm.Experimental results show that,compared with the serial constraint propagation,the parallel constraint propagation improves the efficiency of the original algorithm.3.Two parallel propagators for factor-decomposition encoding(FDE)of constraint network are proposed.Experiments on parallel propagation algorithms show that dynamic submission constraint propagation algorithm has better performance on larger scale problem instances.And FDE makes the original problem easier to solve by adding additional constraints and variables to the original constraint network.Therefore,this paper attempts to speed up the solving process on a larger size FDE constraint network by using the parallel propagation algorithm.The challenge to achieve this goal is to safely rewrite the existing serial algorithm into a parallel one.In this paper,different parallel propagation operators are designed for different types of table constraints using the idea of divide-and-conquer.The final experimental results also demonstrate that this algorithm is the most efficient algorithm for solving the FDE constraint network.4.A new consistency,enhanced forward checking consistency(EFCC),is proposed based on the optimization of forward checking consistency(FCC)using bit representation(i.e.,"bitset").Over the years,research on consistency has never stopped,and balancing the pruning ability and execution time of consistency is the main goal of the research of this field.In this paper,we improve the existing FCC using bit sets and propose EFCC based on it.Experimental results show that,compared with FCC,EFCC has better pruning ability and efficiency compared with the mainstream Arc Consistency.5.A new GAC algorithm for alldifferent constraints based on Word Ram(a bitset model)is proposed.currently,GAC algorithms for alldifferent constraints are improved on the framework of Régin's algorithm.The relevant improvement techniques are incremental matching,phased propagation,priority queueing,assignment optimization,free nodes propagation,SCC splitting computation,early detection and bit representation and bit operation.This paper propoeses All Diff^bitalgorithm,which integrates all the above optimization techniques and further improves some of them.Experimental results show that the All Diff^bit algorithm is stable and performs better than any other algorithms on most of the test instances.In summary,this paper makes an in-depth search of constraint propagation and consistency both theoretically and algorithmically.The specific work includes improving the existing serial constraint propagation scheme,proposing new parallel constraint schemes,proposing a new consistency,and optimizing consistency algorithms.These studies finally improve the efficiency of constraint programming.