Formulation of many real-life problems evolves as the problem is being solved. These changes are typically initiated by a user intervention or by changes in the environment. In this paper, we propose a formal description of a so called minimal perturbation problem that allows an “automated” modification of the (partial) solution when the problém formulation changes. Our model is defined for constraint satisfaction i)roblenis with emphasis put on finding a solution anytime even for over-constrained problems.
Constraint programming is an approach for solving (mostly combinatorial) problems by stating constraints over the problem variables. Iri some problems, there is no solution satisfying all the constraints, so the problem formulation must deal with uncertainty, vagueness, or imprecision. In such a case the standard constraint satisfaction techniques dealing with hard constraints cannot be used directly and some form of soft constraints is required. In the paper we siirvey four generic models for soft constraints, námely hierarchical, partial, valued, and semiring-based constraint satisfaction.