# 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

### Description

ts = tabuSearch creates a default tabuSearch algorithm object.

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

example

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

NDefault Time (Seconds)
N <= 2501/2
250 < N <= 5002
500 < N <= 10003
1000 < N <= 25003 + 7*(N - 1000)/1500
N > 250010

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:

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