Katkat
Back

Design Restart Strategy for Oracle Solver

OpenAISoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenMachine Learning

Last updated

This question tests the ability to optimize restart intervals for a randomized algorithm with heavy-tailed runtime distributions, balancing the trade-off between progress and computation waste.

The Problem: Optimizing Solver Restarts

You are building a randomized heuristic solver (a Las Vegas algorithm) that attempts to find an optimal solution to a combinatorial problem. The time $T$ it takes for this solver to find a solution follows a heavy-tailed probability distribution, where $P(T > t) = F(t)$. Because the solver can occasionally get stuck in local optima or bad search branches, you have the option to "restart" it: if the solver has not found a solution within a fixed time $L$, you kill the current process and start a fresh execution.

Your goal is to derive the optimal restart interval $L^*$ that minimizes the expected time to find a solution.

Task

  1. Write a function calculate_expected_time(F, L) that computes the expected time to find a solution given a survival function $F(t)$ and a restart limit $L$.
  2. Assume $F(t) = 1/t$ for $t >= 1$. Derive the expression for the expected time $E(L)$ as a function of $L$.
  3. Discuss how you would numerically find the optimal $L^*$ given that $F(t)$ is provided as an empirical distribution from historical logs.

Example

If the probability of success in any given second is constant $p$, then $F(t) = (1-p)^t$. The expected time is minimized by choosing $L$ based on the geometric distribution properties. In the case of heavy-tailed distributions (like $1/t$), the expected value of the original distribution might be infinite, but a restart strategy can render the effective expected time finite.

Hints

Hint 1

Consider the law of total expectation: $E[T_{total}] = E[T | T = L)$.

Hint 2

Rearrange the equation to isolate $E[T_{total}]$ and solve for the value of $L$ that minimizes the resulting expression.

Hint 3

For empirical distributions, consider using a grid search or golden-section search to find the minimum of the expected time function.

Follow-up questions

  • How does the optimal restart strategy change if there is a fixed 'setup overhead' cost $C$ incurred every time the solver restarts?
  • What happens to your strategy if the solver is 'stateful'—meaning it learns from previous runs (e.g., via a shared cache or model weights) versus being purely randomized?
  • If you have access to multiple solvers with different runtime distributions, how would you design a 'portfolio' scheduling strategy to invoke them?