The Research On Inference Technology Of Constraint Solving

There are constraints which widely exist in all kinds of fields of scientific research and living in the real world. We always encounter various combinatorial optimization problems connected with the constraints, especially those problems with high business price, such as routing, scheduling, timetabling, design and configuration, and matching. In operational research, handwork or tradition methods were used to solve these problems in the past, but generating irrationality solution and running long time are their limitations.Finding a good or optimal solution to these problems always require searching in a possibly exponentially sized solution space. In order to obtain reasonable efficiency, some important and usefull constraints can be abstracted from the problems, which give some conditions to satisfy for pruning the search space. Constraint is an extensive concept. Generally, it is viewed as restriction in possibility space. Simplifing the real world situation into a system of constraints about idealized objects and using this system to understand the behavior of the real world is the category of constraint programming. Constraint programming is the study of computational systems based on constraints and a powerful method onmodeling, problem resolution and programming.The study of constraint programming, in early time, was focused on backtrack and intelligent improved algorithms. To overcome the limited capacity of solving and simple backtrack algorithm which can not be improved significantly, consistency with revolutionary import on constraint solving and a representational technique of constraint inference is proposed again. It is playing an invaluable role in speeding up solving process and reducing solving space. Also, it has an indispensable way in global constraint, soft constraint satisfaction problem, quantified constraint satisfaction problem and dynamic constraint satisfaction problem. The main contridutions are listed as follows:(1) Propose a new constraint propagation algorithm based on fail first principle, which improves the practical time efficiency through backtracking in advance due to the earlier found of variables which contain null values. When implemented under the platform of"Mingyue1.0", the experiments showed the practical time efficiency is increased by 40 percent through using fail first principles compared with the original one; propose a new singleton consistency --- Singleton Sub-Problem Arc Consistency (SSAC) and present an algorithm SSAC to enforce it. We prove that the pruning efficiency of SSAC is far better than SAC, even if it is not stronger as SAC.(2) Propose the multi-value propagation theory and prove that k-single propagation is equivalent with 1-multi-value propagation. Based on this, we present AC theory of multi-value propagation and combine it and SAC to form a new multi-value propagation algorithm SAC-MP. Besides, we also prove the soundness and completeness of it. Our experiments show the efficiency of our algorithm SAC-MP is 2-3 times of the existing SAC-SDS and SAC-3 algorithm. We propose a notion of entirety singleton consistency and the algorithm to enforce it, and then analyze the time and space complexity and correctness. Based on this, we present a new preprocessing algorithm SAC-ESC based on ESC, and prove its correctness. Furthermore we use the divide-conquer strategy to automatically adapt to domain partition of various problems. Experiments show the efficiency of our algorithm SAC-ESC is 3---20 times of the existing SAC-SDS and SAC-3.(3) Propose two new consistency algorithms called Pre-AC and Pre-AC* applied during searching, which are based on the performance on an improvement of consistency during preprocessing and information extraction. We presents two new searching algorithms called BT+MPAC and BT+MPAC* by embedding those two consistency algorithms into the BT framework respectively. After proving the correctness of Pre-AC and Pre-AC*, this paper analyzes their time complexity. It is evidently that the complexities of Pre-AC and Pre-AC* are O(nd) and O(ed2) respectively. Experiments show efficiency of our algorithms is 2---50 times higher of that of MAC. We present a value ordering searching algorithm named MAC_MPV. It sorts values of every variable's domain according to the probability of the value leading to a solution. So this order enforces the algorithm to give priority to search the space containing a solution with greater possibility. In this way, the efficiency of algorithm can be improved.(4) We study the bidirectional singleton arc consistency and make contributions as followings: we propose a new algorithm---BiSAC-2, which only needs fewer the numbers of maintaining arc consistency and reaches the fixpoint more quickly. So the efficiency can be improved correspondingly, In order to save space, BiSAC-DF and BiSAC-DP are proposed. Besides, for special circumstances, we show BiSAC-DF admits a worst-case time complexity in O(en2d4) and a best one in O(en2d3) when the problem is an already BiSAC, while BiSAC-DP also has the same best one when the tightness is small.