Robust solutions in unstable optimization problems

We consider constraint optimization problems where costs (or preferences) are all given, but some are tagged as possibly unstable, and provided with a range of alternative values. We also allow for some uncontrollable variables, whose value cannot be decided by the agent in charge of taking the decisions, but will be decided by Nature or by some other agent. These two forms of uncertainty are often found in many scheduling and planning scenarios. For such problems, we define several notions of desirable solutions. Such notions take into account not only the optimality of the solutions, but also their degree of robustness (of the optimality status, or of the cost) w.r.t. the uncertainty present in the problem. We provide an algorithm to find solutions accordingly to the considered notions of optimality, and we study the properties of these algorithms. For the uncontrollable variables, we propose to adopt a variant of classical variable elimination, where we act pessimistically rather than optimistically.