HSA        

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:

• a set of variables;
• each variable has got a finite set of possible values (its domain);
• and a finite collection of constraints restricting the values that the variables can simultaneously take.

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 function.
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 Search Algorithm.
 
 

HSA Framework in random problems

Let's see an example of HSA in random problems:

The user must insert the following parameters:

• Number of variables.
• Number of constraints.
• Domain Length.
• Number of desired solutions.
• Number of problems.

HSA generates the random problems, and studies the consistency check:

Finally, HSA returns the number of required solutions, and the problem run time: