Constraints in QUBO Problems

Note

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

Include Constraints by Penalty Function

Although the name QUBO stands for Quadratic Unconstrained Binary Optimization, many problems are most naturally formulated using constraints. For example, the Traveling Salesperson Problem with QUBO example has these constraints: the salesperson visits each city exactly once, and each step of the tour is in one city.

To ensure that constraints are satisfied at a solution for a QUBO problem, add a positive multiplier M times a quadratic function that is positive for unsatisfied constraints and zero for satisfied constraints. For example, suppose you have the constraint that exactly two components of x are equal to 1. This constraint can be formulated as

$${\left({\displaystyle \sum _i{x}_i}-2\right)}^2=0.$$

Include the constraint in a QUBO problem by adding the penalty term

$$M{\left({\displaystyle \sum _i{x}_i-2}\right)}^2.$$

For a large enough M, this penalty causes a solution to the QUBO problem

$$x^{T}Qx+\text{}{c}^{T}x+\text{}M{\left({\displaystyle \sum _i{x}_i}-2\right)}^2$$

to have the penalty term equal to zero; otherwise, the objective function value is not minimized. In other words, the penalty term enforces the constraint.

This constraint term can be represented as a QUBO expression. The penalty term without the multiplier M is

$${\left({\displaystyle \sum _i{x}_i}\right)}^2-4{\displaystyle \sum _i{x}_i}+4=0.$$

To represent this quadratic constraint as a QUBO, take A = ones(N), an all-1 matrix of coefficients for a quadratic term

$$A=\left(\begin{array}{cccc}1& 1& \cdots & 1\\ 1& 1& \cdots & 1\\ ⋮& ⋮& \ddots & ⋮\\ 1& 1& \cdots & 1\end{array}\right).$$

Then, A represents the quadratic term

$$x^{T}Ax={\left({\displaystyle \sum _i{x}_i}\right)}^2.$$

Add a penalty term to enforce the constraint by taking a large positive multiplier M and adding these expressions to your QUBO problem: M*A to the quadratic term, –4*M*ones(N,1) to the linear term, and 4*M to the constant term.

Do not take a very large multiplier M, because doing so might cause the problem to lose precision when it involves a large variation in the function values. Especially when you use quantum annealing hardware to solve a QUBO problem, the number of digits available for computations is limited. Therefore, a multiplier M that is too large might make the problem unsuitable for the hardware.

Examine Solutions for Feasibility

When you incorporate constraints into your QUBO problem by using a penalty term, the returned solution might violate the constraints. Check the feasibility of a solution by examining the constraint function values. The result is feasible if the constraint function evaluates to zero at the solution.

Suppose that your original problem has the following quadratic term with no linear or constant terms.

Q = [0 -5 2 -6
    -5 0 -1 3
    2 -1 0 -4
    -6 3 -4 0];

The constraint is that exactly two elements in the solution are equal to 1. Create and solve the problem with no constraints.

qprob = qubo(Q);
result = solve(qprob)

result = 

  quboResult with properties:

                BestX: [4×1 double]
    BestFunctionValue: -22
      AlgorithmResult: [1×1 tabuSearchResult]

Does the unconstrained solution satisfy the constraint that exactly two x_i are nonzero?

result.BestX

ans =

     1
     1
     1
     1

No, the constraint is not satisfied because the solution has too many ones.

Create and solve a new problem with a linear term, a constant term, and the constraint multiplier M set to 1.

A = ones(4);
c = -4*ones(4,1);
d = 4;
M = 1;
qprob2 = qubo(Q + M*A, M*c, M*d);
sol2 = solve(qprob2)

sol2 = 

  quboResult with properties:

                BestX: [4×1 double]
    BestFunctionValue: -18
      AlgorithmResult: [1×1 tabuSearchResult]

Check whether the solution satisfies the constraints.

constrs = qubo(M*A, M*c, M*d); % QUBO problem just for constraints 
evaluateObjective(constrs,sol2.BestX)

ans =

     4

No, the solution does not satisfy the constraints because they do not evaluate to 0.

Increase the penalty M and then solve the problem again.

M = 10;
qprob2 = qubo(Q + M*A, M*c, M*d);
sol3 = solve(qprob2)

sol3 = 

  quboResult with properties:

                BestX: [4×1 double]
    BestFunctionValue: -12
      AlgorithmResult: [1×1 tabuSearchResult]

Check the result for feasibility.

constrs = qubo(M*A, M*c, M*d); % QUBO problem just for constraints 
evaluateObjective(constrs,sol3.BestX)

ans =

     0

This time, the constraints are satisfied. For this simple problem, you can see that the constraints are satisfied by looking at BestX.

sol3.BestX

ans =

     1
     0
     0
     1

In general, if your solution is infeasible, you can try to find a feasible solution by doing one of the following:

• Examine other returned solutions for feasibility by looking at the returned quboResult.AlgorithmResult object. The AllX property has potential solutions that you can examine for feasibility.

• Rerun the problem using a higher value for the penalty term.

For Ising formulations of common constraints, see Lucas [1]. Ising formulations are equivalent to QUBO formulations; see What Is a QUBO Problem?

References

[1] Lucas, Andrew. Ising formulations of many NP problems. Available at https://arxiv.org/pdf/1302.5843.pdf.