Introduction
In Constraint Programming (CP), solvers traditionally focus on two distinct goals: finding a single optimal solution (optimization) or finding a set of solutions that are as different as possible (diversity in satisfaction problems). However, real-world decision-making often requires a middle ground. For instance, in vehicle routing or personnel scheduling, a manager may prefer a set of high-quality options to choose from, allowing for flexibility in the face of unmodeled preferences or unexpected events. This paper introduces a generic framework for Constraint Optimization Problems (COPs) that simultaneously prioritizes high solution quality and diversity.
The kBESTOPT Framework
The authors propose an iterative algorithm called kBESTOPT to generate a set of "good but different" solutions. The process follows these steps:
- Initial Optimization: Solve the original COP to find the absolute best solution ($t^*$).
- Defining the Trade-off: A new objective variable, $robj$, is introduced to balance diversity ($\delta$) and quality loss ($Q$). The paper explores two primary formulations: a Ratio ($robj = \delta / (Q+1)$) and a Weighted Sum.
- Iterative Search: In each subsequent step, the solver seeks a new solution that maximizes $robj$ relative to the set of solutions already discovered.
- Distance Metrics: Beyond standard Hamming distance, the framework incorporates $L_1$ (Manhattan) and $L_2$ (Euclidean) norms. These are more suitable for numerical problems where the magnitude of change is as important as the occurrence of change.
A significant technical contribution is the development of new filtering algorithms for these $L_1$ and $L_2$ diversity constraints. These algorithms maintain Generalized Arc Consistency (GAC) efficiently, allowing the solver to prune the search space without excessive computational overhead.
Experimental Evaluation
The framework was evaluated on two distinct problem types:
- Sorting Chords: A musical benchmark requiring chords to be arranged to minimize transition costs, testing performance on over-constrained problems.
- TSPLIB: A standard library for the Traveling Salesman Problem (TSP). Symmetric instances like Att48 and Berlin52 were used to demonstrate the framework's ability to find alternative high-quality routes.
To handle the different scales of diversity and quality loss, the authors introduced a normalization technique using rounded integer scaling factors. This ensures that neither factor disproportionately dominates the search process.
Results and Discussion
The experimental results highlight the robustness of the ratio-based approach. As shown in the performance comparison across various instances, using a Ratio (R) or a Normalized Ratio (NR) consistently outperformed a simple weighted sum (S) or normalized sum (NS) in terms of proving optimality and reducing the number of backtracks.
On the TSPLIB benchmarks, the framework successfully identified diverse alternative routes with minimal quality loss—often between 0.1% and 5% deterioration from the absolute optimum. For many instances, the solver could find and prove the optimality of 20 diverse solutions in under a minute, demonstrating that the added complexity of diversity constraints is manageable for modern solvers.
Conclusion and Future Work
The kBESTOPT framework provides a solver-independent paradigm for balancing quality and diversity in COPs. While the current implementation uses the original model's search heuristics, future work could involve developing search strategies specifically tuned for diversity. Additionally, the authors suggest integrating other global counting constraints, such as DEVIATION or BALANCE, to further refine semantic diversity. Testing on larger-scale industrial problems remains a necessary step to fully validate the paradigm's real-world utility.
Summary updated