Reasoning about Optimal Collections of Solutions
Reasoning about Optimal Collections of Solutions
复制标题
关于最优解集合的推理
DOI：
10.1007/978-3-642-04244-7_34
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
B. O’Sullivan
中科院分区：
文献类型：
--
作者：
T. Hadzic;A. Holland;B. O’Sullivan
在许多应用设置中存在找到组合问题的解的集合的问题，该组合问题在解间目标函数方面是最优的。例如，期望在产品配置设置中的一组解决方案之间最大化多样性，以便向客户提供广泛的不同选项。考虑到这些多解查询在计算上具有挑战性的性质，现有的算法方法要么应用算法学，要么应用组合搜索，这不能扩展到大的解空间。然而，在许多领域中，将原始问题编译成紧凑的表示可以支持计算效率高的查询应答。在本文中，我们提出了一种新的方法来找到最佳的解决方案的集合时，问题被编译成一个多值决策图。我们的经验表明，对于现实世界的配置问题，我们的方法的精确和近似版本是有效的，并能够显着优于最先进的基于搜索的技术。
The problem of finding a collection of solutions to a combinatorial problem that is optimal in terms of an inter-solution objective function exists in many application settings. For example, maximizing diversity amongst a set of solutions in a product configuration setting is desirable so that a wide range of different options is offered to a customer. Given the computationally challenging nature of these multi-solution queries, existing algorithmic approaches either apply heuristics or combinatorial search, which does not scale to large solution spaces. However, in many domains compiling the original problem into a compact representation can support computationally efficient query answering. In this paper we present a new approach to find optimal collections of solutions when the problem is compiled into a multi-valued decision diagram. We demonstrate empirically that for real-world configuration problems, both exact and approximate versions of our methods are effective and are capable of significantly outperforming state-of-the-art search-based techniques.
基于案例的推理研究与开发
DOI：
10.1007/978-3-642-39056-2_11
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Horsburgh B
通讯作者：
Horsburgh B