# Constraints Example: Problem Formulation¶

The example of the Unconstrained Example: Solving a SAT Problem chapter formulated
an objective function for a simple SAT problem. As mentioned, the D-Wave
quantum computer is also well suited to solving optimization problems with binary
variables. Real-world optimization problems often come with *constraints*: conditions
of the problem that any valid solution must satisfy.

For example, when optimizing a traveling salesperson’s route through a series of cities, you need a constraint forcing the salesperson to be in exactly one city at each stage of the trip: a solution that puts the salesperson in two or more places at once is invalid.

In fact, the example of the Unconstrained Example: Solving a SAT Problem chapter
is actually also an example of a simple constraint, the equality (or XNOR)
constraint. The example of this section is slightly more complex. The
*exactly-one-true* constraint is the Boolean satisfiability problem of
finding, given a set of variables, when exactly one variable is TRUE (equals
1). This chapter looks at an exactly-one-true constraint for three variables.

The problem-solving process is the same as described in the Solving Problems with Quantum Samplers chapter.

Note

Quantum samplers optimize objective functions that represent problems in
formats that are *unconstrained* (e.g., QUBOs, or unconstrained binary
optimization problems). As is shown in this chapter, any constraints in the
original problem are represented as part of the objective function; this
technique is known as penalty models.

Some Leap quantum-classical hybrid solvers accept only unconstrained objective functions; for example, hybrid BQM solvers. For those too any constraints must be added to the objective function, typically as a penalty. However, some Leap hybrid solvers can handle constraints natively, as shown in the Simple Workflow Example example. For more information, see the Using Leap’s Hybrid Solvers section.

## Formulating an Objective Function¶

For problems with a small number of binary variables (in this example three: \(a\), \(b\), and \(c\)), you can tabulate all the possible permutations and identify the states when exactly one variable is 1 and the other two are 0. You do so with a truth table:

\(a\) |
\(b\) |
\(c\) |
Exactly One is True |
---|---|---|---|

0 |
0 |
0 |
FALSE |

1 |
0 |
0 |
TRUE |

0 |
1 |
0 |
TRUE |

1 |
1 |
0 |
FALSE |

0 |
0 |
1 |
TRUE |

1 |
0 |
1 |
FALSE |

0 |
1 |
1 |
FALSE |

1 |
1 |
1 |
FALSE |

Notice that the three constraint-satisfying states in the truth table have in common that the sum of variables equals \(1\), so you can express the constraint mathematically as the equation,

As noted in the Workflow: Formulation and Sampling chapter, you can solve some equations by minimization if you formulate an objective function that takes the square1 of the subtraction of one side from another:

- 1
If you do not square, the minimum for \(\tilde{E}(a,b,c) = a + b + c - 1\) is \(\tilde{E}(a=b=c=0) = -1\) which is lower than for any of the three constraint-satisfying states, such as \(\tilde{E}(a=b=0;c=1)=0\).

Expanding the squared term—while remembering that for binary variables with values 0 or 1 the square of a variable is itself, \(X^2 = X\)—shows in explicit form the objective function’s quadratic and linear terms.

Notice that this objective formula matches the QUBO format for three variables,

where \(a_i=-1\) and \(b_{i,j}=2\), with a difference of the \(+1\) term.2

- 2
A constant term in an objective function does not affect the solutions because it just increases or decreases energies (values of the objective) for all states by the same amount, preserving relative ordering.

Below, the truth table is shown with an additional column of the energy for the objective function found above. The lowest energy states (best solutions) are those that match the exactly-one-true constraint.

\(a\) |
\(b\) |
\(c\) |
Exactly One is True |
Energy |
---|---|---|---|---|

0 |
0 |
0 |
FALSE |
1 |

1 |
0 |
0 |
TRUE |
0 |

0 |
1 |
0 |
TRUE |
0 |

1 |
1 |
0 |
FALSE |
1 |

0 |
0 |
1 |
TRUE |
0 |

1 |
0 |
1 |
FALSE |
1 |

0 |
1 |
1 |
FALSE |
1 |

1 |
1 |
1 |
FALSE |
4 |

Clearly, a solver minimizing the objective function
\(2ab + 2ac + 2bc - a - b - c\) can be expected to return solutions (values
of variables \(a, b, c\)) that satisfy the original problem of an
*exactly-one-true* constraint.

As explained in the Solving Problems with Quantum Samplers chapter, to solve a QUBO with a D-Wave quantum computer, you must map (minor embed) it to the QPU. That step is explained in detail in the next chapter.

The Constraints Example: Submitting to a QPU Solver chapter then shows how the problem is submitted for solution to a D-Wave quantum computer.