= Sequential algorithm portfolio
A <sequential algorithm portfolio> allocates one processor's time among candidate <algorithms> or runs. Its <algorithm portfolio schedule> determines which candidate runs, when to switch and whether an interrupted run is resumed or abandoned. The original portfolio study compared single-processor interleaving and restart policies with parallel execution.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Sections 4–5, interleaved and restart portfolios]{ref}
Consider original runtimes $A=(2,12)$ seconds and $B=(8,3)$ seconds on two equally likely input types. Either fixed choice has mean $7$ or $5.5$ seconds. Run $A$ for at most four seconds, then start $B$ if $A$ has not finished. The two completion times are $2$ and $4+3=7$ seconds, so the scheduled mean is $4.5$ seconds. The schedule succeeds because the candidates have complementary performance.
<Algorithm portfolio switching overhead> can erase that gain. If the switch costs $3$ seconds whenever it occurs, the second completion time becomes $10$ seconds and the mean becomes $6$ seconds, worse than always running $B$. The cost must be charged to the actual switching events, rather than added equally to every instance.
A timeout also does not say that the interrupted candidate would never solve the input. Resuming preserves previous search work only if the implementation supports it; restarting begins a different run. Record budgets, state retention, random seeds and the final stopping rule when reporting a sequential portfolio's performance. A good schedule on measured inputs still needs evaluation on unused inputs.
Back to article page
