Many real life problems come from uncertain and dynamic environments and therefore, the original problems, and consequently their associated Constraint Satisfaction Problem (CSP) models, may evolve over the time. In such situations, a solution that holds for the original problem can become invalid after changes occur. There exist two main approaches for dealing with these situations: reactive and proactive. Using reactive approaches entails re-solving the CSP after a solution is no longer a solution, which is time consuming. For this reason, such as mentioned in the Verfaillie and Jussien (2005) survey, a desirable objective is: “limit as much as possible the need for successive online problem solvings.”

Motivated by the above statement, in this dissertation we develop proactive approaches, which try to offer a resistance to the possible future alterations of the problem. In addition, in the Verfaillie and Jussien (2005) survey, the authors also state as desirable objectives: “limit as much as possible changes in the produced solution” and “the production of solutions that have every chance to resist changes (robustness) and can be easily adapted when they did not resist (stability).”

For this reason, in this thesis we develop approaches that meet the condition of combining solution robustness and stability. To the best of our knowledge, this combination has not yet been developed for CSPs. Many proactive approaches that search for robust solutions require detailed knowledge about the dynamic environment. As a result, in the lack of such a priori information (which is common in the real life aplications), these methods can not be applied. For this reason: “ideally, no additional knowledge over the data used to build the classical constraint network is required, without taking uncertainty into account (Hebrard, (2006))”

In this dissertation, we try to answer an interesting question in dynamic and uncertain environments: when additional data about the possible changes in the problem is unknown, is it possible to define what is the robustness of a solution of a CSP and to build appropriate algorithms? We found that it is possible and justifiable to extract some limited (and intuitively reasonable) assumptions about the dynamism of problems for which the order over the domain elements is significant. Thus, the fulfillment of these four statements has motivated this PhD thesis work.

This thesis contributes toward better understanding, modeling and solving of problems that come from this kind of dynamic and uncertain environments. One of the contributions of this thesis is the formalization of a new dynamism framework for CSPs with ordered domains that model real life problems in which the order is significant, introducing theoretical approaches for dealing with such environment. Moreover, we further extend the definitions of robustness and stability of the solutions in such framework. This thesis also contributes to the literature by presenting algorithms that can provide solutions with a certain level of robustness and stability for problems that do not consider extra data about the dynamism but only consider the existence of an order over the elements of the domains of the CSPs.