Research On Structure Analysis And Application Of Choco Solver

Artificial intelligence is an important subject in the field of computer science, and constraintsatisfaction problem which is an important branch of Artificial intelligence plays an importantrole in real life and scientific research.In real life and science, there are many practicalproblems can be abstracted into a constraint satisfaction problems, such as aircraft sequencing,nurse scheduling, tournament scheduling, product configuration, job scheduling and otherissues. Constraint satisfaction problems are profoundly affecting and changing people’s lives.Arc consistency techniques are important constraint propagation technologies. Arcconsistency techniques applied in the process of solving can greatly reduce the search spaceand search time. After years of development, there are AC3, AC2001, AC3rm, SAC, STR,maxRPC and a series of partial arc consistency techniques. Backtracking is a completesolving method. In order to reduce the search space in the solving process, there has been acorresponding variable ordering heuristics and value ordering heuristics. The emergence ofthese technologies has promoted the development of constraint satisfaction problems.In order to promote the development of constraint satisfaction problems, numerousresearch teams organized an annual international constraint conference which had become animport meeting in artificial intelligence. In order to create a common platform for solving,researchers have released choco,mistral, gecode and other series of solvers. And these solvershave been excellent application economic and biological fields.These solvers merge the popular consistency and heuristic techniques and optimize theprocesses of instances reading, domain, variable domain representation and storage, nogoods,restart strategy and memory management. Whist these measures have improved the solvingefficiency. In order to facilitate constraint solver research and development, the researchersorganized the annual contest constraint solver.The content of the paper is as follows:First, analyze and summarize the structure, design, basic usage and application of Choco.Summarize the application of other researchers on mining and joint solving whit other solversSecond, the use of the n-queens problem solving choco, set partitioning, task schedulingand other issues, while comparing different heuristic for solving efficiency benchmark. Third, extend the heuristic mid with mistral, and compare the performances of thisheuristic with other heuristics.Fourth, the running time, the number of variables, maximum domain size and thenumber of constraint per instance in58class which sums to2225instances are calculated bymistral and choco. First, gets the average running time per class and label per class with thefaster solver. Then, train the dataset with k-neighbor algorithm. Finally, predict the solver ofeach instance with k-neighbor algorithm.