Supplementary material to the article:
Capping Methods for the Automatic Configuration of Optimization Algorithms
Marcelo de Souza, Marcus Ritt and Manuel López-Ibáñez
Computers & Operations Research, 2021
[link to the article]
Automatic configuration techniques are widely and successfully used to find good parameter settings for parameterized algorithms. Configuration is costly, because it is necessary to evaluate many configurations on different instances. For decision problems, when the objective is to minimize the running time of the algorithm, many configurators implement capping methods to discard poor configurations early. Such methods are not directly applicable to optimization problems, when the objective is to optimize the cost of the best solution found, given a predefined running time limit. We propose new capping methods for the automatic configuration of optimization algorithms. They use the previous executions to determine a performance envelope, which is used to evaluate new executions and cap those that do not satisfy the envelope conditions. We integrate the capping methods into the irace configurator and evaluate them on different optimization scenarios. Our results show that the proposed methods can save from about 5% to 80% of the configuration effort, while finding configurations of the same quality. Based on the computational analysis, we identify two conservative methods, that save an average of about 20% of the configuration effort and never found significantly worse configurations than those obtained without capping on all tested problems. We also provide evidence that capping can help to better use the available budget in scenarios with a configuration time limit.
Keywords: automatic algorithm configuration; capping methods; optimization algorithms; parameter tuning
All capping methods are implemented in capopt. It provides a Python target runner script that integrates with irace. Please, check all details of how to use it and the latest version of the source code in the capopt official repository. You can also download the source code of the exact version of capopt used in our experiments here.
We tested the capping methods in the following scenarios:
- ACOTSP: ant colony optimization algorithms for the symmetric traveling salesperson problem [1].
- HEACOL: hybrid evolutionary algorithm for graph coloring [2].
- TSBPP: tabu search for the bin packing problem [3, 4].
- HHBQP: hybrid heuristic for unconstrained binary quadratic programming [5].
- LKH: a heuristic algorithm for solving the symmetric traveling salesperson problem [6, 7, 8].
- SCIP: an exact solver for mixed integer programs for solving the combinatorial auction winner determination problem [9, 10].
Each configuration scenario contains:
- source code of the target algorithm (or executable, in the case of SCIP; LKH and SCIP has also a wrapper script for communication);
- parameters file;
- training and test instances;
- best known values file;
- parameters of capopt file;
- irace scenario file;
- LKH has also a forbidden configuration file.
Below you find all files for each configuration scenario. We also provide the scenario.txt and parameters-capopt.txt files for the experiments using a total configuration time budget (the rest of files are the same as configuring with a total executions budget):
| Scenario | Budget in executions | Budget in time |
|---|---|---|
| ACOTSP | scenario-acotsp | scenario.txt | parameters-capopt.txt |
| HEACOL | scenario-heacol | scenario.txt | parameters-capopt.txt |
| TSBPP | scenario-tsbpp | scenario.txt | parameters-capopt.txt |
| HHBQP | scenario-hhbqp | scenario.txt | parameters-capopt.txt |
| LKH | scenario-lkh | scenario.txt | parameters-capopt.txt |
| SCIP | scenario-scip | scenario.txt | parameters-capopt.txt |
Important: for each scenario, file parameters-capopt.txt defines the use of the default capping method PEMW.1. In order to evaluate other (or disable) capping methods, this file must be changed according to the instructions given here.
We modified the source code of ACOTSP, HACOL and TSBPP, to be able to monitor the progress of the search during its execution. Below you can find the link and a copy of the original implementation of all target algorithms, as well as the modified version (if applicable) used in our experiments and the patch file with the changes made.
| Scenario | Link (original) | Copy (original) | Copy (modified) | Patch file |
|---|---|---|---|---|
| ACOTSP | link | src-acotsp-original | src-acotsp-modified | src-acotsp.patch |
| HEACOL | link | src-heacol-original | src-heacol-modified | src-heacol.patch |
| TSBPP | link | src-tsbpp-original | src-tsbpp-modified | src-tsbpp.patch |
| HHBQP | link | src-hhbqp-original | – | – |
| LKH | link | src-lkh-original | – | – |
| SCIP | link | scip-original | – | – |
Here you find the raw data of our experiments.
- Evaluating all capping methods using a total executions budget:
- Analyzing the recommended methods in detail (9th replication on ACOTSP):
- Evaluating all capping methods using a total configuration time budget:
[1] Dorigo, M., Stützle, T., 2004. Ant Colony Optimization. MIT Press, Cambridge, MA.
[2] Galinier, P., Hao, J.K., 1999. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3, 379 – 397.
[3] Lodi, A., Martello, S., Vigo, D., 1999. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing 11, 345 – 357.
[4] Lodi, A., Martello, S., Vigo, D., 2004a. TSpack: a unified tabu search code for multi-dimensional bin packing problems. Annals of Operations Research 131, 203 – 213.
[5] De Souza, M., Ritt, M., 2018. Automatic grammar-based design of heuristic algorithms for unconstrained binary quadratic programming, in: Evolutionary Computation in Combinatorial Optimization, Springer International Publishing. pp. 67 – 84.
[6] Helsgaun, K., 2000. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126, 106 – 130.
[7] Helsgaun, K., 2009. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation 1, 119 – 163.
[8] Helsgaun, K., 2018a. Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic, pp. 95 – 107.
[9] Achterberg, T., 2009. SCIP: Solving constraint integer programs. Mathematical Programming Computation 1, 1 – 41.
[10] De Vries, S., Vohra, R.V., 2003. Combinatorial auctions: A survey. INFORMS Journal on Computing 15, 284 – 309.