Constraint satisfaction with a multi-dimensional domain
1992
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.
Keywords:
- Backtracking
- Constraint satisfaction dual problem
- Complexity of constraint satisfaction
- Mathematical optimization
- Constraint satisfaction
- Hybrid algorithm (constraint satisfaction)
- Constraint logic programming
- Constraint learning
- Constraint satisfaction problem
- Mathematics
- Theoretical computer science
- Constraint programming
- Local consistency
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
6
Citations
NaN
KQI