TL;DR
This paper introduces a comprehensive taxonomy of "soft" constraints for modeling diversity and similarity in constraint satisfaction problems. The authors analyze the computational complexity of enforcing consistency on these constraints, revealing that enforcing equality is generally harder than enforcing difference, and providing efficient algorithms for several previously open problems.
What Problem Does This Paper Address?
In many real-world problems, we need to ensure that assignments to variables exhibit a certain degree of diversity or similarity. For example, in university timetabling, we might want to ensure students don't have classes at the same time (diversity), or that all participants in a meeting are scheduled for the same time and place (similarity). When problems become over-constrained, we often want to find solutions that best satisfy these diversity or similarity requirements, rather than strictly enforcing them. This paper addresses how to formally model and efficiently solve these "soft" constraint problems, specifically focusing on constraints related to difference (like ALLDIFFERENT) and equality (like ALLEQUAL). The authors aim to provide a complete picture of the computational complexity of achieving different levels of consistency (Arc Consistency and Bounds Consistency) for various combinations of these soft constraints and their associated cost functions.
Methods
The paper systematically explores a taxonomy of six soft global constraints derived from combining ALLDIFFERENT and ALLEQUAL with two cost metrics (graph-based and variable-based) and two objectives (minimization and maximization). For each constraint, they analyze the complexity of achieving Arc Consistency (AC) and Bounds Consistency (BC). Key techniques include:
- Dynamic Programming: Used to efficiently compute optimal solutions for certain problems, particularly for Bounds Consistency.
- Reduction to Known Problems: Showing that some soft constraints are equivalent to or can be reduced to well-studied problems like 3dMatching or Vertex Matching, allowing for the transfer of known complexity results.
- Sweep Algorithms: Employed for efficient computation of occurrence functions and derivatives, crucial for interval-based domain filtering.
- Fixed-Parameter Tractability (FPT): Developing algorithms whose runtime is exponential only in a specific parameter (like the number of distinct values or "conflicting" values), making them efficient for problems with a small parameter value, even with many variables.
- Approximation Algorithms: Designing algorithms that provide a guaranteed bound on the quality of the solution, even if not strictly optimal, with a focus on achieving linear time complexity.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development for constraint satisfaction problems, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Equality is Harder than Difference: A central finding is that enforcing equality constraints (even soft ones) is generally computationally harder than enforcing difference constraints. This is evident in the NP-hardness results for certain equality-related problems.
- Duality of Graph-Based Costs: The graph-based costs for
ALLDIFFERENTandALLEQUALare shown to be dual, meaning that optimizing one is equivalent to optimizing the other in the opposite direction. - Tractable Cases for Equality: Despite the general difficulty, specific cases of equality constraints become tractable. For instance, if no value appears in more than two domains, or if the number of "heavy" values (occurring more than twice) is limited, the problem can be solved efficiently.
- Efficient Bounds Consistency: While Arc Consistency can be NP-hard for some soft equality constraints, Bounds Consistency can often be achieved in polynomial time, highlighting the importance of different consistency levels.
- Approximation Guarantees: A simple greedy algorithm for maximizing the number of equalities provides a guaranteed approximation factor of 1/2, running in linear time, which is a significant practical result.
Key Results
- Complexity Characterization: The paper provides a comprehensive complexity analysis for achieving AC and BC on six soft constraints related to difference and equality, closing several open questions.
- NP-Hardness for Equality: Achieving Arc Consistency for maximizing the number of pairwise equalities (SOFTALLEQUALmin) is shown to be NP-hard, even in restricted cases.
- Polynomial Time for Bounds Consistency: Bounds Consistency for SOFTALLEQUALmin can be achieved in polynomial time, particularly when domains are contiguous intervals.
- FPT Algorithms: The paper presents FPT algorithms for SOFTALLEQUALmin with respect to the number of distinct values (λ) and the number of "conflicting" values, offering efficient solutions for problems with a limited number of values.
- Approximation Algorithm: A linear-time greedy algorithm approximates the maximum number of equalities within a factor of 1/2.
- Tractable Classes: Specific tractable classes for SOFTALLEQUALmin are identified, including cases related to vertex matching and limited "heavy" values.
Limitations and Future Work
- Theoretical Focus: The paper is primarily theoretical, focusing on complexity analysis and algorithmic design. While practical implications are discussed, empirical evaluation on real-world benchmarks is not presented.
- Specific Cost Metrics: The analysis is limited to two specific cost metrics (graph-based and variable-based). Other cost functions might exhibit different complexities.
- Open Questions: While many gaps are closed, the paper notes that the question of whether the algorithm for BC on ALLDIFFERENT can be adapted to SOFTALLDIFFmin remains open.
- Future Work: The authors suggest exploring applications of their findings to sampling diverse or similar solutions, and further investigating the impact of different cost functions and constraint combinations. The connection to finding robust solutions for problems with uncertain parameters is also highlighted as a promising direction.
Summary updated