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.

Fig. 30 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 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,

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

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 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 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.