Introduction
In domains such as product configuration, automated planning, and decision support, software systems often generate a vast number of valid solutions. While providing options is beneficial, presenting a human user with an exhaustive list of possibilities is counterproductive. To facilitate effective decision-making, a system must offer a representative sample of the solution space. This paper investigates the computational challenges of finding optimal solutions within the framework of Answer Set Optimization (ASO) that satisfy specific distance constraints relative to a reference point.
Specifically, the research addresses two primary user needs:
- Diversity: Generating a set of dissimilar optimal solutions to provide a broad overview of the available options.
- Refinement: Identifying similar alternatives once a user has selected a preferred solution, allowing for "zooming in" on specific nuances that may not have been explicitly modeled.
Answer Set Optimization (ASO)
ASO is a qualitative preference framework where preferences are expressed through rules (e.g., $C_1 > C_2 > \dots > C_k$) rather than numerical scores. This approach is often more intuitive for human users, who find it easier to rank options than to assign arbitrary satisfaction values. However, the qualitative nature of ASO introduces significant computational complexity when searching for solutions that are both optimal and satisfy distance requirements.
Computational Complexity
A core contribution of this work is the formal classification of the complexity involved in finding $k$-similar and $k$-dissimilar optimal solutions. The author establishes that determining the existence of an optimal answer set $S'$ such that the Hamming distance $HD(S, S')$ is either $\leq k$ (similar) or $\geq k$ (dissimilar) relative to a reference solution $S$ is $\Sigma^p_2$-complete.
This classification places the problem in the second level of the polynomial hierarchy, indicating it is significantly more difficult than standard NP-complete problems. The complexity arises from the need to verify both the optimality of a solution (which itself involves a search for better alternatives) and the satisfaction of the distance constraint.
Methodological Approaches: From Offline to Online
The paper evaluates two distinct strategies for solving these preference reasoning tasks:
Offline Methods
The traditional "offline" approach requires computing the entire set of optimal answer sets first. Once all optimal solutions are stored, the system calculates the Hamming distance between the reference solution and every other optimal solution, filtering for those that meet the $k$ threshold. While conceptually simple, this method is often computationally infeasible for large-scale problems due to the potentially exponential number of optimal solutions.
Online Methods (Proposed)
To overcome the limitations of offline processing, the author proposes an "online" method that encodes the optimization criteria, the distance function, and the distance constraints into a single unified program. The proposed pipeline follows these steps:
- QBF Encoding: The problem is translated into a Quantified Boolean Formula (QBF).
- Translation or Direct Solving: The QBF can be translated into a disjunctive logic program for use with solvers like
claspDorDLV, or it can be processed directly by specialized QBF solvers.
This approach aims to find the desired solutions directly without the need to enumerate the entire set of optimal answer sets, potentially offering a more scalable path for real-world applications.
The "Tester" Program and Formalization
The search for optimal solutions is formalized using a "tester" ASP program. In this iterative process, the system starts with an arbitrary solution and uses the tester to find a "strictly better" one. This cycle continues until the tester fails to find a superior solution, signifying that an optimal answer set has been reached. The paper provides a rigorous mathematical representation of how satisfaction degrees are calculated based on preference rules, ensuring a solid foundation for the proposed QBF encodings.
Conclusion and Future Directions
While the theoretical groundwork and complexity results are established, the implementation of the online QBF-based method remains the focus of ongoing work. Future research will involve finalizing these encodings and conducting extensive empirical experiments to compare the performance of various solver technologies. Moving from offline enumeration to direct online reasoning represents a critical step toward building responsive and efficient tools for preference-based decision support.
Summary updated