Research On Adaptive Constraint Solving Methods

The concept of constraint has been used and expanded to the areas of industry and livelihood.As the accelerating of global economy, the theory and application research in constraintprogramming has been paid more and more attention since it was proposed in the late1980s.Constraint programming can be used in industry, agriculture, communication, manufacture,transport, aviation etc. In these areas, constraint can be used in production scheduling, productconfiguration and human management which have actual sense and business values, inreverse, lay the foundation of the research of constraint programming.Constraint satisfaction problem is a key problem of constraint programming, whosekernel is constraint solving. How to find a universally effective constraint solving method is asevere challenge of constraint programming. The traditional solving technology can bedivided as two kinds: search and inference. The deputy of the former is backtrackingalgorithm, and the main methods of the later are variable elimination, tree-decomposition andconsistency technology. With the development of constraint solving, the concept of “adaptive”has been focused on, which has gradually become a spotlight and guided the futuredevelopment. The adaptive constraint solving uses the empiric value which gets in self-searching to guide the following searching. More and more researches get to consider instructure information of problems, and propose some adaptive constraint solving methodswith more adaptability. These modified methods promote the efficiency and intelligence ofalgorithms, but the methods have more capacious development space.The links which are closely related to constraint solving such as branching selection,variable selection, value selection and constraint propagation, etc. are connected with theefficiency of constraint solving seriously. There is no doubt that realizing adaptive in theselinks has become a new improvement way for adaptive constraint solving.After summarizing the basic concepts of constraint and the process of constraint solving,the thesis mainly researches the technologies and methods of adaptive constraint solvingwhich focus on the process of constraint solving itself. These methods which use adaptiveidea are used in every link in constraint solving. We focus on the four kinds of methods:adaptive branching selection constraint solving methods, adaptive variable selectionconstraint solving methods, adaptive value selection constraint solving methods and adaptiveconstraint propagation constraint solving methods. The emphases of the research are thepromoting degree of solving efficiency by adaptation.(1) Adaptive branching selection constraint solving methods: The effect andsignificance of adaptive branching selection to constraint solving are analysis. Based on introduction of existing branching selection strategies, the typical branch strategies arecompared, thus the advantage of adaptive branching strategy is highlighted. Two improvedadaptive branching strategies are proposed. One is the modified strategy of assistantconsultants heuristic, the other is a new adaptive branching solving algorithm:AdaptBranchLVO. After comparing other assistant consultants, the high efficiency of adaptivebranching strategy is proved. By testing multiple typical Benchmarks, the efficiency inconstraint solving of AdaptBranchLVOis validated. We get a result that importing the adaptivebranching strategy to constraint solving is an effective method to the efficiency of constraintsolving.(2) Adaptive variable selection constraint solving methods: Based on the research andcomparison of variable ordering heuristics, the adaptive variable selection method inconstraint solving is proposed. The methods are different from the static or dynamic variableordering heuristics that only use the information of initial and current nodes, which use theinformation of every node from searching tree to help realize the adaptive variable orderingheuristics. By comparing the typical variable ordering heuristics, the idea of the generalizedadaptive variable selection constraint solving is proposed, and it lays the foundation ofcombining it with the adaptive constraint propagation in the later chapters.(3) Aadaptive value selection constraint solving methods: Based on typical valueordering heuristics, the methods of adaptive value selection in constraint solving are discussed.The survivors-first learning adaptive value ordering heuristics are focused on. The methods ofsearching more hopeful values in propagation with low cost are introduced, and the values areused to speed up some special problem solving with the help of heuristics in order to achieveadaptive value selection constraint solving. Furthermore, drawing support from adaptive valueordering heuristics, it combines the adaptive value selection with the adaptive branchingselection. Algorithm AdaptBranchsurvis proposed, and the algorithm is tested to get efficiency.After comparing AdaptBranchsurvand AdaptBranchLVO, AdaptBranchsurvhas an apparentadvantage of improving the efficiency of constraint solving via the experimental result.(4) Adaptive constraint propagation constraint solving methods: With the help ofdiscussing the importance of constraint propagation, the significance of adaptive constraintpropagation is proposed. The constraint solving methods of constraint propagation andadaptation are discussed. This section focuses on two kinds of methods: one is the adaptationbetween two constraint propagation methods, and the other is learning adaptation amongmultiple constraint propagation methods. The former discusses the adaptive constraintpropagation algorithm based on bitwise operations and the adaptive constraint propagationbased on AC and LmaxRPC. The modified algorithm AC_MaxRPC_Bitwise andADAPTAC-LmaxRPCare proposed. The efficiency of these algorithms is proved by Benchmarkstests. The latter realizes learning adaptive constraint propagation among multiple strategieswith the aids of LPP, which paves the way for further study. In the end, it proves the notableperformance of adaptive constraint propagation. With the application of adaptive method to constraint solving, many results have beengotten. More and more teams focus on this area, and develop the area. Our adaptive constraintsolving methods improve the efficiency of constraint solving from a new perspective. Theseadaptive methods help constraint in many links and levels to improve constraint solving, andget more intelligent algorithm.