Optimization in graphical models is an important problem which has been studied in many AI frameworks such as weighted CSP, maximum satisfiability or probabilistic networks. By identifying conditionally independent subproblems, which are solved independently and whose optimum is cached, recent Branch and Bound algorithms offer better asymptotic time complexity. But the locality of bounds induced by decomposition often hampers the practical effects of this result because subproblems are often uselessly solved to optimality. Following the Russian Doll Search (RDS) algorithm, a possible approach to overcome this weakness is to (inductively) solve a relaxation of each subproblem to strengthen bounds. The algorithm obtained generalizes both RDS and tree-decomposition based algorithms such as BTD or AND-OR Branch and Bound. We study its efficiency on different problems, closing a very hard frequency assignment instance which has been open for more than 10 years.
展开▼
机译：图形模型的优化是一个重要的问题，已在许多AI框架（例如加权CSP，最大可满足性或概率网络）中进行了研究。通过识别有条件独立的子问题，这些子问题可以独立解决并且可以缓存其最优值，最近的Branch和Bound算法提供了更好的渐近时间复杂度。但是分解所引起的边界的局部性常常会阻碍该结果的实际效果，因为子问题通常无法无用地求解为最优。遵循俄语玩偶搜索（RDS）算法，克服这一弱点的一种可行方法是（归纳地）解决每个子问题的松弛，以增强边界。所获得的算法对RDS和基于树分解的算法（例如BTD或AND-OR Branch and Bound）进行了概括。我们研究了它在不同问题上的效率，并关闭了一个非常艰苦的频率分配实例，该实例已经开放了10多年。
展开▼
