# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 6 Solving the Optimization Problem  
For each gadget type, we need to define a single-cell Ising program so that conditions (6) are satisfied for all possible tiles \(\tau\) for that gadget, and the value of the gap parameter \(\gamma\) is maximized. We will give details for the internal gadget  since it is the most interesting. For this gadget, we have 4 good tiles, and, and all others are bad tiles. Denote this Ising program by \(Is^{*}(\mathbf{t})\) and its coefficients by \(\mathbf{c}^{*}\) (since internal gadgets do not have \(\mathbf{x}\) variables, their coefficients in front of the \(x_{i}x_{j}\) and \(x_{i}t_{j}\) terms are zeros). Define sets _Good_ of all 4-tuples \((t_{1},t_{2},t_{3},t_{4})\) of interface variables of good internal tiles (see Figure 2) and _Bad_ of all remaining 4-tuples. Then we formulate the following optimization problem.  
**Problem 2**.: _Find values for the coefficients \(\mathbf{c}^{*}\) and parameters \(\mu\) and \(\gamma\) such that \(Is^{*}(\mathbf{t})\) satisfies the conditions_  
1. _For all_ \((t_{1},\ldots,t_{4})\in\textit{Good}\ \exists\,t_{5},\ldots,t_{8}\ \textit{s.t.}\ Is^{*}(\mathbf{t})=\mu\)_,_
2. _For all_ \((t_{1},\ldots,t_{4})\in\textit{Good}\ \forall\,t_{5},\ldots,t_{8}\ \ Is^{*}(\mathbf{t})\geq\mu\)_,_
3. _For all_ \((t_{1},\ldots,t_{4})\in\textit{Bad}\ \forall\,t_{5},\ldots,t_{8}\ \ Is^{*}(\mathbf{t})\geq\mu+\gamma\)__  
_and \(\gamma\) is maximized._  
This is the same type of problem as Problem 1, but of much smaller size. We model Problem 2 as a mixed-integer programming (MIP) problem. We replace each variable \(t_{i}\in\{-1,1\}\) by a binary variable \(t_{i}^{\prime}\in\{0,1\}\) using the linear transformation \(t_{i}^{\prime}=(t_{i}+1)/2\). Since \(Is^{*}(\mathbf{t})\) is linear with respect to variables \(\mathbf{c}^{*}\), conditions (C2\({}^{\prime}\)) and (C3\({}^{\prime}\)) of Problem 2 can be easily encoded as linear constraints. To encode condition (C1\({}^{\prime}\)), we introduce, for each \(g=(t_{1},\ldots,t_{4})\in\textit{Good}\), new binary variables \(t_{i}(g)\), \(i=5,\ldots,8\) corresponding to the values \(t_{5},\ldots,t_{8}\) from condition (i). This introduces \(|\textit{Good}|\cdot 4=16\) binary variables. Then (C1\({}^{\prime}\)) is replaced by  
\[(\text{C1}^{\prime\prime})\ \text{For all}\ g=(t_{1},\ldots,t_{4})\in\textit{Good} \ \text{and for}\ t_{i}=t_{i}(g),i=5,\ldots,8\ Is^{*}(\mathbf{t})=\mu\]  
This removes the \(\exists\) predicate, but since the Ising program coefficients \(\mathbf{c}^{*}\) are variables, the resulting constraint is cubic (there are cubic terms of the type \(c_{ij}t_{i}t_{j}\)).  
We linearize each such product \(t_{i}t_{j}\) by introducing a new real variable \(t_{ij}=t_{i}t_{j}\) and adding the constraints  
\[t_{ij}\geq 0,\quad t_{ij}\leq t_{i},\quad t_{ij}\leq t_{j},\quad t_{ij}\geq t_{i} +t_{j}-1.\]  
and we use a similar technique to linearize quadratic terms of the type \(c_{ij}t_{ij}\), where \(c_{ij}\) is real and \(t_{ij}\) is binary.  
We implemented Problem 2 using the AMPL modeling language [27] and the Gurobi solver [28]. The resulting linear program has 16 binary variables, 234 continuous variables, and 884 constraints. [PERSON] found the optimal solution in a tiny fraction of a second, with \(\gamma=4\) and \(\mu=-10\). Please note that a value \(\gamma=2\) would have been sufficient, since the penalty for mismatched adjacent tiles is only 2 and the gap for the entire Ising program is the minimum of the gap between good and bad tiles and the gap between good and bad tile pairs.  
**Corollary 1**.: _The Ising program \(Is(R)\) defined in Section 5 is a solution of Problem 1 with \(\gamma=2\)._