Tabu Search Algorithm

Note

Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.

To solve a combinatorial optimization problem formulated as a QUBO problem, call the solve function on the QUBO problem. The solve function internally uses the tabu search algorithm, as described in Palubeckis [1]. For background information on QUBO problems, see What Is a QUBO Problem?

Change of Variables

For a binary vector x, a QUBO objective function has the form

$f (x) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} Q_{i, j} x_{i} x_{j} + \sum_{i = 1}^{N} c_{i} x_{i} + d .$

The algorithm begins by choosing a random binary vector x, and then changing the problem to a binary vector y that has all zero components. The coefficients of the problem must change so that the objective function for y is equal to the objective function for the corresponding x. The quadratic coefficients Q_i,j for x become K_i,j for y, where

$K_{i, j} = Q_{i, j} (1 - 2 {(x_{i} - x_{j})}^{2}) .$

The linear coefficients c_i for x become d_i for y, where

$d_{i} = (1 - 2 x_{i}) (c_{i} + \sum_{j : x_{j} = 1} r (i, j)),$

and

$r (i, j) = Q_{i, j} + Q_{j, i} .$

With these definitions, the value of the constant term of the objective function in the y formulation becomes f(x). In other words,

$y^{T} K y + d^{T} y + f (x)$

is the objective function in terms of y. Therefore, when y = 0, the value of the objective function is f(x).

This reformulation makes it easy to determine when a one-variable change in y leads to a lower objective function value. If any component d(i) is negative, then changing y(i) to 1 results in a lower value of the objective function, because all quadratic terms are zero. This change assumes, without loss of generality, that the diagonal entries in K are zero, because nonzero entries can be absorbed into d.

Palubeckis [1] gives an efficient algorithm for updating the coefficients of the objective function after a one-variable change in y. This update makes a local search for a minimum an efficient procedure.

Algorithm Steps

The tabu search algorithm has three phases: Initialize, Simple Tabu Search, and Get New Start Point. The algorithm starts with Initialize, then alternates between Simple Tabu Search and Get New Start Point until it reaches a stopping condition. The Simple Tabu Search phase has a tabu list, which is a list of variables that the algorithm cannot change until it is past the tabu tenure value for each variable. The tabu tenure value is the smaller of 20 and N/4, where N is the length of x.

Given a QUBO problem, the algorithm completes each phase as follows:

Initialize — Create a random binary vector x0. Map the x0 vector to an all-zero vector using the procedure explained in Change of Variables. Set x*, the best point found, to x0, and set the associated best function value to f(x*).
Simple Tabu Search — Starting from index 1, search for the first index K in the vector so that setting x(K) = 1 causes the objective function value f(x) < f(x*), ignoring any K selected within the past tabu tenure searches.
1. If the search is successful, change x(K) from 0 to 1, and map x(K) to the zero vector again using the procedure explained in Change of Variables. Each successful step counts as one iteration in the iterative display and output structure. Then repeatedly perform a strictly greedy search for a minimum, without referring to tabu, by taking the first index with a negative coefficient K, changing x(K) from 0 to 1, and then remapping x(K) to 0 using the procedure for changing variables. Each step counts as one iteration. Restart the search from index K + 1. Repeat until a full loop from x(1) to x(N) of the search is unsuccessful, meaning the current point is a local minimum of the objective function. The best point x* and the best function value f(x*) are different from before this phase, and the current point x = x*.
2. If the search is unsuccessful, choose K as the index not in the tabu list (list of variables with positive tabu values) that has the lowest linear coefficient. Change x(K) from 0 to 1, and map x(K) to the zero vector again using the procedure for changing variables. This procedure leads to a new x, but not a new x*. Each step of this type can count for up to N iterations, because the process of examining each coefficient value counts as an iteration.
  Update the tabu list by setting variable K to have a tabu value of 20, and lowering the tabu value of all other variables with positive tabu values by 1.
Repeat the Simple Tabu Search until reaching a stopping condition for this phase. Generally, the stopping condition occurs when the iteration count in this phase exceeds 1e4*N.
Get New Start Point — Initialize the set I to all N indices. Choose a random integer r uniformly in the interval [10,0.1*N]. Perform the following steps r times.
1. Find the five indices with the minimal linear coefficients among those in I. Randomly choose one of these indices, J.
2. Remove J from I.
3. Change x(J) to 1. Update the problem coefficients using the procedure explained in Change of Variables.
Take this new start point, clear the tabu list, and return to phase 2.

References

[1] Palubeckis, G. Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem. Informatica (2006), 17(2), pp. 279–296. Available at https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3c323a1d41cd0e2ca1ddb27192e475ea73959e52.