Online Search Algorithm Configuration
Authors: Tadhg Fitzgerald, Barry O'Sullivan, Yuri Malitsky, Kevin Tierney
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments Combinatorial auctions involve users placing bids on a collection of goods, with the objective of finding the set of bids which can be satisfied and produce the maximum profit (Leyton-Brown, Pearson, and Shoham 2000). For our current experiments we use 2000 combinatorial auction instances sorted by increasing number of goods. This dataset provides a good representation of a growing company whose problem type is changing over time. We generated these instances using the Combinatorial Auction Test Suite (CATS).1 Any trivial instances (solvable in under 30 seconds using CPLEX defaults) and any very difficult instances (taking more than 900 seconds) were removed. This is done so that we do not spend time tuning on parameters that can easily be solved using a presolver or instances that are too difficult to solve. SMAC (Hutter, Hoos, and Leyton-Brown 2011) is the current state-of-the-art offline parameter tuning approach. We simulate the case where initially no training instances exist and the default parameters must be used to solve the first 200 instances. SMAC then uses the first 200 instances as its training set and is tuned over two days, after which each new instance is solved with the tuned parameters. We follow the typical practice of tuning multiple versions with SMAC and selecting the best based on training performance. In our case we present both the result of the best found SMAC parameters (SMAC-VB), and the average performance of the three parameterizations we trained (SMAC-Avg). In our results we compare two versions of our system. The first has no information about the solver beforehand, and thus all six initial parameterizations are generated at random. We call this case Online-Cold. We also include Online Warm, where one of the initial parameterizations contains the CPLEX default parameters and the other five are randomly generated. We run each version of our system three times, and present the average of all three runs in the plot. Figure 1 shows the cumulative average solving time for CPLEX Default, SMAC virtual best, SMAC average, Online-Cold started and Online-Warm started. Notice that as the difficulty increases the average time for the default parameter set increases rapidly while our system increases at a much slower pace because we are able to adapt to the changes in the dataset. The performance of our approach almost matches that of SMAC despite the fact that our approach required no pre-training while SMAC spent 48 hours training offline. |
| Researcher Affiliation | Academia | Tadhg Fitzgerald, Yuri Malitsky, and Barry O Sullivan Insight Centre for Data Analytics University College Cork, Ireland tadhg.fitzgerald@insight-centre.org Kevin Tierney DS&OR University of Paderborn Paderborn, Germany |
| Pseudocode | No | No pseudocode or clearly labeled algorithm blocks were found. |
| Open Source Code | No | No concrete access to source code for the methodology described in this paper was provided. There is no explicit statement of code release or a link to a code repository for the authors' work. |
| Open Datasets | Yes | We generated these instances using the Combinatorial Auction Test Suite (CATS).1 1http://www.cs.ubc.ca/ kevinlb/CATS/ |
| Dataset Splits | No | No specific dataset split information (percentages, sample counts, citations to predefined splits) for training, validation, and testing was provided for their online method. For SMAC, it mentions: SMAC then uses the first 200 instances as its training set and is tuned over two days, after which each new instance is solved with the tuned parameters. |
| Hardware Specification | No | The paper mentions 'modern multi-core CPUs' but does not provide specific hardware details such as exact GPU/CPU models, processor types, or memory amounts used for running its experiments. |
| Software Dependencies | No | The paper mentions 'CPLEX defaults' and 'CPLEX' but does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | Currently we decide when a parameter is being dominated using a ratio method, e.g. given a ratio of 2, if parameterization A has 10 wins and parameterization B has 20, then parameterization A is considered the weaker. The first has no information about the solver beforehand, and thus all six initial parameterizations are generated at random. We call this case Online-Cold. We also include Online Warm, where one of the initial parameterizations contains the CPLEX default parameters and the other five are randomly generated. |