Abstract
This paper introduces Hybrid Constraint Tightening (HCT), a preprocessing algorithm designed to accelerate solvers for complex scheduling problems. By mathematically "lifting" implicit temporal constraints and making them explicit before the search begins, HCT enables standard solvers to prune impossible schedules early, resulting in speedups of up to 96x.
The Challenge of Hybrid Scheduling
Scheduling is a notoriously difficult task because it requires balancing two distinct types of logic: Finite-Domain (the "what" and "where," such as topics and rooms) and Temporal (the "when," such as start times and durations). In real-world scenarios, these domains are often interdependent. For instance, a conference session on "Quantum Computing" might require two hours, while an introductory workshop requires only one.
Most solvers fail to recognize that a session will take at least one hour until they have already assigned a specific topic. If the overall schedule only has 30 minutes remaining, a solver might waste significant computation time testing different topics before realizing none can fit. While previous "least-commitment" approaches attempted to address this during the search phase, they are computationally expensive and require modifying core search algorithms.
The HCT Algorithm
The authors propose HCT as a modular preprocessing step that tightens the problem description itself rather than altering the solver's search mechanism. The algorithm operates in three primary stages:
- Grouping: Constraints involving the same temporal variables (e.g., all constraints affecting the duration of "Session A") are grouped using a hash function.
- Sorting: Within these groups, constraints are ordered by the restrictiveness of their temporal bounds.
- Reformulation (The "Lifting" Trick): This core innovation identifies commonalities across constraints. If Topic A requires 3 hours and Topic B requires 2 hours, HCT "lifts" this information to create a new global constraint: "This session requires at least 2 hours, regardless of topic."
By explicitly stating these minimum requirements upfront, the solver can immediately prune time slots that are too small without needing to assign a specific topic first.
Evaluation and Key Insights
The approach was evaluated using 1,500 randomly generated Hybrid Scheduling Problems (HSP) modeled after realistic AI conference scenarios. The tests included complex constraints that exceeded the capabilities of previous frameworks, demonstrating HCT's broad applicability.
Two key insights drive HCT's success:
- Ordinal Bounds: Temporal bounds have a natural order (a requirement of $\le 5$ implies $\le 10$). HCT exploits this to pull the loosest common bound out of specific cases.
- Preprocessing Efficiency: By making the data "smarter" before the search starts, HCT maintains a low complexity of $O(H \log H)$ while keeping the solver modular.
Results
The performance gains observed when applying HCT preprocessing to a standard solver were dramatic:
- Speedup: The solver was 96 times faster on average.
- Search Efficiency: Node visits dropped by 93.8x, and backtracks—where the solver hits a dead end and must reverse—plummeted by 411.8x.
- Reliability: Without HCT, the solver completed only 87.6% of problems within a 2.5-minute limit. With HCT, it achieved a 100% completion rate, often finishing in a fraction of a second.
Limitations and Future Work
While HCT shows immense promise, its effectiveness likely scales with the "constrainedness" of the problem; in very loose schedules, the minimal overhead of preprocessing might not be necessary. Future research aims to generalize HCT to any hybrid problem where variable values have inherent ordinal meanings, such as cost, weight, or size, extending the benefits of constraint tightening beyond the temporal domain.
Summary updated