Abstract
In modern telecommunications, the proliferation of user-defined features leads to the "feature interaction problem," where service requests may conflict with network rules or other features. This paper models service personalization as a combinatorial optimization task, specifically seeking the "optimal relaxation" of inconsistent user requests. By comparing Constraint Programming (CP), Partial Weighted Max-SAT (PWMSAT), and Integer Linear Programming (ILP), we demonstrate that CP provides superior performance, solving 100% of test instances and scaling effectively to complex configurations.
The Feature Interaction Problem
In modern telecommunications protocols like SIP, "features" are modular increments of functionality, such as call-waiting, caller ID screening, or "find-me" services. While users desire the flexibility to mix and match these services, their combination often leads to conflicts—a challenge known as the Feature Interaction Problem.
For instance, a user might enable "Do Not Disturb" while simultaneously requesting a "Welcome Announcement" for incoming callers. In Distributed Feature Composition (DFC) architectures, these features are sequenced into "zones." If a user's requested sequence creates logical cycles or violates technical precedence rules, the subscription becomes inconsistent.
The core challenge is finding the "optimal relaxation": when a request is technically impossible, the system must automatically identify a legal configuration that preserves as many high-priority user preferences as possible.
Methods
The authors formalize feature composition as a graph-based configuration problem. Features are represented as nodes, and precedence requirements (e.g., "Feature A must precede Feature B") are directed edges. A configuration is deemed consistent if the resulting graph is acyclic.
To solve the optimization task of maximizing the total weight of included features and rules, three mathematical approaches were evaluated:
- Constraint Programming (CP): Utilizing the Choco library with a depth-first branch-and-bound algorithm and Generalized Arc Consistency (GAC) for efficient search space pruning.
- Partial Weighted Max-SAT (PWMSAT): Using the SAT4J library to treat the problem as a set of hard and soft boolean logic clauses.
- Integer Linear Programming (ILP): Employing the industry-standard IBM ILOG CPLEX solver.
The primary innovation is the CP formulation, which leverages "restricted singleton generalized arc consistency" on boolean variables to significantly reduce search time.
Datasets and Evaluation
Due to the proprietary nature of large-scale feature catalogues, the study used randomly generated catalogues and feature subscriptions (RFS):
- Catalogues: Up to 50 features and 750 technical constraints.
- Subscriptions: Tested scenarios with up to 50 features and varying user-defined precedence rules.
- Weights: Features and rules were assigned integer weights (1–4) to simulate user priorities.
Key Results
The experimental results demonstrate a clear advantage for the Constraint Programming approach across all metrics.
- Reliability: The CP solver was the only method to solve 100% of the test instances within the 4-hour time limit.
- Scalability: As complexity grew (45–50 features), both ILP (CPLEX) and SAT solvers frequently timed out.
- Speed: For complex scenarios (e.g., 45 features with 90 user rules), CP found the optimal solution in approximately 336 seconds (336,076 ms), while competing solvers either failed or were significantly slower.
Key Insights
- Personalization as Relaxation: The system shifts from simple error-checking to automated resolution by finding the "closest" legal state to a user's request.
- Consistency Levels: Fine-tuning the level of local consistency in CP allows it to navigate the search space much faster than general-purpose ILP or SAT solvers.
- Anti-subscriptions: The concept of an "anti-subscription"—the set of excluded features—provides a formal mechanism to explain to users why certain preferences could not be met.
Limitations and Future Work
While the current model effectively handles subscription-time configuration, future work is needed to address "context-rich" subscriptions where features change based on dynamic factors like user location or schedule. Additionally, while random data is a standard benchmark, real-world telecom catalogues may have different structures that impact solver performance. Finally, the researchers aim to explore how to best present these mathematical trade-offs to non-technical end-users.
Summary updated