In this paper, we apply incremental answer set solving to product
configuration. Incremental answer set solving is a step-wise incremental
approach to Answer Set Programming (ASP). We demonstrate how to use this
technique to solve product configurations problems incrementally. Every step of
the incremental solving process corresponds to a predefined configuration
action. Using complex domain-specific configuration actions makes it possible
to tightly control the level of non-determinism and performance of the solving
process. We show applications of this technique for reasoning about product
configuration, like simulating the behavior of a deterministic configuration
algorithm and describing user actions.

本文介绍了如何使用增量式答案集求解技术来解决产品配置问题，该技术能够通过使用复杂的领域特定配置操作来控制非确定性水平和求解过程的性能，并且具有模拟确定性配置算法和描述用户动作等应用。

应用增量答案集求解于产品配置

Applying Incremental Answer Set Solving to Product Configuration

In many AI domains such as product configuration, a user should interactively
specify a solution that must satisfy a set of constraints. In such scenarios,
offline compilation of feasible solutions into a tractable representation is an
important approach to delivering efficient backtrack-free user interaction
online. In particular,binary decision diagrams (BDDs) have been successfully
used as a compilation target for product and service configuration. In this
paper we discuss how to extend BDD-based configuration to scenarios involving
cost functions which express user preferences.
We first show that an efficient, robust and easy to implement extension is
possible if the cost function is additive, and feasible solutions are
represented using multi-valued decision diagrams (MDDs). We also discuss the
effect on MDD size if the cost function is non-additive or if it is encoded
explicitly into MDD. We then discuss interactive configuration in the presence
of multiple cost functions. We prove that even in its simplest form,
multiple-cost configuration is NP-hard in the input MDD. However, for solving
two-cost configuration we develop a pseudo-polynomial scheme and a fully
polynomial approximation scheme. The applicability of our approach is
demonstrated through experiments over real-world configuration models and
product-catalogue datasets. Response times are generally within a fraction of a
second even for very large instances.

这篇论文讨论了如何将基于二进制决策图（BDD）的配置扩展到涉及表示用户偏好的成本函数的情景中，并证明即使在其最简单的形式下，多成本配置也是 NP - 难问题。