Constraint satisfaction with a multi-dimensional domain

Abstract This paper presents a novel approach to a class of constraint satisfaction problems (CSPs). First, it defines Multi-Dimensional Constraint Satisfaction Problem (MCSP) , which is a useful model applicable to many scheduling problems. Second, it proposes an approach for MCSPs. The approach employs both a general problem-solving method and an automatic generation method for problem-solving programs. The problem-solving method is a combined method with backtracking and constraint propagation, based on the features of MCSPs. The automatic generation method analyzes the meaning of constraints and generates a problem-solving program, which is especially efficient for the given problem. Finally, the proposed approach is evaluated by several experiments including scheduling applications and well-known toy problems. Employing both the two methods enables solving a hard MCSP in a reasonable time, merely by describing it in a declarative form.