Constraint programming is gaining a great deal of attention because many combinatorial problems especially in areas of planning and scheduling can be expressed in a natural way as a Constraint Satisfaction Problem (CSP). It is well known that a non-binary CSP can be transformed into an equivalent binary CSP using some of the actual techniques. However, when the CSP is not discrete or the number of constraints is high relative to the number of variables, these techniques become impractical. We propose an algorithm called "Hyperpolyhedron Search Algorithm" as an incremental and non-binary CSP solver. This non-binary CSP solver does not increase its temporal complexity with the variable domain size. It carries out the search through a hyperpolyhedron that maintains those solutions that satisfy all metric non-binary temporal constraints. Thus, we can manage more complex and expressive problems with high a number of constraints and very large domains.
Specification of the Hyperpolyhedron Search Algorithm.
Briefly, a constraint satisfaction problem (CSP) consists of:
We assume a non-binary temporal CSP where variables are time points which are bounded in continuous domains and a collection of non-binary temporal constraints (linear constraints).
The specification of the Hyperpolyhedron
Search Algorithm (HSA) is presented in (Fig.1). Initially, HSA has a static
behaviour such a classic CSP solver. The hyperpolyhedron vertices are created
by means of the Cartesian product of the variable domains (step 1). Then,
for each constraint, HSA carries out the consistency check (step 2). If
the constraint is not consistent, HSA returns not consistent problem; else,
HSA determines if the constraint is not redundant, updating the hyperpolyhedron
(step 3). Finally, HSA can obtain some important results such as: the problem
consistency, one or all problem solutions, the new variable domains and
the vertex of the hyperpolyhedron that minimises or maximises some objective
Furthermore, when HSA finishes its static behaviour (classic CSP solver), new constraints can be incrementally inserted into the problem, and HSA studies the consistency check such as an incremental CSP solver.
Fig. 1. General Scheme of the Hyperpolyhedron
HSA Framework in random problems
Let's see an example of HSA in random problems:
The user must insert the following parameters:
HSA generates the random problems, and studies the consistency check:
Finally, HSA returns the number
of required solutions, and the problem run time: