New Techniques for Algorithm Portfolio Design

Matthew J. Streeter, Stephen F. SmithUAI 2008

TL;DR

This paper introduces a novel approach to algorithm portfolio design that simultaneously tackles both the scheduling of heuristic runs and the machine learning aspect of predicting which heuristic will perform best. By integrating these two components, the authors demonstrate significant performance improvements on challenging NP-hard problems like Boolean satisfiability, integer programming, and AI planning, outperforming state-of-the-art individual solvers.

What Problem Does This Paper Address?

Many real-world computational problems are NP-hard, meaning they are theoretically intractable for large instances. However, practical instances can often be solved efficiently using specialized heuristics. The challenge is that no single heuristic performs best on all instances. When faced with a new problem instance, we have a set of available heuristics, each with a known (or estimable) performance profile on similar past instances. The core problem is to decide how to best allocate limited computational resources (CPU time) to these heuristics to solve the current instance as quickly as possible. This involves two key decisions: which heuristic to run, and for how long before switching to another. Previous work often addressed these aspects in isolation, either focusing on scheduling strategies or on using machine learning to predict the best heuristic. This paper aims to bridge this gap by developing a unified approach.

Methods

The paper proposes an integrated approach to algorithm portfolio design, combining machine learning for heuristic selection with scheduling strategies.

  • Scheduling Models: They define two models for running heuristics:
  • Suspend-and-resume: A heuristic can be paused and later resumed, retaining its state.
  • Restart: A heuristic is run from scratch each time, potentially with a new random seed if it's randomized.
  • Offline Greedy Algorithm: For a fixed set of training instances with known heuristic performance, a greedy algorithm constructs a schedule by iteratively adding the heuristic-time pair that maximizes the expected number of solved instances per unit time. This algorithm provides a 4-approximation to the optimal schedule.
  • Online Greedy Algorithm (OG): For a sequence of instances arriving one by one, this algorithm learns an effective schedule on-the-fly. It's an online version of the greedy approach, with performance guarantees that approach the offline optimum as the number of instances grows.
  • Exploiting Features (OGse): This is the core novel contribution. It leverages instance-specific features (e.g., problem size, structure) to tailor the schedule. It uses a "sleeping experts" framework, where each feature is treated as an expert. An online algorithm (OG) is run for each feature, and a meta-algorithm selects which feature-specific schedule to follow. This allows for dynamic adaptation of the schedule based on instance characteristics.
  • Anytime Algorithms: The paper extends its framework to "anytime algorithms" that improve their solution quality over time. By defining multiple objectives (e.g., finding a solution with cost $\alpha$ times optimal for various $\alpha$), they transform the problem into a set of fictitious instances, allowing the scheduling framework to find schedules that yield good solutions quickly and prove optimality efficiently.

Datasets

The paper evaluates its techniques using data from three real-world solver competitions:

  • SAT 2007: Boolean satisfiability instances, including industrial, random, and handcrafted benchmarks. Features used included formula size, clause-to-variable ratio, and literals per clause.
  • IPC-5 (International Planning Competition): AI planning instances from the optimal planning track, using the STRIPS language. Features were based on planning domain, number of goals, objects, and initial predicates.
  • PB'07 (Pseudo-Boolean Optimization): Zero-one integer programming instances, including optimization and decision problems.

The authors note that for these competitions, the number of heuristics was often too large for brute-force dynamic programming, making their approach more relevant.

Key Insights and Ideas

  • The Synergy of Scheduling and Learning: The most significant insight is that effectively solving NP-hard problems requires a tight integration of what heuristic to run (learning) and how to run it (scheduling). Treating these as separate problems leaves performance on the table.
  • Feature-Driven Scheduling is Powerful: Instance-specific features are crucial for achieving near-optimal performance. The "sleeping experts" approach allows portfolios to adapt dynamically to different types of problems, outperforming both pure scheduling and pure feature-based heuristic selection.
  • Practical Performance Gains: Even with a relatively small number of training instances, the proposed greedy scheduling approach can significantly outperform the best individual heuristic and naive parallel execution.
  • Suspend-and-Resume vs. Restart: While the suspend-and-resume model offers a slight advantage, the restart model is often competitive, suggesting that the overhead of state management might sometimes outweigh its benefits.
  • Anytime Algorithms Benefit from Portfolio Design: The framework effectively extends to anytime algorithms, enabling schedules that not only find solutions quickly but also prove optimality efficiently.

Key Results

  • Significant Speedups: The proposed techniques achieved substantial speedups. For example, on PB'07 optimization problems, the greedy schedule outperformed the fastest individual solver by more than a factor of 2.
  • Near-Optimal Performance with Features: The "Greedy w/features" approach consistently outperformed pure scheduling or purely feature-based heuristic selection across SAT and AI planning benchmarks.
  • Few Training Instances Needed: Experimental results showed that only a small number of training instances (e.g., 16 for PB'07) were sufficient to derive schedules that outperformed baseline approaches.
  • Anytime Algorithm Improvements: For PB'07 data, the portfolio approach yielded speedups of 1.2x to 3.7x across different objectives (finding feasible, finding optimal, proving optimality) compared to individual heuristics.

Limitations and Future Work

  • Ignoring Dynamic Scheduling: The current work does not dynamically adjust schedules based on the observed behavior of heuristics during execution (e.g., progress bars).
  • No Information Sharing: The approach does not allow heuristics to share information (like bounds on optimal values) during execution.
  • Artificial Time Bounds: The online algorithm relies on an artificial bound $B$ on CPU time per instance to guarantee performance.
  • Future Directions: The authors suggest exploring dynamic scheduling based on heuristic state, sharing information between heuristics, and potentially using more sophisticated feature engineering. They also note that their experimental results for the number of training instances needed were much better than theoretical worst-case bounds, suggesting room for tighter theoretical analysis.

Summary updated

BibTeX
@inproceedings{streeter2008new,
  author = {Matthew J. Streeter and Stephen F. Smith},
  title = {{New Techniques for Algorithm Portfolio Design}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure