Abstract
ASAP.V2 and ASAP.V3 are advanced algorithm selection systems designed to handle the "algorithm portfolio" problem by combining a fast, global pre-scheduler with a machine learning-based algorithm selector. By sequentially optimizing these components, the system ensures that the pre-scheduler handles "easy" instances while providing behavioral features that enhance the selector's ability to solve "hard" instances. This approach yields a robust and computationally efficient framework for diverse problem domains.
Introduction
In computational problem-solving, the "algorithm portfolio" problem highlights that no single algorithm is universally optimal across all instances of complex tasks like SAT solving or constraint programming. Algorithm Selection (AS) aims to mitigate this by predicting the most suitable algorithm for a given instance. A standard architecture for AS involves a two-stage process: a pre-scheduler for quick wins on easy instances and a machine learning selector for the remaining difficult ones. However, these modules are often interdependent; training them in isolation leads to inefficiencies. ASAP (Algorithm Selector And Prescheduler) addresses this by jointly and sequentially optimizing both components to maximize overall performance.
Methods and Architecture
The core of the ASAP system is a four-step sequential optimization process designed to create a complementary relationship between the pre-scheduler and the algorithm selector.
1. Initial Pre-scheduler ($PS_{ini}$)
The process begins by building a simple schedule of algorithms with short timeouts. The goal is to maximize the number of instances solved within a minimal time budget. This budget is determined dynamically using a "knee detection" heuristic on a cumulative performance curve, identifying the point where additional time yields diminishing returns in solved instances.
2. Initial Algorithm Selector ($AS_{ini}$)
A Random Forest regression model is trained to predict algorithm performance (measured by PAR10 scores). A key innovation here is the use of "behavioral features"—the successes and failures observed during the $PS_{ini}$ phase—as additional training data for the selector.
3. Fine-tuned Pre-scheduler ($PS_{opt}$)
The pre-scheduler's timeouts are then refined using CMA-ES (Covariance Matrix Adaptation Evolution Strategy). The optimization objective is to minimize the joint runtime of both the pre-scheduler and $AS_{ini}$. This step ensures the pre-scheduler focuses on instances the selector might struggle with, rather than wasting time on instances the ML model can already solve efficiently.
4. Final Algorithm Selector ($AS_{opt}$)
Finally, a second Random Forest model is trained using the behavioral features generated by the optimized $PS_{opt}$, resulting in the final integrated system.
Version Differences and Data Handling
ASAP.V2 utilizes a fixed number of algorithms ($\kappa = 3$) in the pre-scheduler, while ASAP.V3 dynamically optimizes $\kappa$ (between 1 and 4). To handle missing feature data—a common issue in real-world scenarios—ASAP employs mean imputation supplemented by boolean flags that indicate the specific reason for the data's absence (e.g., timeout vs. crash), preserving valuable diagnostic signals.
Key Insights
- Behavioral Probing: The pre-scheduler serves a dual purpose: solving easy instances and acting as a low-cost probe. The outcomes of these initial runs provide highly predictive features for the downstream selector.
- Joint Optimization: By optimizing the pre-scheduler against the selector's performance, the system eliminates redundant effort, ensuring each component specializes in the instances it handles best.
- Informative Missingness: Treating the cause of missing data as a feature itself allows the system to leverage information that standard imputation techniques typically discard.
Performance and Efficiency
As a submission to the Open Algorithm Selection Challenge (OASC 2017), ASAP was designed for high scalability, supporting up to 10,000 instances and 30 algorithms. ASAP.V2 demonstrates high efficiency, training in under 30 minutes on standard hardware (Intel Xeon @2.6 GHz). ASAP.V3, with its more intensive dynamic optimization of $\kappa$, requires approximately 3 hours.
Conclusion and Limitations
While ASAP provides a robust framework for algorithm selection, it faces challenges such as potential overfitting on small datasets. The authors mitigate this through Random Forest regularization techniques. Future iterations aim to further automate hyperparameter selection, building on the progress made between V2 and V3.
Summary updated