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.

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

Display — Level of display

"off" (default) | "final" | "iter"

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"

MaxIterations — Maximum number of simple tabu search iterations

1e6 (default) | positive integer

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

Example: 1e7

MaxStallIterations — Maximum number of iterations in which best function value does not change

[] (default) | positive integer

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

MaxStallTime — Maximum time in seconds for which best function value does not update

[] (default) | positive scalar

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

MaxTime — Maximum time in seconds the algorithm runs

20 (default) | positive scalar

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

Example: 10

Examples

Modify Tabu Search

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