Main Content

solve

Solve QUBO (Quadratic Unconstrained Binary Optimization) problem

Since R2023a

collapse all in page

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

Q=[0−12−104240]c=[−56−4]d=12.

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

See Also

| |

Topics