Optimal Solution Stability in Dynamic, Distributed Constraint Optimization

We define the distributed, continuous-time combinatorial optimization problem. We propose a new notion of solution stability in dynamic optimization, based on the cost of change from an already-implemented solution to the new one. Change costs are modeled with stability constraints, and can evolve over time. We present RSDPOP, a self-stabilizing optimization algorithm which guarantees optimal solution stability in dynamic environments, based on this definition. In contrast to current approaches which solve sequences of static CSPs, our mechanism has a lot more flexibility: each variable can be assigned and reassigned its own commitment deadlines at any point in time. Therefore, the optimization process is continuous, rather than a sequence of solving problem snapshots. We present experimental results from the distributed meeting scheduling domain.