# Constraints Example: Problem Formulation¶

The example of the Simple Example: Solving a SAT Problem chapter formulated
an objective function for a simple SAT problem. As mentioned, the D-Wave
system 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 Simple 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 D-Wave Solvers chapter.

## 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 Solving Problems with D-Wave Solvers chapter, you can solve some equations by minimization if you formulate an objective function that takes the square[1] 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 D-Wave Solvers 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 D-Wave System chapter then shows how the problem is submitted for solution to a D-Wave quantum computer.