# tabuSearch

Tabu search algorithm for `QUBO` `solve`

Since R2023a

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

## Description

The tabu search algorithm solves a QUBO (Quadratic Unconstrained Binary Optimization) problem. Call a nondefault tabu search by creating a `tabuSearch` object, and then setting the object as the `Algorithm` in `solve`.

```ts = tabuSearch(MaxTime=60); % Set maximum time larger than default qprob = qubo(Q,c,d); % Create QUBO result = solve(qprob,Algorithm=ts); % Solve problem using ts object```

## Creation

### Syntax

``ts = tabuSearch``
``ts = tabuSearch(Name=Value)``

### Description

````ts = tabuSearch` creates a default `tabuSearch` algorithm object.```

example

````ts = tabuSearch(Name=Value)` sets Properties using one or more name-value arguments. For example, to specify more possible iterations than the default, set `ts = tabuSearch(MaxIterations=5e6)`.```

## Properties

expand all

Level of display, specified as one of the following:

• `"off"` (default) — No displayed information.

• `"final"` — Display information after the last call to the simple tabu search.

• `"iter"` — Display information at every call to the simple tabu search.

For details of the simple tabu search algorithm, see Tabu Search Algorithm.

Example: `"iter"`

Maximum number of simple tabu search iterations, specified as a positive integer.

Example: `1e7`

Maximum number of iterations in which best function value does not change, specified as a positive integer or `[]`.

When the property has the default value of `[]`, the value used by the algorithm depends on the number of problem variables `N`. When `N <= 1000`, ```MaxStallIterations = 0.01*MaxIterations```. When `N > 1000`, `MaxStallIterations = MaxIterations`.

Example: `500`

Maximum time in seconds for which best function value does not update, specified as a positive scalar or `[]`.

When this property has the default value of `[]`, the value used by the algorithm depends on the number of problem variables `N`.

`N`Default Time (Seconds)
`N <= 250``1/2`
`250 < N <= 500``2`
`500 < N <= 1000``3`
`1000 < N <= 2500``3 + 7*(N - 1000)/1500`
`N > 2500``10`

Example: `500`

Data Types: `double`

Maximum time in seconds the tabu search algorithm runs, specified as a positive scalar.

Example: `10`

## Examples

collapse all

Create a QUBO problem.

```Q = [0 -1 2;... -1 0 4;... 2 4 0]; c = [-5 6 -4]; d = 12; qprob = qubo(Q,c,d)```
```qprob = qubo with properties: QuadraticTerm: [3×3 double] LinearTerm: [-5 6 -4] ConstantTerm: 12 NumVariables: 3```

Create a tabu search object that displays iterations and limits the stall time to 0.01s.

`ts = tabuSearch(Display="iter",MaxStallTime=0.01);`

Solve the QUBO problem using the tabu search object.

`result = solve(qprob,Algorithm=ts)`
```Tabu call Best fval Stall time Tabu iterations 0 18 0 0 1 7 0.0002593 309 2 7 0.00109 301 3 7 0.001731 301 4 7 0.002031 301 5 7 0.00232 301 6 7 0.002605 301 7 7 0.002885 301 8 7 0.003163 301 9 7 0.003446 301 10 7 0.003772 301 11 7 0.004054 301 12 7 0.00433 301 13 7 0.004611 301 14 7 0.004888 301 15 7 0.005163 301 16 7 0.005438 301 17 7 0.005719 301 18 7 0.005992 301 19 7 0.006266 301 20 7 0.006544 301 21 7 0.00682 301 22 7 0.007104 301 23 7 0.007385 301 24 7 0.007669 301 25 7 0.007949 301 26 7 0.008411 301 27 7 0.008699 301 28 7 0.008978 301 29 7 0.009257 301 Tabu call Best fval Stall time Tabu iterations 30 7 0.009549 301 31 7 0.009894 301 32 7 0.01013 301 TabuSearch stopped because MaxStallTime is exceeded. result = quboResult with properties: BestX: [3×1 double] BestFunctionValue: 7 AlgorithmResult: [1×1 tabuSearchResult]```

Tabu search is a stochastic algorithm, so your results might vary.

## Algorithms

The tabu search algorithm is based on Palubeckis [1]. Starting from a random binary vector, the software repeatedly attempts to find a binary vector with a lower objective function value by switching some existing values from 1 to 0 or from 0 to 1. The software tries to avoid cycling, or the repeated evaluation of the same point, by using a tabu list. For details, see Tabu Search Algorithm.

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

## Version History

Introduced in R2023a