Towards a framework for designing constraint solvers and solver collaborations
In this paper, we propose a strategy language for designing constraint solvers and schemes of solver collaborations. Solvers are seen as bricks that can be integrated when creating more complex solvers that can become themselves new bricks to compose new solvers. These bricks are glued together using operators of our...
A general s hema for constraint propagation
Various algorithms for achieving different levels of local consistency (i.e., constraint propagation algorithms), even diverse ones for the same kind of local consistency, are present in the literature and built into existing systems. Due to their variety and diversity, a natural quest is to search for a common framework. In...
Solving CSPs with predominating constraints of the “not equal” type
In this paper we present a new stochastic search algorithm which is designed to solve finite binary constraint satisfaction problems, where constraints of the “not equal” type predominate. The experiments show that, in comparison with the backtrack-based algorithms, the presented algorithm is superior when it is used to solve problems...
Solving problems of resource constraint satisfaction with Time-EX
In the present paper, we examine some issues related to the development of Time-EX (an intelligent scheduling and project management system) as an application of the method of subdefinite models (SD-models). Extension of SD-models with dynamic elements is briefly discussed, along with their implementation via the tools for knowledge representation...
Application of constraint hierarchy to timetabling problems
At the beginning of each school year, universities everywhere must undertake boring and time-consuming process of slotting students, teachers and lessons into available classrooms. It is a natural scheduling problem and schedulemakers are looking for simple flexible and effective automatic systems.
Scheduling problems are often NP-complete. There are many approaches...
Rule-based versus procedure-based view of logic programming
Logic programming is a rule-based formalism: a program consists of a set of rules activated by an initial query. In contrast, imperative programming is explained by means of a procedure-based view: a program consists of a set of procedure declarations and an initial statement.
We clarify here to what procedure-based...
Constraint propagation in presence of arrays
We describe the use of array expressions as constraints, which represents a consequent generalisation of the element constraint. Constraint propagation for array constraints is studied theoretically, and for a set of domain reduction rules the local consistency they enforce, arc-consistency, is proved. An efficient algorithm is described that encapsulates the...
A model of cooperative solvers for computational problems
The paper presents a model for building cooperative solvers for computational problems. We suggest an architecture of an environment which allows us to implement the model. It consists of a kernel, a library of methods, a scenario language and a universal internal representation. Methods have a special structure that provides...
Representation of interval models and interval data in the constraint programming system
One of the most advanced and practically significant approaches in constraint programming is the method of subdefinite models.
This method is the basis for a multilevel constraint programming tech- nology that has been developed to solve various problems in economics, engineering, calendar planning, etc.
A subdefinite model is a pair...
Model vs. Algorithm: change of paradigm in information technology
Algorithm is one of the most fundamental concepts in information technology. Its absolutely dominant position reminds that of programming in machine codes during the era of the first computers: it appeared to be the only conceivable method to communicate with a machine, but its fate disproved this axiom. The same...
Subdefinite data types and constraints in knowledge representation language
A knowledge representation language with subdefinite data types and constraints is considered. An important feature of this language is the possibility of operating with objects that may have slots (attributes) with imprecisely defined (subdefinite) values. Another important feature of the language is that it allows one to bind any object...