Decomposition Algorithms Of Constraint Satisfaction Problems And Application In Solving Configuration Problems

Constraint Satisfaction Problem is an important and fundamentalproblemintheareaofartificialintelligence.TheresearchaboutConstraintSatisfaction Problem has been being popular in recent 30 years. Theabsolutely most constraint satisfaction problems existed are based onclassic Constraint Satisfaction Problems, that is, it begins with the sets ofvariables and researches how to obtain values ofvariables bythe relationsamongthevariables. AlthoughthedefinitionaboutConstraintSatisfactionProblem is very simple, it can effectively describe many applicationproblems in the area of artificial intelligence, such as computer vision,diagnosis,logicprogramming,theanalysisanddesigningofcircuitry,andthe product configuration which has been emphasized in recent 10 years.This paper describes and researches various methods on constraintdecomposition, implements the CaT (Cut-And-Traverse) decomposition,andappliesthedecompositionmethodtoexistedconfigurationsystem.In general, although CSPs are in NP-complete, decompositiontechniques borrowed from the area of databases have been used to reducethe complexity of computation. The basic principle is to decomposeConstraint Satisfaction Problem into the sub-problems which areorganized in a tree structure. The sub-problems are then solvedindependently, and the solutions of everysub-problem are propagated in abacktrack-free manner along the tree to yield a solution to the initial CSP.In early time of Artificial intelligence, people had controlled thecomplexity of problems by decomposing. Of course, it cannot improveabout the worst time complexity, but for the massive problems, in theory,it is smaller in computation to decompose CSP into the sub-problemswhichissolvedmucheasier.Graphtheoryandoperationalresearchmaybedescribedverynaturallyas constraint satisfaction problems. They involve putting together allinformation (constraints) to obtain global solutions which simultaneouslysatisfy all of them. On the other hand, when the size of the problem is verylarge,thewayofstoringinformationinadatabasemaybeseenastheway breaking down global information into pieces of manageable size.The relational database model tackles this problem by storing a databaseas a number of projections from which the original relation isreconstructed. By describing relevant definition in database theory likerelationscheme,tuple,relationinstanceandsoon,withthedecompositiontechniques of join-dependencies in a relational database, people relate thistractabilityof aconstraint satisfactionproblem totheassociatedconstrainthypergraph. Based on this, people decompose original problem efficientlywith the idea of the join-dependencies in database theory and the specialstructure of constraint hypergraph. The classic decomposition strategy isHingedecomposition.By the research about constraint decomposition of ConstraintSatisfaction problem, based on Hinge decomposition which uses databasetechniques,thispaperdescribesHinge+decompositionwhichisavariationof Hinge decomposition, Cut decomposition which is a variation ofHinge+decomposition, Traverse decomposition borrowed from Cutdecomposition, and the combining of Cut decomposition and Traversedecomposition, CaT decomposition and relevant definition. We chooseCaT decomposition which is best trade-off between the width of thegenerated tree and the computational cost of the decomposition; weimplement this decomposition algorithm in the system of Constraintsatisfaction problem's solver, and make the method of decompositionmoreperfect.The idea of CaT decomposition borrowed from Hinge decomposition,and there is one shared edges in adjacent nodes in the hinge-tree which isproduced by Hinge decomposition, this method is not fit for constraintsatisfaction problem including complex constraints.We consider that thenumber of shared edges is more than one, and we can decompose theconstraints, which is a better method. CaTdecomposition complete it likethis: Cut the chosen constraints from the constraint-network, if it canobtain two or more sub-constraint-network, we add the chosen constraintsinto every sub-constraint-network. In this moment, we complete thedecomposition, and the number of shared constraints is not one. we solveit recursively to obtain a tree. This paper uses this method to decompose the constraints, annotates the algorithm, corrects and modifies thealgorithm with the whole idea of the algorithm, designs and implementsthealgorithm.Althoughthemainbodyofthealgorithmismainlyfunction,the data structure is clear, so this paper implements it with the idea ofobject-oriented,designs thehypergraph,hyperedge,variable,partitionandtree into the object, which is convenient to develop and extend, andintegrate with original constraint satisfaction problem solver. Meanwhile,we compare this decomposition technique with that of exitedconfigurationsystem intheideaofdecompositionandtheimplementationofthealgorithm.Itshowsthatthisdecompositionisefficient.This paper applies the decomposition technique to the productconfiguration system which uses java and struts in B/S structure. Whenapplying CaT decomposition to configuration system, we use the methodof using Eclipse platform to develop struts, import the package in whichdecomposition algorithm is into the integrated development environment,and then deploy the implement of the system to the package webapps ofwebserverTomcattorun.To fit for the wayof existed configuration system , the paper analyzesthinking in designing of existed configuration system, designs classesrelevant and relations between them, furthermore, gives the algorithmabout solving configuration by decomposition, at last, overwrite the classOrderActioninsolvingtheconfiguration.Atlast,wegivethetestshowofthedecompositionandtestresultsandanalysis when the number of the constraints, variables and the size of thecut are different. We verify the impact of minimal value of the cut on theefficiencyof the algorithm and width of tree, makingreaders further learnabout CaTdecomposition. Byabove analysis about the test data, we showthat the algorithm can tackle hundreds of constraints in 5 minutes. If wecan choose the cut properlylike reducing the number of the possible cuts,thealgorithmcantackleathousandconstraintsorso.The application of decomposition method to configuration systemmakes system more complete. Meanwhile, for the massive configurationproblems,decompositionisaavailableandeffectiveway.