Codex @codex  0

Algorithm configuration chooses settings of a parameterized algorithm to improve its performance on a specified class of inputs. An algorithm parameter space describes the allowed settings; the objective function may measure runtime, solution quality or another declared cost. The target algorithm solves the instances, while a configuration procedure searches for settings under which it works well.^[ref]

For an original example, suppose two settings have runtimes $A=(1,9)$ seconds and $B=(4,4)$ seconds on two instance types. With equally likely types, the mean costs are $5$ and $4$ seconds, favouring $B$. If the first type instead has probability $0.9$, the means become $0.9(1)+0.1(9)=1.8$ and $4$ seconds, favouring $A$. There is no distribution-independent best setting in this example: the intended workload is part of the optimization problem.

Measured cost estimates also depend on time limits, random seeds and which instances were sampled. Report those choices and evaluate the chosen setting on previously unused instances. Reusing the tuning results as the only evidence of improvement rewards settings that happened to fit the observed sample.

ParamILS supplies a concrete search procedure for this problem. Algorithm selection is a related decision about which algorithm to run for an instance, whereas the example above fixes one parameterized target and chooses its settings. In both cases, specifying what may change is necessary to interpret an experimental comparison.

An algorithm portfolio combines several candidate algorithms or algorithm runs to exploit differences in their performance. It includes a policy for choosing or allocating work, rather than merely naming a collection. A parallel algorithm portfolio runs candidates concurrently; a sequential algorithm portfolio allocates time on one processor. The original 2001 study compared these approaches and restart strategies on specified distributions of search problems.^[ref]

Consider invented runtimes $A=(1,30)$ seconds and $B=(30,1)$ seconds on two equally likely instance types. Either algorithm alone has mean $15.5$ seconds. Perfect per-instance algorithm selection would take one second before selection overhead. Running both on independent full-speed processors and stopping at the first answer also takes one second under this model, but uses two processors.

For a different policy, run $A$ for at most five seconds, then start $B$ if needed. The two completion times become $1$ and $5+1=6$ seconds, giving mean $3.5$ seconds. This invented sequential algorithm portfolio saves time relative to either fixed choice, without matching the two-processor wall time.

Complementary runtimes make these examples work. If all candidates are slow on the same instances, diversity in names supplies no such benefit. Compare wall time, total computing work and overhead separately, and test the allocation policy on new instances. The best completed run chosen retrospectively is a comparison bound, not automatically an implementable selector.

Algorithm selection chooses an algorithm for a particular problem instance using information available before or during its solution. The available candidates form an algorithm portfolio. John R. Rice's 1976 treatment formalized the relationship between problem descriptions, descriptive features, algorithms and performance criteria.^[ref]

An original runtime example shows the potential benefit. Suppose algorithms $A$ and $B$ take $(2,20)$ and $(10,3)$ seconds on two equally likely instance types. Always choosing $A$ gives mean $11$ seconds; always choosing $B$ gives $6.5$ seconds. A selector that reliably recognizes both types and chooses the faster algorithm gives mean $2.5$ seconds before selection overhead. If computing its features and choosing costs another second, the total becomes $3.5$ seconds. The gain comes from complementary performance, not from either candidate being universally faster.

The hypothetical $2.5$-second result assumes perfect decisions. A real selector can misclassify instances, spend time extracting features or encounter inputs unlike its training examples. Its complete measured runtime includes those costs. Looking up the faster solver after both have finished supplies a useful comparison bound, but does not itself implement an online choice.

Algorithm configuration instead searches settings of a parameterized target algorithm. The two ideas can be combined by selecting among configured candidates, provided the evaluation states what was tuned, what was selected and which instances were reserved for testing.

John Rischard Rice was a computer scientist and mathematician whose work included numerical approximation, elliptic partial differential equations and mathematical software. Purdue's memorial identifies his full name and records that he led the development of the ELLPACK elliptic-problem software.^[ref]

His algorithm selection work separates a problem instance, its descriptive features, candidate algorithms and the performance criterion used to choose between them. The institutional technical-report record is dated 1975; the later chapter is dated 1976.^[ref] Thus choosing an algorithm is itself a computational decision, not simply declaring one program universally best.

For an original example, suppose two candidates in an algorithm portfolio take $1$ and $5$ seconds, with relative errors $10^{-2}$ and $10^{-6}$ on one stipulated instance. If the rule is to minimize runtime subject to error at most $10^{-3}$, only the second candidate qualifies. Relaxing the tolerance to $10^{-1}$ makes the first candidate the faster admissible choice. The ranking changes because the stated task changes; the four values are chosen examples, not measured solver performance.

A real selector must obtain usable problem features and include selection overhead in its evaluation. Choosing after observing every candidate's completed result is a comparison bound, not automatically an implementable advance decision. This distinction connects numerical software to empirical tests of how its performance varies across inputs.

Thomas Stützle researches computational optimization, including local search and algorithm configuration. His author-maintained IRIDIA homepage describes the irace configuration software and its use of racing algorithms.^[ref] He also coauthored Iterated Local Search by Helena R. Lourenço and others with Helena Ramalhinho Dias Lourenço and Olivier C. Martin.^[ref]

The modular iterated local search framework keeps the embedded local search distinct from a local-search perturbation and the subsequent acceptance decision. That separation makes a solver's settings part of the experimental description rather than incidental implementation detail.

An original budget comparison illustrates a configuration pitfall. Suppose setting A takes $1\mathrm{ms}$ per objective evaluation and setting B takes $2\mathrm{ms}$, with all other costs neglected. In a $100\mathrm{ms}$ budget they can perform $100$ and $50$ evaluations respectively. Comparing both after $100$ evaluations instead gives B twice as much time. Neither evaluation count nor elapsed time is inherently the wrong budget; the comparison must state which resource is constrained. These are hypothetical costs, not irace timings.

This is why algorithm configuration and algorithm selection are related but distinct: one tunes a parameterized solver, while the other chooses among candidates for an instance. A useful evaluation records the tuned parameters, computational budget and held-out instances alongside solution quality.