Research On The Extension And Application Of Mistral Solver

Constraint Satisfaction Problem(CSP) has been an important research field in artificial intelligence(AI). And the related technologies are widely applied to the configuration, scheduling and combinatorial problem, etc. Constraint programming is the key to CSP research, and the solution efficiency has been the international hot spot in the field of artificial intelligence.At present, there have been some very mature general constraint solvers, such as Ilog Solver, Gecode, Choco, Mistral, etc. These solvers have good efficiency by applying the mature solution techniques, and are widely used by the CSP research groups.These mainstream CSP solvers are used as a comparison in Mini Zinc CSP solver competition every year, and they all have good efficiency. But most of the search mechanism of CSP solver does not contain the adaptive component, that is, for most of the CSP solver, we can only choose a search strategy to solve, but cannot automatically according to the problem of structure to choose the appropriate heuristic or filtering algorithm.Most of the CSP solver is consists of three main components: 1) modeling language; 2) a series of filtering algorithms for specified constraints; 3) search strategy. Modeling language is provided by the solver can model CSP, including the definition of domians, variables and constraints, and so on. Filtering algorithms are based on the theory of constraint network, the main idea is to delete incompatible values. Search strategies are to search the solution through the guidance in search space. For most mature CSP solvers, they have achieved some major heuristics for constraint propagation and backtracking algorithms. For CSP solver Gecode and Choco, there have been the user manuals to learn the structure of the solver to use. But there is not a user manual to analyze system structure of Mistral solver.The main contents of this paper are as follows:(1) We mainly have a detailed analysis about the structure of Mistral solver. Firstly, we introduce the background of the Mistral solver. And, we analyze the main structure of Mistral solver; Secondly, we introduce variable ordering heuristic of Mistral solver, and its implementation mechanism and several important classes and functions associated with it. Thirdly, we introduce value ordering heuristic implementation mechanism. Finally, we detail the implementation mechanism of constraint propagation in Mistral solver.(2) We extend the constraint propagation method on Mistral solver. Firstly, we add max RPC3, max RPC3 rm, lmax RPC3, lmax RPC3 rm filtering technologies to the Mistral solver, and elaborate on the details. Secondly, we add the adaptive parameterized consistency algorithms p-max RPC and apx-max RPC, then we present a parameterized improved version of solving binary CSPs apx-max RPC-COS, and test results show that the improved algorithm has a good efficiency on structural problem. Finally, we add adaptive constraint propagation method based on multi armed bandits to the Mistral.(3) We extend the search strategy of the Mistral solver. Firstly, we introduce TLBO algorithm. Secondly, we present an adaptive algorithm of ETLBO, and test results show that the improved algorithm improve the efficiency of solving the ETLBO well. Then, we present a discrete TLBO algorithm based on the improved algorithm. Finally, we apply the discrete algorithm to the solve max CSPs. And make a comparison with the solver abscon109-pfc and abscon109-epfc, test results show that the algorithm has a very big potential and research value in solving the max CSPs.