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.

Traveling salesman problem

Fig. 25 The traveling salesperson problem is an optimization problem that can be solved using exactly-one-true constraints. Map data © 2017 GeoBasis-DE/BKG (© 2009), Google.

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,

\[a + b + c = 1.\]

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:

\[E(a,b,c) = (a + b + c - 1)^2.\]
[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.

\[\begin{split}E(a,b,c) &= a^2 + ab + ac -a + ba + b^2 + bc -b + ca + cb + c^2 -c -a - b -c +1 \\ &= a^2 + b^2 + c^2 + 2ab + 2ac + 2bc - 2a - 2b - 2c + 1 \\ &= 2ab + 2ac + 2bc - a - b - c + 1,\end{split}\]

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

\[\begin{split}E_{qubo}(a_i, b_{i,j}; q_i) &= \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j \\ E_{qubo}(a_i, b_{i,j}; q_1, q_2, q_3) &= a_0 q_0 + a_1 q_1 + a_2 q_2 + b_{0,1} q_0 q_1 + b_{0,2} q_0 q_2 + b_{1,2} q_1 q_2 ,\end{split}\]

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.