Research On The Problem Structure Oriented Constraint Solving Algorithms

Lots of daily problems and academic problems can be abstracted as constraint satisfactionproblems (CSP) and lots of CSP solving techniques have been used to solve them, such as nqueens problem, shop scheduling problem, routes selecting problem and map coloringproblem. As constraint satisfaction problems are widely used, more in-depth research ofconstraint satisfaction problems has started. And it has become a very hot direction in the fieldof artificial intelligence. Constraint Programming(CP) International Conference hold annuallyhas become a very import conference in AI field. And even some companies have launchedsome commercial constraint solvers, such as ILog, that have played a significant role in thepractical application.Judging whether a CSP has a solution is NP-hard. Researchers have proposed a varietyof techniques to improve the efficiency of solving CSP in order to effectively solve the CSP.The basic algorithm for solving CSP is backtracking search, which is a complete algorithm. Itcan make sure that if a CSP’s solution exists, you will certainly be able to find it, or provingthat there is no solution for the CSP. Other solving techniques, such as constraint propagationand variable ordering heuristic, can be applied in the framework of backtracking search.In constraint propagation, the most important and the most famous technology iscompatibility technology. It can efficiently remove the redundant values of the variables inconstraint network. So the search space will be reduced significantly, and the efficiency willbe improved. Recently researchers have proposed a lot of compatibility technologies, whichhave different ability to remove redundant values, and spend different time and space as theyare running. In general, if the ability of a compatibility algorithm to delete redundant value isstronger, then the running time and space spent is greater. Arc compatibility algorithm is nowthe most popular compatible algorithm, not only because it can reasonably remove redundantvariable, but also it has a good time complexity and occupy less system resources.Although there are so much CSP solving technology being proposed, but solving CSP isstill relatively difficult. Because the structure of CSP may be very complex, and the individualtechnologies often achieve good solving efficiency only on some class of CSP instances, butnot perfect on other CSP instances. Part of the reason may be that the interactions of theexisting technologies are not understood well. So it needs to select the correct solving technologies when solving a CSP, which requires a thorough insight. The adaptive constraintsolving is proposed for hoping that the CSP solver can automatically selects CSP solvingtechnologies based on the property of the instances’structures, or that several suitable CSPsolving technologies can be switched between them in the process of solving.This paper mainly focuses on constraint propagation and search heuristics. A lighter arcconsistency algorithm has been proposed based on current algorithms. Random explorationtechnology also has been improved. The main contents of this paper are as follows:(1) A new maxRPC algorithm and its light version which are more portable and moresuitable for searching are proposed based on the exiting maxRPC algorithm. These algorithmsdo not require complex data structures and discard the date structures, LastAC and LastPC, inmaxRPC3. Every time when we want to find supports, the searching is started from the firstvalue of the variable’s domain. The results show that compared to both the existing maxRPCalgorithms alone, and with value ordering heuristics, the new proposed maxRPC algorithmsare very competitive.(2) It is a good quest of adaptive constraint propagation that random probing is used toconstraint propagation. In the preprocessing stage, the constraint information which is used toclassify the constraints is obtained from random probing. Then different propagating methodsare used on different constraints in the process of searching. We make a more in-depth studyof random probing, and improve its coordinate system of constraint information clustering.Our experiments are launched on multiple coordinate systems and constraints sorting methods.And we explore the efficiency of random probing with variable ordering heuristics. Theexperimental results show that, in some instances, the efficiency of solving with the variableordering heuristic has improved.(3) Using solution counting estimation as a heuristic method is recently proposed. In thecounting-based branching heuristic algorithms, the solution counting estimation are used asheuristic information for selecting variables and values. It can be used not only as variableordering heuristics or value ordering heuristics alone, but also for directly selecting a variablevalue pairs. In this article we realize solution counting algorithm for Alldifferent constraint.