A Soft Global Precedence Constraint

David Lesaint, Deepak Mehta, Barry O'Sullivan, Luis Quesada, Nic WilsonIJCAI 2009

Abstract

This paper introduces SOFTPREC, a novel global constraint designed to efficiently handle "soft" precedence rules in optimization problems. By employing polynomial-time pruning rules and a "forward cost" mechanism to estimate penalties, the proposed method achieves significant performance gains. Evaluation on telecommunication feature configuration and minimum cutset problems shows up to a 10x speedup and a 100x reduction in search nodes compared to previous state-of-the-art techniques.

Introduction

In complex system configurations, such as telecommunications feature subscription, users often have preferences (soft constraints) that may conflict with mandatory system rules (hard constraints). For instance, a user might prefer "Voicemail" to precede "Call Divert," while the system mandates the opposite to prevent infinite loops. Resolving these conflicts to find an optimal compromise—minimizing the penalty for discarded preferences—is a specific type of Constraint Optimization Problem (COP).

This problem generalizes the NP-hard "minimum cutset problem." Traditional Constraint Programming (CP) approaches often struggle with efficiency because they treat each precedence rule in isolation, failing to exploit the global structure of the constraints.

Methodology: The SOFTPREC Global Constraint

The authors propose SOFTPREC, a global constraint that views the entire set of precedence rules simultaneously. This "global vision" allows for more effective pruning of the search space.

Pruning and Forward Costs

Enforcing perfect consistency (Generalized Arc Consistency) is NP-complete for this problem. Instead, SOFTPREC uses polynomial-time pruning rules based on transitivity and asymmetry. The core innovation is the use of forward costs. The algorithm constructs an "incompatibility graph" where nodes represent features and edges represent conflicts.

Incompatibility graph partitioned into independent components C1 and C2 to calculate forward costs.

By decomposing this graph into independent connected components (as seen in Figure 1), the solver can calculate a guaranteed minimum penalty—the forward cost—required to resolve conflicts within each component. Summing these costs provides a much tighter lower bound on the objective function than standard techniques.

Experimental Evaluation

The researchers benchmarked SOFTPREC against two primary datasets:

  1. Feature Subscription Benchmarks: Synthetic catalogues and subscriptions mimicking real-world telecom configurations with up to 45 features.
  2. Minimum Cutset Problems: Standard graph-theory instances used in prior literature.

Results and Discussion

SOFTPREC demonstrates superior performance in both speed and search efficiency. On hard feature subscription instances, it outperformed the previous best CP approach (Restricted Singleton Arc Consistency, or RSAC) by a factor of 5 to 11.

Comparison of search nodes explored by RSAC, Barták and Čepek (2008), and the proposed SP (SoftPrec) algorithm.

As shown in Figure 6, SOFTPREC (labeled SP) reduces the number of search nodes by approximately two orders of magnitude compared to specialized filtering algorithms. Furthermore, the most advanced forward cost calculation methods ($SP_4$) were found to reduce the nodes visited by nearly 70% compared to simpler versions, justifying the additional computational overhead of the pruning logic.

Conclusion

SOFTPREC provides a powerful framework for solving optimization problems with soft precedence constraints. By treating the problem globally and utilizing incompatibility-based forward costs, it offers a significant leap in solver performance. Future work will explore direct comparisons with SAT solvers and the development of even tighter bounds by analyzing complex cycle structures within the precedence graph.

Summary updated

BibTeX
@inproceedings{lesaint2009soft,
  author = {David Lesaint and Deepak Mehta and Barry O'Sullivan and Luis Quesada and Nic Wilson},
  title = {{A Soft Global Precedence Constraint}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure