The Design And The Implementation Of The Constraint Solver Based On Java

In the real world, there are often constraints widely existing in all kindsof fields of scientific research and living. And we always encounter variouscombinatorial optimization problems which are connected with theconstraints, especially those problems interested in business, such asscheduling, timetabling, design and configuration, routing, and matching. Inthe past, solvents comprise handwork or tradition methods in operationalresearch. Their limitation is generating irrationality solution (or schedulingtable), and running long time.These kinds of problems always require searching through a possiblyexponentially sized solution space in order to find a good or optimal solutionto the problem. To obtain reasonable efficiency, some useful constraints mustbe abstracted from the problems giving some conditions to satisfy so thatthey can be used to prune the search space. Constraint is an extensive concept.Intuitively, a constraint is viewed as restriction in possibility space.Mathematic constraint (e.g. X+Y>Z) is simply a logical relation amongseveral unknowns (variables X, Y, Z), each taking a value in a given domain.A constraint thus restricts the possible values that variables can take.Constraints are used to model the behavior of systems of objects in the realworld by capturing an idealized view of the interaction among the objects,this called constraint modeling. It is the category of constraint programmingto simplify a real world situation into a system of constraints about idealizedobjects, and use this system of constraints to better understand the behaviorof the real world. Constraint programming is the study of computationalsystems based on constraints, is a powerful method on programming,modeling and problem resolution. Based on the difference of approaches tosolve constraints, there can be seen two branches of Constraint Programmingresearch: Constraint Satisfaction and Constraint Solving.The Constraint Satisfaction Problem (CSP) is used to deal with generalfinite constraint domains. It comprises a finite set of variables, everyvariable's finite domain, a finite set of constraints. Each constraint restrictsthe combination of values that a set of variables may take simultaneously. Asolution of a CSP is an assignment to each variable a value from its domainsatisfying all the constraints. The task of a CSP is to find one solution or allsolutions. The intuitive search methods to CSPs are systematic searchalgorithms, e.g. generate and test, backtracking. Since no attempt is made toprune the search space, their efficiency is low. Because consistencytechniques (e.g. node-consistency, arc-consistency) can prune the searchspace, it is a perfect method to integrate systematic search algorithms withconsistency techniques, named constraint propagation. Constraintpropagation is divided into two kinds: look-ahead and look-back. Theordering in which the variables are instantiated and the values chosen couldaffect the efficiency of search algorithms to a great extent. Constraint Solving differs from Constraint Satisfaction by usingvariables with infinite domains. Also, the individual constraints are morecomplicated, e.g., nonlinear equalities. Consequently, the constraint solvingalgorithms uses the algebraic and numeric methods instead of combinationsand search. However, there exists an approach which discretizes the infinitedomain into finite number of components and, then, applies the techniques ofconstraint satisfaction. When solving a certain kind of CSPs, by using some specificallyknowledge you can get better efficiency. However, it is expensive, and thespecifically arithmetic isn't easy to modify when the problem changes. Ageneral solver is very useful, so we design and implement the ConstraintSolving Platform. It integrates constraints into object orientedlanguages(Java), takes constraints, variables and solver as entities, based onconstraint programming, uses predefined constraint sets and general solver tosolve all kinds of CSPs. The system is a Java open package, with provisions for extensions. Andit can be integrated into existing applications. It is designed for applicationdevelopers. The system provides power modeling. Users can widely selectdecision variables and all predefined constraints. And users can add newconstraints and new search strategies simply by extending predefined classes.The system introduces a design principle on separation of problem modelingfrom problem resolution, users will find that they have latitude with Solver totest a variety of search strategies to find the most efficient solving approachwithout disturbing the stated constraints of the problem. What I concentrate on most is to design and implement a constraintsolver which can solve the general CSPs. And the procedure consists ofproblems analyzing and modeling, solving approaches designing andimplementing. Feature of the system is the method that it deals withnon-binary constraint satisfaction problems is not translating them into theirequivalent binary ones, but solving them directly. Consequently, the generalCSPs are expressed as some domains, variables, non-binary constraints and aconstraint network. And different constraints have different constraintpropagation algorithms. When users tell system constraints, the system uses v...