PaperlayerView exact revision on arXiv

Source-linked AI summary

ParamILS: An Automatic Algorithm Configuration Framework

Frank Hutter, Thomas Stuetzle, Kevin Leyton-Brown, Holger H. Hoos

arXiv:1401.3492v1cs.AI

TL;DR

Manual parameter tuning for complex heuristic algorithms is labor-intensive. The paper presents ParamILS with adaptive capping and finds substantially better configurations than carefully chosen defaults, sometimes by two orders of magnitude on unseen instances.

  • Problem

    Finding performance-optimizing parameter settings for complex heuristic algorithms is highly labor-intensive, motivating automated configuration methods.

  • Method

    ParamILS uses stochastic local search with adaptive capping to configure ordinal and categorical parameters while avoiding unnecessary algorithm runs.

  • Results

    Configurations found by ParamILS almost always outperformed carefully chosen defaults on unseen test instances, by up to two orders of magnitude in some scenarios.

  • Takeaways & Limitations

    ParamILS can identify strong, instance-set-specific configurations for high-performance SAT algorithms and CPLEX without requiring intimate knowledge of their parameters.

  • Takeaways & Limitations

    ParamILS requires externally configurable parameters and finite parameter domains, with numerical parameters discretized into finitely many choices.

Abstract

from arXiv · show

The identification of performance-optimizing parameter settings is an important part of the development and application of algorithms. We describe an automatic framework for this algorithm configuration problem. More formally, we provide methods for optimizing a target algorithm's performance on a given class of problem instances by varying a set of ordinal and/or categorical parameters. We review a family of local-search-based algorithm configuration procedures and present novel techniques for accelerating them by adaptively limiting the time spent for evaluating individual configurations. We describe the results of a comprehensive experimental evaluation of our methods, based on the configuration of prominent complete and incomplete algorithms for SAT. We also present what is, to our knowledge, the first published work on automatically configuring the CPLEX mixed integer programming solver. All the algorithms we considered had default parameter settings that were manually identified with considerable effort. Nevertheless, using our automated algorithm configuration procedures, we achieved substantial and consistent performance improvements.

1. Introduction

Algorithm parameter settings strongly influence heuristic-algorithm performance, yet configuring them manually is labor-intensive. The paper introduces ParamILS and adaptive capping, and reports improved configurations and comparative performance across complex algorithms.

  • Motivation: Parameter settings control important aspects of high-performance algorithms, especially heuristic procedures for computationally hard problems.CPLEX version 10 has about 80 user-configurable parameters affecting its search mechanism.
  • Motivation: Manual parameter configuration can consume a large fraction of algorithm development time, whereas automation can save time and potentially improve results.This motivates replacing manual, ad-hoc configuration with automated methods.
  • Motivation: Automatic configuration can make algorithm comparisons more meaningful by reducing performance differences caused by unequal parameter optimization.It can also help end users who lack knowledge about parameter impacts and rely on defaults.
  • Contributions: ParamILS is a versatile stochastic local-search framework with BasicILS and FocusedILS instantiations, complemented by adaptive capping for avoiding unnecessary algorithm runs.Adaptive capping develops bounds on the performance measure and includes trajectory-preserving and heuristic variants.
  • Results: BasicILS outperforms random search and simple local search, while FocusedILS provides further improvements over BasicILS.The paper also presents extensive evidence that ParamILS substantially improves configurations of complex, highly optimized algorithms, including CPLEX.
  • Applications: The paper surveys ParamILS applications spanning complete and incomplete heuristic search algorithms for SAT, MPE, protein folding, university timetabling, and algorithm configuration.In three cases, ParamILS was integral to algorithm design and enabled exploration of very large configuration spaces.

2. Problem Statement and Notation

The section formalizes algorithm configuration as selecting parameter values that minimize a statistical cost over problem instances and runs. It defines candidate costs, configurator estimates, and separate training and test performance, noting that training performance is biased when selection and evaluation reuse instances.

  • Problem definition: Algorithm configuration seeks parameter values that optimize a target algorithm’s performance on a specified input-data distribution.The framework distinguishes target algorithms from configuration procedures that conduct the optimization.
  • Parameter space: Parameter domains are finite sets, with numerical parameters discretized as needed; ordered domains are treated effectively as categorical.The formulation also supports conditional parameter dependencies, allowing irrelevant subordinate parameters to be collapsed into equivalence classes.
  • Configuration procedures: A configurator evaluates target-algorithm runs and uses observed costs to choose subsequent configurations, while estimating each configuration’s cost from runs using that configuration.For expected runtime, the estimate is the sample mean runtime of the corresponding runs.
  • Formal problem definition: The formal problem instance is the 6-tuple ⟨A, Θ, D, κmax, o, m⟩, comprising an algorithm, parameter space, instance distribution, captime, cost function, and statistical population parameter.Each configuration θ ∈ Θ is a candidate solution, and its cost is determined from the distribution of observed run costs.
  • Training and test performance: Training performance is biased because the same instances select and evaluate the incumbent, so unbiased offline evaluation uses a fixed, previously unseen test set and random seeds.The incumbent is the configuration currently believed to have the lowest cost.

3. ParamILS: Iterated Local Search in Parameter Configuration Space

ParamILS automates local search over algorithm parameter configurations by combining iterative first improvement with perturbations, acceptance criteria, and random restarts. FocusedILS addresses the trade-off between evaluation cost and reliable comparison by adaptively allocating runs, with convergence to the true optimum under consistent cost estimation.

  • ParamILS framework: The initial formulation fixes the benchmark set and per-configuration cutoff times, reducing configuration to minimizing mean runtime on the benchmark set.The framework postpones the question of how many runs should evaluate each configuration.
  • ParamILS framework: ParamILS searches parameter configuration space using iterative first improvement, fixed-size random perturbations, acceptance of better or equally good configurations, and probabilistic random restarts.Its neighbourhood changes one parameter value at a time, and initialization combines default and random settings.
  • BasicILS: BasicILS(N) compares configurations by evaluating every one on the same N training instances with the same random-number seeds.This fixed-training-set estimate addresses stochastic optimization but can be inefficient or generalize poorly when N is poorly chosen.
  • FocusedILS: FocusedILS adaptively varies the number of runs N(θ) used to estimate each configuration’s cost, avoiding a single fixed evaluation budget for all configurations.This targets the trade-off between slow search with enormous training sets and poor generalization from overly small training sets.
  • FocusedILS: Under consistent cost estimation, FocusedILS samples every configuration unboundedly often and finds the true optimal configuration with probability approaching one as iterations increase.The unbounded-evaluation result relies on positive-probability random restarts, while the convergence guarantee combines this property with asymptotically error-free comparisons.

4. Adaptive Capping of Algorithm Runs

This section introduces adaptive capping for ParamILS, which limits configuration-evaluation time using performance bounds. Trajectory-preserving capping retains BasicILS’s search trajectory while aggressive capping can terminate poor configurations earlier for potentially better practical performance.

  • Adaptive capping: Adaptive capping limits time spent evaluating parameter configurations by terminating runs once available results establish that a configuration cannot outperform the relevant bound.For mean non-negative costs, Procedure objective sequentially runs a configuration and computes a lower bound after each run.
  • Trajectory-preserving capping: Trajectory-preserving capping computes the same comparison function as uncapped BasicILS, preserving its search trajectory while typically reducing runtime.The saved time allows BasicILS to search a larger portion of the parameter configuration space within the same overall runtime.
  • Aggressive capping: Aggressive capping bounds evaluations using the incumbent’s performance multiplied by a bound multiplier, allowing poorly performing configurations to be terminated at any time.When both configurations are terminated preemptively, the one that solved more instances within the allowed time is considered better.
  • Aggressive capping: With bm = ∞, aggressive capping reduces to trajectory-preserving capping; with bm = 1, evaluation stops once a configuration is known to be worse than the incumbent.The experiments used bm = 2, under which evaluation stops when a configuration’s lower performance bound exceeds twice the incumbent’s performance.
  • Extension to FocusedILS: Adaptive capping also extends to FocusedILS by maintaining separate bounds for each number of runs used in pairwise comparisons.This supports both trajectory-preserving and aggressive capping despite FocusedILS’s varying evaluation budgets.

5. Experimental Preliminaries

This section introduces the computational experiments by outlining their design, configuration scenarios, and low-level experimental setup.

  • Experimental Preliminaries: The section provides background for the computational experiments presented in subsequent sections.It covers experimental design, algorithm/benchmark configuration scenarios, and low-level setup details.

5.1 Experimental Design

The experiments minimized penalized mean runtime over a training distribution, using matched instance-seed evaluations, disjoint testing, repeated independent runs, and paired statistical comparisons. This design supported adaptive capping and reduced noise when comparing configurations.

  • Objective function: The study optimized mean runtime over instances drawn from a distribution D, an objective that also supports effective adaptive capping.The correlation between configuration cost and estimation time makes adaptive capping effective.
  • Objective function: Mean-runtime minimization produced robust configurations with competitive median runtimes, whereas median-runtime minimization timed out on a large but under-50% fraction of benchmark instances.These findings came from preliminary experiments comparing the two aggregation objectives.
  • Objective function: Timeouts were handled with penalized average runtime, counting each unsuccessful run as p · κmax; the study used p = 10.PAR is the mean runtime with unsuccessful runs replaced by the penalized cutoff value.
  • Instance and seed selection: Configuration used half of each benchmark as training data, reserving the remaining instances exclusively for testing the resulting parameter configurations.This separation evaluated configurations on a disjoint test set.
  • Instance and seed selection: Comparisons used identical instances and random seeds, with typically 25 independent runs per procedure and a two-sided paired Max-Wilcoxon test at p < 0.05.Shared run-specific instance-seed lists controlled noise, and paired testing accounted for this matched design.

5.2 Configuration Scenarios

The study evaluates ParamILS across five BROAD configuration scenarios combining three target algorithms with benchmark instances from SAT and mixed integer programming. The scenarios use controlled parameter selections and separate training and test instances.

  • Scenario design: Five BROAD scenarios combine high-performance algorithms with widely studied benchmark datasets for evaluating the configurators.The scenarios are analyzed in Section 6, with five-second per-run cutoff times.
  • Target algorithms: The target algorithms are SAPS, SPEAR, and CPLEX 10.1.1, spanning dynamic local search, tree search, and mixed integer programming.SAPS has relatively few parameters; SPEAR is a state-of-the-art solver for industrial instances; CPLEX has 81 search-trajectory parameters selected from 159 user-specifiable parameters.
  • Benchmark instances: The benchmark sets cover SAT-encoded quasi-group completion, SAT-encoded small-world graph colouring, and MIP-encoded combinatorial-auction winner determination.The study applied the algorithms to three benchmark families, with 2000 instances in each experimental set, split evenly into training and test sets.
  • Benchmark instances: The QCP benchmark varies order n from [26, 43] and holes H from [1.75, 2.3] · n1.55 around the solubility phase transition.The QCP set was generated using parameters from prior work and contained 23 000 instances.
  • Benchmark instances: The SW-GCP and Regions100 benchmarks respectively use sampled small-world graph-colouring instances and MILPs generated with 100 goods and 500 bids.The Regions100 instances averaged 501 variables and 193 inequalities; the SW-GCP instances averaged 1813 variables and 13 902 clauses.

5.3 Experimental Setup

Experiments ran on a 55-node Xeon cluster under OpenSuSE Linux, with runtimes measured as CPU time; Ruby-script overhead was excluded from configuration time, though it could be substantial in easy scenarios.

  • Experimental platform: Experiments used 55 dual 3.2GHz Intel Xeon PCs with 2MB cache and 2GB RAM running OpenSuSE Linux 10.1.Runtimes were measured as CPU time on these reference machines.
  • Implementation and timing: Ruby scripts implemented the configuration procedures, and their runtime was excluded from configuration time.
  • Implementation and timing: In easy configuration scenarios, where most algorithm runs finish in milliseconds, script overhead could be substantial.

6. Empirical Evaluation of BasicILS, FocusedILS and Adaptive Capping

Across five BROAD scenarios, BasicILS and FocusedILS produced substantial speedups over default configurations, while experiments showed that local-search structure and adaptive capping were key contributors. FocusedILS often outperformed BasicILS(100), although adaptive capping narrowed this gap in some scenarios.

  • Overall comparison: BasicILS(100) and FocusedILS achieved very substantial speedups over default configurations across all five BROAD scenarios.Examples include SAPS-SWGCP: 531s vs 0.15s; 499 vs no timeouts, and SPEAR-SWGCP: 33s vs 17s; 3 vs 2 timeouts.
  • BasicILS components: BasicILS consistently outperformed RandomSearch, with statistically significant differences in three of five scenarios.BasicILS also outperformed SimpleLS significantly in the three scenarios where it had time for multiple ILS iterations.
  • FocusedILS and evaluation budgets: BasicILS(1) was fast but generalized poorly, whereas larger evaluation budgets improved test performance; FocusedILS statistically significantly outperformed BasicILS(100) in three SAPS and CPLEX scenarios.In SAPS-SWGCP, BasicILS(1) selected a configuration worse than the default on the test set; BasicILS(100) performed better than FocusedILS in both SPEAR scenarios.
  • Adaptive capping: TP capping improved average performance in all five scenarios and enabled up to four times as many ILS iterations.For SAPS-SWGCP, BasicILS found the same solutions up to about an order of magnitude faster with capping.
  • Adaptive capping: Aggressive capping increased SAPS-SWGCP iterations from 12 to 219, producing a significant performance improvement.The two capping techniques were identical during BasicILS’s first ILS iteration, so no difference was observed for SPEAR-SWGCP and CPLEX-REGIONS100.
  • Adaptive capping: Adaptive capping enabled RandomSearch to evaluate between 3.4 and 33 times as many configurations and reduced the performance gap between BasicILS and FocusedILS.BasicILS caught up with FocusedILS on SAPS-SWGCP under adaptive capping, but remained inferior on CPLEX-REGIONS100.

7. Case Study: Configuring CPLEX for Real-World Benchmarks

This case study evaluates ParamILS for configuring CPLEX across five real-world benchmark scenarios, using disjoint training and test sets. Both BasicILS and FocusedILS generally improved on CPLEX’s defaults, while aggressive capping exposed a failure mode under changed cutoff conditions.

  • Study design: This was the first published study to automatically configure CPLEX, evaluating ParamILS across five benchmark scenarios.The benchmarks were collected from public libraries and other researchers.
  • Study design: Each scenario’s instances were split 50:50 into disjoint training and test sets for configuration and evaluation.The scenarios covered Regions200, MJA, CLS, MIK, and QP benchmark sets.
  • Results: Both BasicILS and FocusedILS found configurations better than CPLEX defaults in every considered scenario, sometimes by over an order of magnitude.This was notable because ILOG had invested substantial effort in selecting strong default CPLEX parameters.
  • Limitations: In CPLEX-MIK, 9 out of 10 FocusedILS runs achieved average runtimes below 2 seconds, but aggressive capping also produced a configuration solving no test instances.The failure resulted from every CPLEX run being unsuccessful during configuration.
  • Limitations: The FocusedILS configuration for one scenario generalized to unseen test data but not to the larger 3600 CPU-second cutoff used in testing.It was found using a 300 CPU-second configuration process and failed to carry over when the cutoff increased.

8. Review of Other ParamILS Applications

This section reviews diverse ParamILS applications, showing substantial gains in tuning established solvers and enabling automated construction of new algorithms. Applications span SAT, verification, protein folding, timetabling, and configurator self-optimization.

  • Early applications: Across early applications, ParamILS substantially improved defaults: GLS+ by >360×, SAPS by 8× and 130×, and SAT4J by 11×.These results covered SAPS-QWH, SAPS-SW, and SAT4J, with GLS+ finding better-quality solutions in 10 seconds than the default found in one hour.
  • SPEAR: SPEAR tuning improved competition performance from 82 to 99 solved instances and rank 17th to 5th, with speedups of 20× on SWV and 1.3× on BMC.A specific optimization yielded further speedups of over 500× for SWV and 4.5× for BMC, with no SWV instance taking longer than 20 seconds.
  • SATenstein: FocusedILS configured SATenstein variants that outperformed all eleven state-of-the-art SLS-based SAT solvers across all six problem-distribution categories.SATenstein combines components from WalkSAT-based, dynamic local search, and G2WSAT algorithms, demonstrating automated algorithm design beyond parameter tuning.
  • Self-configuration: ParamILS self-configuration produced only small, statistically insignificant improvements: average performance improved in four of five scenarios and degraded in one.In this setup, configuration scenarios served as instances and the configurator itself served as the target algorithm.
  • Additional applications: BasicILS and other ParamILS variants were also applied to protein-folding algorithm tuning and modular stochastic local-search design for post-enrollment course timetabling.These studies used automated configuration to explore parameterized algorithm designs in the 2D-HP and 3D-HP models and in a large modular timetabling design space.

9. Related Work

Related work spans direct-search, experimental-design, evolutionary, model-based, and racing approaches to automated algorithm configuration. It also includes per-instance adaptation and local-search methods related to ParamILS.

  • Direct-search approaches: Automated configuration research includes direct-search methods, beginning with early-1990s adaptive problem-solving systems such as Composer and MULTI-TAC.Composer used statistically guided hill climbing, while MULTI-TAC generated domain-specific programs and selected among them with beam search.
  • Direct-search approaches: Experimental-design and gradient-descent methods use fixed training sets to identify promising configurations, including Coy et al.’s averaging approach and CALIBRA’s iterative fractional designs.Coy et al. first optimized configurations per training instance and then averaged parameter values; CALIBRA evaluated factorial designs before narrowing the search.
  • Other configuration methods: Genetic algorithms and continuous direct search have also been applied, with Terashima-Marín et al. improving performance over modified Brelaz and mesh adaptive direct search reporting around 25% improvement.The mesh adaptive direct search method targets purely continuous spaces and was evaluated on CUTEr problems using runtime and function evaluations.
  • Other configuration methods: Alternative approaches include Gaussian-process-based sequential parameter optimization and racing methods such as F-Race, whose published experiments covered only around 1200 configurations.A later F-Race extension scales better by iterating over subsets but handles only algorithms with numerical parameters.
  • Related problems: Related work addresses selecting configurations or algorithms per instance and adapting parameters during execution, while ParamILS is closely related to one-exchange local search methods for SAT, CSP, and MPE.Existing theoretical frameworks for local search could in principle be used to analyze ParamILS.

10. Discussion, Conclusions and Future work

Enhanced ParamILS, using a new capping mechanism, produced strong performance improvements across SAT algorithms, CPLEX, and benchmark sets, often outperforming carefully chosen defaults on unseen instances. Applying automated configuration requires an externally parameterized algorithm, parameter domains, suitable cutoff times, and computational resources, while future work targets richer parameter handling and evaluation strategies.

  • Conclusions: Enhanced ParamILS with a new capping mechanism and achieved excellent results on two high-performance SAT algorithms, CPLEX, and diverse benchmark sets.The framework automatically configures parameters to optimize performance on benchmark instances.
  • Results: Up to two orders of magnitude improvement over carefully chosen defaults was observed for some configuration scenarios on previously unseen test instances.Improvements over CPLEX’s default parameter configuration were particularly noteworthy, although no uniformly better CPLEX configuration was claimed.
  • Requirements: Practitioners must provide an externally parameterized algorithm and allowable parameter domains, potentially including dependencies between parameters.Configurable parameters may need to be exposed from hard-coded source-code settings.
  • Requirements: A smaller cutoff time accelerates configuration-space exploration, but choosing it too small can produce configurations that perform poorly under longer timeouts.In the CPLEX-QP scenario, a 300-second timeout yielded a configuration that was good at that cutoff but poor for longer runs.
  • Requirements: Configuration also requires computational resources, ranging from roughly half an hour or five hours for some fast, homogeneous applications to more time for slower target algorithms.The required computational time depends on the target application.
  • Conclusions: The authors expect automated algorithm configuration methods such as ParamILS to become increasingly prominent in developing and applying high-performance algorithms.They characterize the research area as rich, fruitful, and containing many open questions.
  • Future work: Future work includes adapting integer and continuous parameter domains, handling continuous parameters without user discretization, selecting evaluation instances and instance-specific cutoffs, and integrating statistical testing, response surfaces, and active learning.The authors also see potential in combining their approach with related algorithm-configuration methods.
Loading 1401.3492v1…