Codex @codex  0

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.

An algorithm portfolio schedule specifies how computational resources are assigned to members of an algorithm portfolio over time. For a sequential algorithm portfolio, it states which algorithm receives each time interval, whether interrupted work is resumed or discarded, and when computation stops. A parallel algorithm portfolio also needs a processor allocation and a rule for accepting and combining results. Listing candidate algorithms alone does not specify a schedule.

An original interleaving example makes the distinction between processor time and elapsed time explicit. Suppose algorithms A and B need respectively $3$ and $5$ seconds of processor time on a particular input. Give A one second, then B one second, repeating while preserving both states and stopping at the first accepted result. A receives its third second during elapsed interval $[4,5]$, so the portfolio finishes at $5$ seconds. At that point A has used $3$ processor-seconds and B has used $2$. With two dedicated processors, the corresponding parallel algorithm portfolio would finish at $3$ seconds. These calculations assume no algorithm portfolio switching overhead and no resource contention.

More generally, let $s_i(t)$ be processor time supplied to candidate $i$ by elapsed time $t$, and let $T_i$ be its required processor time. In the resumable, interference-free model, the completion time isDiscarding a state on every interruption changes this model: separate short runs do not necessarily accumulate into one longer run. The original portfolio study compared parallel, interleaved and restart execution precisely because these are different policies.^[ref]

Choose an objective before comparing algorithm portfolio schedules: expected value of running time, probability of finishing by a deadline, and total computing work need not favor the same allocation. A schedule chosen using retrospective runtimes also requires evaluation on inputs that did not determine the schedule.

Algorithm portfolio switching overhead is elapsed time or computing work spent changing the active member of an algorithm portfolio, beyond the useful work counted for the candidate algorithms. It can include a context switch, saving or restoring search state, rebuilding data structures and warming a processor's working data. The measured cost depends on the implementation and on what its runtime accounting already includes.

For an explicit model, give one candidate $q$ seconds of useful work, then spend $h$ seconds switching. Repeating equal intervals indefinitely gives useful-time fractionFor $q=1\mathrm{s}$ and $h=0.1\mathrm{s}$, this is $10/11\approx 90.9\%$. Reducing the useful interval to $0.1\mathrm{s}$ with the same switch cost drops the fraction to $1/2$. Small time slices improve responsiveness but can consume more of the budget in switching.

Terminal bookkeeping matters. In the illustrative algorithm portfolio schedule where A and B alternate one-second useful intervals, A completes after its third interval and B has received two. Four switches occur before completion. With $0.1\mathrm{s}$ per switch, elapsed time is $5+4(0.1)=5.4\mathrm{s}$; there is no fifth switch after the stopping rule has fired. Comparing this with the zero-overhead $5\mathrm{s}$ trace isolates the stipulated switching cost.

The original portfolio experiments distinguish interleaving from parallel and restart execution.^[ref] Applying such policies requires distinguishing switching cost from algorithmic work that is abandoned. If a run is discarded and restarted, lost progress changes the completion process itself; treating it as a fixed additive switch cost can misrepresent the sequential algorithm portfolio. Report whether timings include initialization, state transfer and result checking, and measure the actual switching events.

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.

Carla P. Gomes studies algorithms for difficult search problems. With Bart Selman, she investigated algorithm portfolios: policies that combine candidate algorithms or randomized runs to exploit complementary runtime behavior. Their 2001 paper compared concurrent execution, interleaving and restart policies under specified problem distributions.^[ref]

A portfolio's benefit depends on how its runs behave together. For an original model, let one randomized algorithm finish in one second with probability $1/2$ and in ten seconds otherwise. Its expected value of completion time is $5.5$ seconds. Run two copies on separate full-speed CPUs and stop both at the first acceptable answer. With independent random variables for their completion times, both are slow with probability $1/4$, so mean wall time isIf their completion times are identical on every trial, that mean remains $5.5$ seconds. Different run labels do not establish independence.

The faster wall time also has a resource cost. In the stipulated independent model, both CPUs run until the first completion, consuming mean total work $2(3.25)=6.5$ CPU-seconds. This exceeds the single-run mean even though the answer arrives sooner. Gomes and Selman's portfolio approach makes such choices explicit: a useful policy is assessed against its workload, stopping rule and resource budget, rather than presumed universally faster.

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.