solve

Solve QUBO (Quadratic Unconstrained Binary Optimization) problem

Since R2023a

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

Syntax

``result = solve(qprob)``
``result = solve(qprob,Algorithm=ts)``

Description

example

````result = solve(qprob)` searches for a solution `result` to `qprob`, a `QUBO` problem, using the default `tabuSearch` algorithm.```

example

````result = solve(qprob,Algorithm=ts)` searches using the `ts` tabu search algorithm. Use this syntax when you want to set the properties of the tabu search object `ts`.```

Examples

collapse all

Create a QUBO problem for the quadratic matrix `Q`, linear vector `c`, and constant term `d`, where

`$\begin{array}{c}Q=\left[\begin{array}{ccc}0& -1& 2\\ -1& 0& 4\\ 2& 4& 0\end{array}\right]\\ c=\left[\begin{array}{ccc}-5& 6& -4\end{array}\right]\\ d=12.\end{array}$`

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

Solve the problem using the tabu search algorithm.

`result = solve(qprob)`
```result = quboResult with properties: BestX: [3×1 double] BestFunctionValue: 7 AlgorithmResult: [1×1 tabuSearchResult]```

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.

Input Arguments

collapse all

QUBO problem, specified as a `qubo` object. Create `qprob` using the `qubo` function.

Tabu search algorithm, specified as a `tabuSearch` object. Set algorithm properties using the `tabuSearch` function.

Example: To run the algorithm for no more than 60 seconds, set ```ts = tabuSearch(MaxTime=60)``` and then call `solve(qprob,Algorithm=ts)`.

Output Arguments

collapse all

Solution of the QUBO problem, returned as a `quboResult` object. `result` contains the following properties:

• `BestX` — Solution point corresponding to the minimum objective function value.

• `BestFunctionValue` — Objective function value corresponding to `BestX`. Generally, ```BestFunctionValue = evaluateObjective(qprob,BestX)```.

• `AlgorithmResult` — Details of the results, returned as a `tabuSearchResult` object.

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