How Tabu Search works
Tabu Search is an iterative improvement algorithm. At each step it evaluates all moves in the current solution's neighborhood, selects the best non-tabu move (even if it worsens the objective), and adds the reverse move to the tabu list for tabu_tenure iterations. This prevents cycling back to recently visited solutions and forces exploration of new regions.
The aspiration criterion overrides the tabu status: if a tabu move would produce a new global best solution, it's allowed regardless of its tabu status.
Usage
import nerox
client = nerox.Client()
job = client.optimize.scheduling(
jobs=jobs,
problem_type="job_shop",
solver="tabu",
tabu_tenure=20, # moves forbidden for 20 iterations
max_iter=10000,
aspiration=True, # allow tabu move if it beats global best
)
# Also works for general QUBO
job2 = client.optimize.qubo(
Q=Q_matrix,
solver="tabu",
tabu_tenure=15,
max_iter=50000,
)
result = job.wait()Neighborhood structure
For QUBO problems, the neighborhood is all single bit-flip moves (n moves for an n-variable problem). For structured problems (TSP, scheduling), NEROX uses problem-specific neighborhoods: 2-opt moves for TSP, operation-swap moves for job shop scheduling. Problem-specific neighborhoods typically converge 10–50× faster than generic QUBO bit flips.
When Tabu Search beats GPU Annealing
On scheduling problems with clear local move semantics (swap two operations on the same machine), Tabu Search consistently finds better solutions than GPU Annealing given the same wall-clock time — because domain-guided moves are far more informative than random bit flips. For scheduling benchmarks (FT10, LA-series), Tabu Search on NEROX matches or exceeds published STS results.