Research On Search Technology Of Constraint Programming

The serial propagation mode that enforces the generalized arc consistency(GAC)on table constraint network is an important branch of the research of constrained programming search technology.The mode consists of two parts: the serial propagation algorithm and the serial filtering algorithm.The serial propagation algorithm will execute the serial filtering algorithm that enforces the GAC on the table constraint.In order to further improve the efficiency of serial propagation mode,this paper focuses on parallel computing.Parallel computing is the ability to process multiple parts of a problem simultaneously without changing the expected result.With the development of parallel processing ability of computer,the research on the combination of constraint programming and parallel computing has become a focus of attention,namely parallel constraint programming.Research on parallel constraint programming can be roughly divided into the following categories: parallel propagation,search space division,combination algorithms and problem decomposition,etc.Among them,parallel propagation refers to the parallel execution of filtering algorithms on constraints,and its research significance lies in using parallel computing to improve the efficiency of constraint propagation.This paper proposes a parallel propagation mode that enforces temporary generalized arc consistency(TGAC)on table constraint network.This mode is based on a multi-core CPU and consists of two parts: the parallel propagation algorithm and the parallel filtering algorithm.The parallel propagation algorithm uses the thread pool to parallelly call the parallel filtering algorithm that enforces the table constraint TGAC.This paper presents the reliability proof of the parallel propagation mode,that is,the parallel propagation mode also enforces the table constraint network GAC.The worst time complexity of the parallel propagation mode is also analyzed.After comparing with the worst time complexity of the serial propagation mode,I think that the parallel propagation mode is faster than the serial propagation mode on instances with longer average filtering time.The final experimental results also confirm the above conclusion.The control experiment was carried out on 22 series.The serial propagation mode and the parallel propagation mode were tested respectively by using the backtracking search algorithm.In the serial propagation mode,CT and STRbit are used respectively as the serial filtering algorithm.In the parallel propagation mode,the parallel filtering algorithm uses PCT and PSTRbit respectively.The parallelism of the thread pool is set to 2,4,and 6 in turn.The final experimental results show that the parallel propagation mode is faster than the serial propagation mode on 17 series,and achieves a speed-up ratio ranging from 1.4 to 3.4 on most series.