Workflow for QUBO Problems
Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.
A Quadratic Unconstrained Binary Optimization (QUBO) problem is a quadratic optimization problem in binary variables. For background information, see What Is a QUBO Problem?
To solve a QUBO problem, you first need to convert your problem to QUBO, and then solve it using the tabu search algorithm.
Convert Problem to QUBO
solves problems represented in QUBO form. For x(i), a
binary variable with N components, a QUBO objective function has the
To express your problem as a QUBO, create a real
Q, an optional
c, and an optional scalar
d. Then create the QUBO problem as follows:
qprob = qubo(Q,c,d); % Or qprob = qubo(Q) or qprob = qubo(Q,c)
For more information, including how to convert between QUBO form and Ising form, see What Is a QUBO Problem?
Some problems have constraints that you express as a penalty term in the QUBO objective function. See Constraints in QUBO Problems.
Solve Problem Using Tabu Search
solve on the QUBO to find a solution using the tabu search
solve syntax is:
result = solve(qprob)
Tabu search is a stochastic algorithm, so each time you run the algorithm, you might get
a different result. If you add constraints to a problem by using a penalty term, and the
first solution you get is infeasible, you can try to find a feasible solution by rerunning
You can control some aspects of
solve by creating a tabu search
algorithm object, which contains properties for the tabu search. Pass the tabu search object
with specified properties to
solve. For example, to have
solve use more time and iterations than the defaults, enter
ts = tabuSearch(MaxTime=60,MaxIterations=1e7); result = solve(qprob,Algorithm=ts)
For details about the properties and their default values, see
When your problem has constraints expressed as a penalty term, some results might violate the constraints. See Examine Solutions for Feasibility.
Alternative Solution for Simple Problems Using Optimization Toolbox
If your QUBO problem has only a few variables (up to perhaps 100 or 200), and you have
an Optimization Toolbox™ license, convert the QUBO to a mixed-integer linear problem and solve it using
intlinprog. The advantage of using
that the resulting solution is guaranteed to be optimal. The disadvantages are that the size
of the problem is limited, and the solver can take a long time to finish. For details, see
Verify Optimality by Solving QUBO as MILP.