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，最大可满足或概率网络。通过识别有条件的独立子问题，它们独立解决并且其最佳缓存，最近的分支和绑定算法提供更好的渐近时间复杂度。但是分解引起的界的界定经常妨碍这种结果的实际效果，因为子问题通常无用地解决了最优性。在俄语娃娃搜索（RDS）算法之后，克服这种弱点的可能方法是（电感）解决每个子问题的放松以加强边界。该算法概括了基于RDS和树分解的算法，例如BTD或AND AND AND和BREAD。我们研究其对不同问题的效率，关闭了一个非常硬的频率分配实例，该实例已开放超过10年。
展开▼
