| Constraint is one of our familiar concepts, for there are plenty of examples about constraints in our everyday study lives. For instance, the three angles of a triangle sum to 180 degree, the relative position of the scroller in the window scroll-bar must reflect the position of the current text in the underlying document. Formally, a constraint is simply a logical relation among several unknowns, each taking a value in a given domain. Constraint Programming (CP) is the methodology on programming and problem solving which was founded on the work circling the concept of constraints, and its central goal is constructing the reasoning and computing system for constraint-based combinatorial optimization problems. As an emergent software technology, CP has the advantage of declarative description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling, not surprisingly, it has been identified by the ACM (Association for Computing Machinery) as one of the strategic directions in computer research. When evaluating it, the famous American computer scientist Eugene C. Freuder said, "Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it."In CP Community, it is generally recognized that the constraint idea comes from 1963 when Sutherland introduces Sketchpad, the first interactive graphical interface that solved geometric constraints. After that, a series of research on geometry constraints processing came forth, but the genuine CP theory hadn't taken shape yet. The CP was founded as the extension of the logic programming (LP). In the middle of 1980, with the failure of the Japan fifth generation computer planning, the research of logic programming fell into low tide, meanwhile, there was much work on the research on logic programming combining with constraint solving in succession, whose practice was focused on the extension from tree constraints to constraints on arbitrary domain. In 1987, Jaffar presented a general model after analyzing the previous related work. His finding leads to the paper titled by "Constraint Logic Programming", which became the seminal paper of Constraint (Logic) Programming. Now, with the absorption from constraint satisfaction problems solving algorithms of artificial intelligence (AI) and the mathematical programming theory of operations research, it has been one of the most important and active research directions in computer science. As one the earliest and the most developed parts in CP, CLP theory is the most important part of CP. Above all, CLP's foundation is LP, so a majority of work was to lift the conclusion from LP to CLP, such as Jaffar firstly presented the relative completeness operational semantics, logic semantics, algebraic semantics and their relations of CLP, Giacobazzi gave the abstract interpretation based general semantics of CLP, and Gabbrielli analyzed the all sorts of observable behaviors of CLP deeply. At the same time, with the development of the AI, especially the advancement of the logic based reasoning and LP, a lot of research on non classical CLP emerged, e.g. Modal CLP, Inductive CLP, Abductive CLP and Linear CLP. At the same time, the program theory affected the CLP study, such as slicing, reflection and transformation research of CLP. In theory, the exploration in broad semantics and the improvement of express power do good to reinforce the theory foundation of CLP. Collaboration with procedural language is another successful research direction of CP, which give consideration to the advantage of the two areas. One hand, it makes the user declarative model problems with constraints. On the other hand, the procedure languages have the advantage of efficient codes and being suited to real life problems. But this collaboration differs from the CLP, the difficult come from the characteristic of procedure language, which lead the incompact collaboration rather than a united constraint language. Thereinto, the constraint solving toolkits is the most successful form. Constraint solving toolkits take the object oriented language as the host language, such as C++ and Java, therefore which allow constraints, variables and solvers to be first class entities. ILOG SOLVER toolkit is the classical successful example. Our constraint solving system belongs to the same research area too. In addition, as far as the constraint solving tools are concerned, the high efficiency and expressiong power are two hard principles, which lead to the importance of the research on constraint satisfaction problems solving algorithms and new constraint models. The algorithms consist the backtracking based systematic search and its improvement; consistence checking techniques and its extension; constraint propagation approaches; variables and values selection heuristic strategies; randomized algorithms such as genetic algorithm and artificial neural networks for constraint optimization problems. Nowadays, there are the new trends of collaborative solving with diversiform algorithms. Furthermore, the Randomized Constraint Satisfaction Problems (RCSP) generation model originated from SAT provides the impartial algorithm testing, and the improvement and the adaptability enhancement are the urgent work. As to models, for the sake of handling the over constrained satisfaction problems, on the basis of the Fuzzy CSP, there is much work on soft CSP, which includes the probability CSP, weight CSP, hierarchical CSP, semiring-based CSP and valued CSP. All these work strengthen the express power of the CP. Meanwhile, therelated research on algorithms improvement is hotpot and the integration of constraint satisfaction models with reasoning approaches is a new question for discussion. In this thesis we present our work circling the theory foundation of CLP and the implementation of the CP system, which including the semantics research on CLP; the integration of soft CP approach with qualitative reasoning; the work about the testing of constraint solving algorithms; the implementation of our constraint solving tools. The detailed contents fall into the following aspects: 1. After analyzing the characteristic of the S-semantics approach, we discuss another observable behavior of CLP, and present the multiset answer constraint based fixpoint semantics, which can reflect the parallel character from the semantics. Then we define the new program equivalence on it. With the new definition we can analyze the program equivalence more strictly, and comprehend the programs deeply. All these work will help the programmer write the more efficient and compact program, and give prominence to the language characteristic of CLP system. 2. Inspired by the application of game theory in the procedure language and LP semantics, we give the winning strategy based semantics of CLP from the game theory point of view. Because game theory is the new approach for studying the program semantics, it has the advantage of comprehending the programs with the new point, i.e. it focus on the parallel behaviors, which will help us develop the parallel CLP system. Moreover, we not only present the game semantics of CLP, but also prove that it is equivalent with the traditional semantics. 3. Aim at the reasoning problems of CP-nets with constraints, firstly we improve the semantics of the CP-nets, then we present a new approaches that transforming the CP-nets with constraints into the constraint hierarchy, so as to handle the constraints and the preference relations in a unified framework. Meanwhile, we prove that the transformation keeps the ceteris paribus property and doesn't lose any information. Finally we present the complexity results and some conclusions, furthermore, we compare our work with the research of integrating with the semring-based CSP and logic programming, then point the future work. 4. For the testing of the constraint solving algorithms, we study the current randomized generating models of constraint satisfaction problems. On the basis the analysis of all kinds of models, we firstly present the extended RCSP generating model and problem instances generating method, then we give the relation matrix oriented backtrack search integrated consistence checking RCSP solving algorithms. On the next section, we discuss the design and the implementation of instance generator and solver, and show the experiment results of the classical problem instances. The results prove that our new model has the same phase transition field with the traditional models, but has the advantage of being suited to the heuristic based constraint solving algorithms testing.5. After absorbing the experiences of the famous ILOG SOLVER toolkit, we design and implement the constraint solving system with all sorts of constraint solving algorithms and search procedure visualization function in Java language. Our system considers the constraint domains, variables and solvers as the entities, and use the pre-defined constraint set and general purpose constraint solver solve all kinds of constraint satisfaction problems. When announcing the constraints, our system can reduce the constraint domain using constraint propagation approaches automatically and then solving the problems the search tree integrated consistence checking techniques. In addition, our system has the advantage of openness, extensibility and maintainability. In the last section we using the popular problem instances testing all algorithms included by our system, and give the analysis of the results in detail.
|
PDF Full Text Request