## 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)={\displaystyle \sum _{i=1}^{N}{\displaystyle \sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}}+{\displaystyle \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*for

_{i,j}*y*, where

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

The linear coefficients *c _{i}* for

*x*become

*d*for

_{i}*y*, where

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

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}Ky+{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.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*`

.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.Find the five indices with the minimal linear coefficients among those in

`I`

. Randomly choose one of these indices,`J`

.Remove

`J`

from`I`

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

## See Also

`solve`

| `tabuSearch`

| `quboResult`

| `tabuSearchResult`