= Algorithm portfolio switching overhead
\b[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 fraction
$$
\eta=\frac{q}{q+h}.
$$
For $q=1\,\mathrm{s}$ and $h=0.1\,\mathrm{s}$, this is $10/11\approx90.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.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Sections 4–5, interleaved portfolios and restart comparisons.]{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.
Back to article page
