Recent Results

[isPANN]

Main results

I define BooleanInference-Default as the solver configuration (Selector)MostOcc(3,k) + (Measure)NumHardTensor, which achieves the relatively best overall average performance across datasets.
Here k is the maximum number of tensors inside one selected region. For each factoring dataset, I'll choose the k leading to the least number of branches.

[isPANN]

Selector comparison

Now we have implemented 2 different selectors to choose variables at each decision level. At the beginning of the algorithm, I'll cache the region related to each variable. So each time the selector pick a variable, the algorithm will directly index the cached region, rather than constructing the region dynamically during the search process.

• MinGammaSelector: This selector will "look forward" to each unfixed variable at every decision level and do pre-branch and examine the leading $\gamma$ vaule. The selector will always choose the variable with the minimum $\gamma$ value.
• MostOccurrenceSelector: This selector will calculate a score for each unfixed variable at every decision level. The score is the number of hard tensors (the tensor containing more than 2 unfixed variables) connected to one variable. At each time, the selector will choose the variable with the maximum score. Moreover, when the score vector becomes all zero, this means the problem is reduced to a 2SAT problem.

(Note: here the measure is fixed to NumHardTensor)

[isPANN]

Measure Comparison

The measure measures the size of the subproblem created by the branching algorithm. Here we implement 2 measures.

• NumHardTensors: calculate the number of hard tensors (those tensors containing more than 2 unfixed vars) in subproblem.
• NumUnfixedVars: calculate the number of unfixed variables in subproblem.

MinGammaSelector

MostOccurrenceSelector

[isPANN]

Region Size Sensitivity

I find some instance are very sensitive to the choice of the region size.
I calculated the Coefficient of Variation (CV) of each instance under different region size.

sensitivities = [std(branch_matrix[i, :]) / mean(branch_matrix[i, :]) for i in 1:num_instances]

#TODO: This need to figure out why.

[isPANN]

Something need to be done

• Compare with NaiveBranch.
• Add datasets for k-SAT.
• Tree width measure?
• Try another new measure CoverSetSize: We want to know in order to make the current subproblem easy, how much variables do we need to fix at least. So we need to select the smallest set of variables such that every hard tensor is associated with at least one variable from this set. (This process is very slow, so maybe calculate in the beginning, and do not change during the algorithm)

[isPANN]