# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 3 Combinatorial Problems as Univariate Finite Domain Functions  
In this section, we show that any problem with a _combinatorial_ complexity of \(O(2^{n})\) can be reduced to a _univariate_ function with a domain of size \(\Omega(2^{n})\). The reduction is quite general and can also be applied to problems with a combinatorial complexity of \(O(poly(n)^{poly(n)})\). Here, the different branching factor \(m\) has to be considered. The reduction algorithm (seen in Algorithm 1) assumes that the problem instance can be viewed as a decision tree (see Figure 3), where a left child arc of a decision node implies that the decision variable at the node is assigned as 0 and the right child arc implies the assignment of 1 (or vice versa). The function that the reduction produces, takes value in a domain \(D=[D_{0},D_{1}]\) and uses the value to find an assignment for the combinatorial problem instance. Finally, the function evaluates the combinatorial problem with the assignment derived from the input value. The algorithm starts by ordering the decision variables randomly. Next, the algorithm creates an objective function that accepts a value from a finite domain \(D=[D_{0},D_{1}]\). Based on the value passed to the function, the function always divides the remaining domain into two equally sized halves and selects the half that contains the value. At each selection of the half, the assignment is updated with the corresponding decision variable value based on which the halves were selected. When the domain has been completely split so that no more intervals can be selected, the original combinatorial problem instance is evaluated with the assignment and value of the evaluation (number of vertices in a clique, number of clauses satisfied, or number of vertices in a vertex-cover, and so forth) is scaled using the scaling parameter and eventually returned. The algorithm can be seen in Algorithm 1, and the geometric presentation of the combinatorial problem in Figure 3.  
If Algorithm 1 is called using a partial assignment (that is, some variables have already been assigned values), then the algorithm starts by randomly ordering the variables that have not been assigned to any values. Then, the algorithm produces the function for the remaining variables and uses the partial assignment as a basis of the final evaluation. ```
1:input:X (problem instance), V (variables), scale (scale of function values), P (partial assignment), \(D_{0}\), \(D_{1}\)
2:randomly sort V (if P contains values then discard assigned variables from V)
3:create black-box function with parameters x (point to evaluate), \([D_{0},D_{1}]\):
4:current := \([D_{0},D_{1}]\)
5:\(i\) := 0
6:while current \(\
eq\) single value do
7:a := first half of current
8:b := second half of current
9:current := a if x \(\in\) a else b
10:\(V_{i}\) := (1 or 0) based on current (whether a or b was selected)
11:\(i\) := \(i+1\)
12:endwhile
13:assignment := evaluate X with assignment of V and P
14:y := value of assignment (value of maximization / minimization problem)
15:scale y based on scale
16:return black box function (lines 3-15)
```  
**Algorithm 1** Combinatorial problem to finite domain univariate function  
In a combinatorial problem, whose combinatorial complexity is \(O(2^{n})\), there exist \(2^{n}\) different variable assignments. Algorithm 1 runs \(O(n)\) steps and at each step, the algorithm splits the remaining domain into two halves and selects another half as a new domain. The assignment for the combinatorial problem is updated based on the order of the variables, the depth at which the algorithm currently operates, and whether the value of input \(x\) belongs to the first or second half of the split interval (other half indicates, say, 0 value and the other half indicates 1 value). In this manner, the algorithm assigns each value of input \(x\in D,D=[D_{0},D_{1}]\) (\([1,2^{n}]\), for instance) with a different assignment, which is used to evaluate the combinatorial problem at the end of the algorithm.