A Constraint Programming Approach for $n$-Day Lookahead Playoff Clinching

Technical Summary: A Constraint Programming Approach for n-Day Lookahead Playoff Clinching in the NHL

Problem Definition
The paper addresses the computational challenge of determining "playoff clinching" scenarios in the National Hockey League (NHL). A team is said to have "clinched" if they are guaranteed a postseason spot regardless of the outcomes of any remaining games. While determining if a team has clinched based on the current state of the season (0-day lookahead) is a known NP-Complete combinatorial problem, the authors extend this to "n-day lookahead." This involves identifying the specific combinations of game outcomes over the next $n$ days that guarantee a team's playoff qualification.

The problem is complicated by the NHL's complex qualification structure (two conferences, two divisions per conference, top-three division qualifiers, and two wild cards per conference) and an extensive, hierarchical list of seven tie-breakers (ranging from point percentage to goal differential and goals scored). The complexity increases significantly when considering future games, as the search space grows exponentially with the number of possible game outcomes (six types: regulation win, overtime win, shootout win, shootout loss, overtime loss, regulation loss).

Methodology
The authors propose a two-stage approach combining Constraint Programming (CP) and a custom tree search algorithm.

1. 0-Day Lookahead Subroutine (CP Model):
   The core of the approach is a CP-based model designed to determine if a specific team ($k$) can be mathematically eliminated. The model searches for a "counter-example"—an assignment of outcomes to all remaining games where team $k$ fails to qualify. If no such assignment exists, the team has clinched.

   • Win Assignment Model: This initial phase assigns game outcomes (wins/losses) to determine points and win counts. It incorporates "worst-case" assumptions for team $k$ (losing all remaining games in regulation) to maximize the difficulty of clinching. It uses binary variables to represent rankings and handles tie-breakers (1) through (4) directly.
   • Tie-Group Evaluation & Lazy Constraints: For ties persisting through tie-breaker (4), the model uses "guess" variables ($u_{ij}$) to hypothesize rankings. If the solver's guess conflicts with the actual head-to-head points (tie-breaker 5), a "no-good" constraint is generated to exclude that specific ranking guess, forcing the solver to explore alternative solutions.
   • Goal Assignment Model: If a potential elimination scenario involves ties persisting through tie-breaker (5), a secondary CP model is triggered. This model assigns specific goal scores to games to verify if the tie can be broken by goal differential (tie-breaker 6) or goals scored (tie-breaker 7). This model is only constructed when necessary to avoid computational overhead.

2. n-Day Lookahead Algorithm (Tree Search):
   To determine clinching scenarios over the next $n$ days, the authors employ a tree search where nodes represent specific game outcomes.

   • Presolve Phase: Before searching, the algorithm checks if the team can clinch in an "impossibly optimistic" best-case scenario or if they are eliminated in an "impossibly pessimistic" worst-case scenario. If the answer is definitive, the search is skipped.
   • Tree Traversal & Pruning: The algorithm uses a queue-based search (primarily depth-first) with sophisticated ordering heuristics for games, nodes, and inference algorithms.
   • Pruning Strategies: The search is heavily pruned using the 0-day CP subroutine. If a node represents a state where team $k$ has clinched, all child nodes (further outcomes) are pruned. If the team is eliminated, the node and its children are pruned.
   • Sideways Pruning: A key efficiency gain comes from "sideways pruning." If game outcomes can be ordered by their impact on team $k$ (e.g., a Regulation Win is strictly better than an Overtime Win), and a specific outcome leads to a clinch, all "stronger" outcomes to the right in the search tree are also pruned as they would lead to the same result.

Key Contributions

• Novel 0-Day Approach: The paper introduces a CP model updated for the modern NHL structure (post-2019-20 rules), utilizing a decomposition strategy (win assignment vs. goal assignment) and lazy constraint generation to handle complex tie-breakers efficiently.
• Novel n-Day Algorithm: It presents a custom tree search algorithm that determines concrete $n$-day lookahead scenarios. This approach combines preprocessing, pruning strategies, and node ordering heuristics to manage the combinatorial explosion of future game outcomes.
• Validation and Benchmarking: The methods are validated against official NHL scenarios for $n \in \{0, 1\}$ across four seasons (2021-22 to 2024-25), showing exact matches. The authors report on runtime, pruning efficacy, and scenario complexity.

Results

• Accuracy: The algorithm successfully reproduced all official 0-day and 1-day clinching scenarios published by the NHL for the tested seasons.
• Performance:
  • 0-Day: Solve times are generally low, peaking in the middle of the season when playoff races are tight.
  • 1-Day: The algorithm demonstrates high pruning efficiency (often near 1.0), meaning it explores a very small fraction of the total possible game outcome combinations. However, solve times can vary significantly; the most complex scenario (Boston Bruins, March 2023) required over 25,000 seconds and involved 27 literals.
  • n > 1: The algorithm was tested for $n=2$ and $n=3$ on the 2024-25 season. While computationally feasible for many cases, the time required scales exponentially with the number of relevant games. Scenarios with $n=3$ often resulted in complex outputs (up to 65 literals) that were difficult for stakeholders to interpret, even when solvable within a 30-minute timeout.
• Model Usage: The goal assignment model and lazy constraints are invoked rarely (only in specific tie-breaking scenarios) but are critical for correctness when invoked.

Significance
The paper claims that its primary contribution is providing an automated, mathematically rigorous, and computationally efficient alternative to the manual determination of clinching scenarios, which has become increasingly error-prone due to the NHL's complex tie-breaking rules. The methods enable stakeholders (fans, marketers, teams) to understand precisely under which conditions a team will clinch in the near future. The authors note that while the approach is tailored to the NHL, the underlying CP and tree search techniques are general enough to be adapted for other sports, different qualification metrics (e.g., division titles, President's Trophy), or other seed-specific clinching scenarios. The work highlights the trade-off between computational complexity and the interpretability of the resulting scenarios, particularly as the lookahead window ($n$) increases.