## 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\\ \vdots & \vdots & \ddots & \vdots \\ 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.

## See Also

`solve`

| `qubo`

| `evaluateObjective`

| `tabuSearch`