Research On The Constraint Propagation Based Constraint Solving Methods

Constraint is one of our familiar concepts, for there are plenty of examples about constraints in our everyday study lives. For instance, the three angles of a triangle sum to 180 degree, the relative position of the scroller in the window scroll-bar must reflect the position of the current text in the underlying document. Formally, a constraint is simply a logical relation among several unknowns, each taking a value in a given domain. Constraint Programming (CP) is the methodology on programming and problem solving which was founded on the work circling the concept of constraints, and its central goal is constructing the reasoning and computing system for constraint-based combinatorial optimization problems. As an emergent software technology, CP has the advantage of declarative description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling, not surprisingly, it has been identified by the ACM (Association for Computing Machinery) as one of the strategic directions in computer research. When evaluating it, the famous American computer scientist Eugene C. Freuder said,"Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it."In CP Community, it is generally recognized that the constraint idea comes from 1963 when Sutherland introduces Sketchpad, the first interactive graphical interface that solved geometric constraints. After that, a series of research on geometry constraints processing came forth, but the genuine CP theory hadn't taken shape yet. The CP was founded as the extension of the logic programming (LP). In the middle of 1980, with the failure of the Japan fifth generation computer planning, the research of logic programming fell into low tide, meanwhile, there was much work on the research on logic programming combining with constraint solving in succession, whose practice was focused on the extension from tree constraints to constraints on arbitrary domain. In 1987, Jaffar presented a general model after analyzing the previous related work. His finding leads to the paper titled by"Constraint Logic Programming", which became the seminal paper of Constraint (Logic) Programming. Now, with the absorption from constraint satisfaction problems solving algorithms of artificial intelligence (AI) and the mathematical programming theory of operations research, it has been one of the most important and active research directions in computer science.According to the book"constraint processing"written by Rina Dechter, who is Profossor of college of information and computer science, California university, USA, the technology of solving CSPs is divided into two kinds: search and inference. The main algorithm of search is backtracking, and inference contains variable elimination and consistency technology. Those two algorithms have their own advantages and disadvantages. Inference is fit for solving lower density constraint network, and when the density of constraint network grow higher the time and space needed maybe increase exponentially. The worse time complexity of search algorithms is exponential, but the space needed is polynomial. In order to optimize the performance of the entire solving system, inference must be combined with search framework. With the cooperation of inference and search, time of search and space taken by inference can decrease. The searching algorithms follow the idea of generate and test, which derived from method to solve combinatorial optimization problems. It systematically generates and tests each possible combination of variable assignment, and checks whether it satisfies all the constraints. Other search algorithms can be regarded as the expansion forms of this method. Search algorithms are required inference technology to solve practical problems effectively. Backtracking searching algorithms needs consistency check to reduce the search space; Local searching requires tabu list and the corresponding inference methods to avoid traping in a local minima time after time; artificial immunity usually added to genetic algorithms; Branch-and-bound algorithms use variable and value heuristics as well as methods of evaluating bounds; So how to add suitable inference technologies to the specific search strategy is the key factor of designing a constraint satisfaction algorithm. At present, consistency check, tree decomposition, bucket elimination, and counting solutions for variable and value heuristics are the main inference technologies, which are widely used in contrant solving.In addition, as far as the constraint solving tools are concerned, the high efficiency and expressiong power are two hard principles, which lead to the importance of the research on constraint satisfaction problems solving algorithms and new constraint models. The algorithms consist the backtracking based systematic search and its improvement; consistence checking techniques and its extension; constraint propagation approaches; variables and values selection heuristic strategies; randomized algorithms such as genetic algorithm and artificial neural networks for constraint optimization problems. Nowadays, there are the new trends of collaborative solving with diversiform algorithms. Furthermore, the Randomized Constraint Satisfaction Problems (RCSP) generation model originated from SAT provides the impartial algorithm testing, and the improvement and the adaptability enhancement are the urgent work. As to models, for the sake of handling the over constrained satisfaction problems, on the basis of the Fuzzy CSP, there is much work on soft CSP, which includes the probability CSP, weight CSP, hierarchical CSP, semiring-based CSP and valued CSP. All these work strengthen the express power of the CP. Meanwhile, the related research on algorithms improvement is hotpot and the integration of constraint satisfaction models with reasoning approaches is a new question for discussion.In this thesis we present our work circling the constraint solving and constraint propagation.The detailed contents fall into the following aspects:(1) After discussing the development of arc consistency algorithms and some relevant concepts, we introduced some arc consistency algorithms with general constraint form, such as AC-1, AC-3, AC-4, AC-6, AC-7, AC-2000, AC-2001, AC-3.1, AC-3.2 and AC-3.3. Then we presented our experimental results and compared all the algorithms with our experiments. By comparison, we considered AC-2001(AC-3.1) to be the best algorithm both before searching and during searching. At last, we briefly explained the application of the arc consistency algorithm.(2) Firstly we analysed the processing of constraint propagation, then we represented parameterized description of the arc consistency propagation depth by using variable domain retraction proportion, proposed an arc consistency algorithm whose propagation degree is controllable, meanwhile we studied the constraint solving algorithm's efficiency under different parameters. The algorithm is implemented under the platform of"Mingyue 1.0", and the results show that, the key factor that impacts the efficiency of the algorithm is constraint propagation degree, so through adjusting the control parameter, the algorithm can be 3 to 4 times faster.(3)We examined existing notions and techniques, and then proposed a new algorithm---BiSAC-2 to enforce Bidirectional singleton arc consistency in constraint network. Finally, we also prove its soundness and completeness. BiSAC-2 has a property of reducing the scale of problems like BiSAC-1. However, it only needs the small numbers of maintaining arc consistency and reaches the fixpoint quickly. So the efficiency can be improved correspondingly. In our experiments on random CSPs our algorithm BiSAC-2 only requires less time than conventional BiSAC-1.(4) A dynamic variable ordering heuristic and look-ahead strategy inspired from centralized constraint programming technique are combined with concurrent backtrack search, which can be performed in distributed environment. Experiments on randomly generated DisCSPs demonstrate that the proposed algorithm can drastically improve performance of concurrent search both on speed and on stability.(5) In this part, our research results have been embedded in the "Mingyue" constraint solving tool, in which we used randomly generated problems bound to test the compatibility of various algorithms and its arc and a variety of intelligent algorithms backtrack hybrid combination of algorithms, experiments show that our algorithm will further enhance the "Mingyue" the performance of constraint solving tool.