# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 4 Human-Algorithm Collaboration in Bayesian Optimization
### Numerical Experiments  
We used the algorithms defined in Algorithms 1 and 3, with 50 randomly generated _maximum exactly-3 satisfiability_ (MAX E3 SAT) [36] instances and 25 randomly generated _maximum satisfiability_ (MAX SAT) [33] instances. MAX E3 SAT is a generalization of a _satisfiability_ problems where the goal is to find an assignment to satisfy the maximum number of clauses consisting exactly of 3 literals. In [37], it was shown that MAX E3 SAT can be approximated within a factor of at least \(8/9\), if the instances are randomly generated and in the \(7/8\) factor for all instances unless \(P=NP\)[36]. MAX E3 SAT differs from MAX SAT in that the number of literals in a clause has no restrictions in the latter, which can be approximated within the factor \(3/4\)[33]. For the numerical tests, we selected a discrete Wiener process as a statistical model for UCB2 because it does not require a hyperparameter selection during the iterations of Algorithm 3 if the variance is fixed as opposed to, say, squared exponential covariance (the lengthscale parameter is required, which may vary accross the domain). A discrete Wiener process \(W\) is a Gaussian process defined by Gaussian increments  
\[W_{t+u}-W_{t}\sim N(0,u) \tag{23}\]  
and  
\[W_{0}=0 \tag{24}\]  
The covariance function is defined in \(W\) for \(W_{s}\) and \(W_{t}\), \(t\geq s\) as  
\[\min\{s,t\} \tag{25}\]  
if the variance is fixed unit variance. We selected MAX SAT and MAX ESAT problems for numerical tests because they are well studied and understood optimization problems, and the function values are mostly non-zero everywhere (an assignment usually satisfies more than 0 clauses), as opposed to say, _maximum clique_. Hence, our hypothesis was that a discrete Wiener process would be a suitable statistical model for Algorithms 2 and 3. For the tests, we bootstrapped UCB2 by randomly selecting \(C\) points from the domain and used \(T:=C\), \(S:=T\), where \(C\) was the number of clauses. The instances in MAX ESAT had 125-350 clauses and in MAX SAT case, the instances had 125-250 clauses. We restricted the number of clauses because the standard implementation of UCB2 (or EI2) has a time complexity of \(O(N^{3})\), which yields a total of \(O(N^{5})\). We evaluated the results by calculating the number of satisfied clauses and comparing the number to the overall number of clauses in the instance. Note that some instances were not satisfiable with high probability. For the MAX E3 SAT, the highest achieved result was 0.944 of clauses being satisfied, while the lowest result was 0.792. The mean value of all 50 instances was 0.91 after rounding. For the MAX SAT, where the number of literals in a clause was not restricted and varied from 1 to 5 in every instance, the lowest percentage of satisfied clauses was 0.63, while the highest percentage was 1.0 of clauses satisfied. On average, the number of clauses satisfied was 0.77 after rounding. Figure 7: Algorithm 3 expands the cell with the highest upper bound (\(-v_{1}\), \(+v_{2}\)) and evaluates the upper bounds of cells (\(-v_{1}\), \(+v_{2}\), \(+v_{3}\)) and (\(-v_{1}\), \(+v_{2}\), \(-v_{3}\)) (upper bounds of cells (\(+v_{1}\)), and (\(-v_{1}\), \(-v_{2}\)) are known). The results from the numerical experiments indicate that the methods proposed in this paper offer quite powerful approximation methods for NP-hard optimization problems also in practise. However, it must be noted that the instances we used (random MAX SAT and MAX E3 SAT) were actually not quite the realizations of the discrete unit Wiener process--which might have caused the low approximation ratios for some of the used instances. UCB2 (and EI2) and Algorithm 3 require the function to be a realization of a given Gaussian process to provide a high approximation accuracy described in the previous section. The results can be seen in Table 1.  
In the future, we wish to extend the numerical studies to the problems that are usually considered harder to approximate than MAX E3 SAT (or even MAX SAT).