A Schema for Constraint Relaxation with Instantiations for Partial Constraint Satisfaction and Schedule Optimization
John Beck · 1994
We investigate constraint relaxation within a general constraint model. We claim that a key to relaxation is recognition that a constraint can be modified in a variety of ways and that each modification potentially carries a different impact for both the quality of the solution and the problem solving process. Our primary motivation is the application of constraint relaxation as a technique for coordination of multiple agents in a shared environment. We propose a schema for constraint relaxation that is based on the propagation of information through a constraint graph. The schema isolates five heuristic decision points where techniques of varying complexities can be specified. Three algorithms within the schema are declared and shown to perform well on Partial Constraint Satisfaction Problems (PCSPs). Three additional algorithms are defined and used in the estimation of the impact of scheduling decisions in a medium size job shop scheduling problems. Difficulties with the calculation of actual impact data prevents comparison among the algorithms. The algorithms represent an advance by allowing propagation over all types of constraints and the ability to integrate heuristic decision making. iii ivAcknowledgments