Optimal Solution Stability in Dynamic, Distributed Constraint Optimization
Optimal Solution Stability in Dynamic, Distributed Constraint Optimization
复制标题
动态分布式约束优化中的最优解稳定性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
B. Faltings
中科院分区：
文献类型：
--
作者：
Adrian Petcu;B. Faltings
定义了分布式连续时间组合优化问题。基于从已实现解到新解的改变代价，我们提出了动态优化中解的稳定性的新概念。变更成本是根据稳定性约束进行建模的，并且可以随着时间的推移而演变。基于这个定义，我们提出了一种保证动态环境下最优解稳定性的自稳定优化算法RSDPOP。与当前求解静态CSP序列的方法不同，我们的机制具有更大的灵活性：每个变量都可以在任何时间点分配和重新分配其自己的承诺截止日期。因此，优化过程是连续的，而不是一系列解决问题的快照。我们给出了分布式会议调度领域的实验结果。
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.