Optimising Constrained Systems in the Presence of Uncertainty
The constraints on many problems can be divided into hard constraints, soft(or fuzzy) constraints and desirable constraints. Hard constraints are those which must be satisfied in order for the resulting timetable to be considered feasible. Soft constraints are hard constraints which have a tolerance or a probability associated with them - they may be satisfied approximately or with a probability. Desirable constraints are those which are desirable to be satisfied, but which in general cannot all be wholly satisfied.
The problem addressed here is based on the following specification. A solution is required which minimises an objective function weighting the ('probable') violation of the different desirable constraints, and the overall degree of satisfaction of the soft constraints. As many desirable constraints are satisifed as possible, and the collective uncertainty of the soft constraints is either acceptable (within a given range) or simply minimised. If a solution cannot be found which definitely violates no hard constraints then the problem is said to be infeasible, but there might still be an acceptable degree of violation. In such cases, some hard constraints must be relaxed in order to produce an acceptable solution, with an associated degree of certainty of satisfaction. Some variations of this specification are possible, depending on the degree of uncertainty in the problem space.