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\left(x\right)=\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 Qi,j for x become Ki,j for y, where

`${K}_{i,j}={Q}_{i,j}\left(1-2{\left({x}_{i}-{x}_{j}\right)}^{2}\right).$`

The linear coefficients ci for x become di for y, where

`${d}_{i}=\left(1-2{x}_{i}\right)\left({c}_{i}+\sum _{j:{x}_{j}=1}r\left(i,j\right)\right),$`

and

`$r\left(i,j\right)={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}Ky+{d}^{T}y+f\left(x\right)$`

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:

1. 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*)`.

2. 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`.

3. 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.