Abstract: This paper introduces "reconstitution," a novel paradigm for generating effective admissible search heuristics. While traditional heuristics often rely on problem abstraction—ignoring constraints to simplify computation—this approach selectively reintroduces ignored details to tighten lower-bound estimates. Applied to project scheduling, the resulting Reconstituted Critical Path (RCP) heuristic demonstrates significant pruning power, reducing search states and computation time by orders of magnitude compared to standard critical path methods.
Introduction
In pathfinding and optimization, an admissible heuristic serves as a lower-bound estimate of the remaining cost to reach a goal. If the heuristic never overestimates this cost, algorithms like A are guaranteed to find optimal solutions. Historically, these heuristics are generated through abstraction*: removing constraints to make a problem easier to solve (e.g., ignoring tile collisions in the 8-puzzle to calculate Manhattan Distance).
The primary challenge lies in the "accuracy vs. efficiency" trade-off. High-level abstractions are fast to compute but provide loose bounds, leading to an exponential explosion of states to explore. Conversely, low-level abstractions are more accurate but can be as computationally expensive as the original problem. This research proposes a middle ground: starting with a high-level abstraction and strategically adding back just enough detail to tighten the bound without sacrificing computational speed.
The Reconstitution Paradigm
The core innovation is a three-step process: Abstract → Solve → Reconstitute. Instead of attempting to solve a complex problem in its entirety, the system solves a simplified version and then "patches" the solution by identifying which original constraints were violated.
As shown in Figure 1, the process maps the original problem state ($s$) to an abstracted state ($s'$). After finding a path in the abstracted space, the algorithm reconstitutes specific details ($s'_r$) to create a more accurate estimate for the original goal ($g$). This allows for a "selective detail" approach where only the most impactful constraints are reintroduced.
Application: Project Scheduling
The authors demonstrate this paradigm using Project Scheduling, an NP-hard problem involving jobs with specific durations, precedence requirements (Job A must finish before B), and mutual exclusion constraints (Job C and D cannot overlap due to shared resources).
- The Base (Abstraction): The process starts with the Critical Path (CP) heuristic. This ignores all resource/mutual exclusion constraints and only considers precedence. While fast ($O(n)$), it frequently underestimates project duration.
- The Innovation (RCP): The Reconstituted Critical Path (RCP) heuristic first calculates the standard CP. It then traverses that path backward to identify "unsatisfied" mutual exclusion constraints. If a job not on the critical path must be delayed due to a resource conflict with a job on the critical path, the algorithm calculates the minimum necessary overlap and adds it to the total duration estimate.
This keeps the heuristic computation efficient ($O(n^2)$) while providing a much tighter bound by focusing only on constraints that directly impact the current critical path.
Experimental Results
The heuristics were evaluated using IDA* on sets of randomly generated project scheduling problems with varying numbers of jobs (30 to 40) and mutual exclusion constraints (0 to 40).
The results in Figure 4 highlight a dramatic performance gap as problem complexity increases:
- Pruning Power: In a 30-job problem with 25 mutual exclusions, the standard CP heuristic required expanding 6,242 states, whereas the RCP heuristic required only 54 states.
- Computational Efficiency: For the same problem, CP took 1,651.53 seconds to find a solution, while RCP achieved the same result in just 30.67 seconds—a roughly 50x speedup.
- Scalability: As constraints increased, CP's performance degraded exponentially. In contrast, RCP remained relatively stable, proving that reconstitution effectively manages search space complexity.
Conclusion and Future Work
The reconstitution paradigm offers a powerful method for generating heuristics that are both accurate and efficient. By selectively adding detail to an abstracted solution, the RCP heuristic prevents the exploration of millions of redundant states.
Future research aims to extend this model to handle complex resource pools (beyond simple mutual exclusion) and temporal constraints like deadlines. A significant long-term goal is the automation of the reconstitution logic, allowing systems to independently discover which details are most critical to reintroduce for any given problem domain.
Summary updated