Strong Bounds Consistencies and Their Application to Linear Constraints

Christian Bessiere, Anastasia Paparrizou, Kostas StergiouAAAI 2015 · DOI

Abstract

Standard Bounds Consistency (BC) is the industry standard for linear constraints due to its low computational cost. However, its local focus on individual constraints often misses significant pruning opportunities. This paper introduces rBC2 and rBCall, two relational consistencies that reason about multiple constraints simultaneously. Although enforcing these consistencies is NP-hard, the authors provide efficient polynomial-time approximations through model reformulation and a novel filtering algorithm. Experimental results across random problems, web services matchmaking, and planning benchmarks demonstrate that these methods significantly outperform standard BC in both pruning power and execution time.

Introduction

In Constraint Satisfaction Problems (CSPs), solvers utilize local consistency techniques to prune variable domains. For linear constraints (e.g., $3x + 2y \leq 10$), Bounds Consistency (BC) is preferred for its efficiency. However, BC's "one-at-a-time" approach is a major limitation. When constraints share variables, BC may fail to identify tighter bounds that a global view would reveal. While stronger consistencies exist, they are typically too expensive for the large-scale linear systems found in scheduling and resource allocation.

Relational Bounds Consistencies

To bridge this gap, the authors define two relational consistencies:

  1. rBC2: Ensures every bound has support satisfying pairs of overlapping constraints.
  2. rBCall: A stricter version considering support across all constraints simultaneously.
Hierarchy of local consistencies showing the theoretical strength relationships between standard BC, SBC, and the proposed relational consistencies.

As illustrated in Figure 1, these consistencies are strictly stronger than standard BC. To make them practical, the authors propose two polynomial-time approximations:

  • Constraint Reformulation (rBC2-Y / rBCall-Y): This approach identifies shared subexpressions and introduces auxiliary variables. By applying standard BC to this expanded model, the solver implicitly performs relational reasoning.
  • The rBC2-A Algorithm: A specialized filtering algorithm that computes interval projections for intersecting constraints dynamically. A high-speed variant, rBC2-wA, is also introduced.

Experimental Evaluation

The methods were tested on random linear problems, real-world web services matchmaking (100–1,500 variables), and 15-puzzle planning benchmarks.

Performance comparison of BC, SBC, and relational consistencies across various linear inequality and equation problem classes, showing time and node counts.

Key Results

  • Order of Magnitude Speedups: On random linear equations, the proposed techniques were often 10x to 20x faster than standard BC. This efficiency stems from reducing the search tree size by up to two orders of magnitude (see Figure 4).
  • Scalability: In web services benchmarks, while standard BC performance degraded exponentially with variable count, rBC2-A and rBC2-Y maintained near-linear performance.
  • Planning Efficiency: For 15-puzzle lower-bound calculations, the rBC2-wA algorithm was roughly 8x faster than standard BC.

Discussion and Conclusion

The core insight is that for linear constraints, the most significant pruning gains come from analyzing constraint intersections. Even though the theoretical problem is NP-hard, linear structures allow polynomial approximations to capture nearly all pruning benefits.

While powerful, these methods have trade-offs. Model reformulation (rBC2-Y) is fast for sparse problems but can lead to memory issues in dense ones. Additionally, on very simple instances, the overhead of advanced intersection checks may occasionally outweigh the pruning benefits. Future research will explore extending these relational consistencies to other global constraints.

Summary updated

BibTeX
@inproceedings{bessiere2015strong,
  author = {Christian Bessiere and Anastasia Paparrizou and Kostas Stergiou},
  title = {{Strong Bounds Consistencies and Their Application to Linear Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9756},
}
Figure