 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.^[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.