Optimal Solution Stability in Real Time Optimization

We define the distributed, real-time combinatorial optimization problem. We propose a general, semantically well-defined notion of solution stability in such systems, based on the cost of change from an already implemented solution to the new one. This approach allows maximum flexibility in specifying these costs through the use of stability constraints. We present the first mechanism for combinatorial optimization that guarantees optimal solution stability in dynamic environments, based on this notion of solution stability. In contrast to current approaches which solve sequences of static CSPs, our mechanism has a lot more flexibility by allowing for a much finer-grained vision of time: each variable of interest can be assigned its own commitment deadlines, allowing for a continuous, real-time optimization process. We describe an algorithm for the distributed case, but its reduction to a centralized system is straightforward.