Question

You are given a Boolean formula involving variables X₁, X₂, ... X_n. The Boolean formula is of form (C₁ AND C₂ AND C₃... AND C_m), where each clause is a disjunction (logical "or" function) of the X variables. You have to assign true/false values to the variables so as to maximize the number of clauses that evaluate to true. Present a branch and bound approach for this optimization problem.

Answer 1

If it is branch and bound, just scan every possibility. The time complicity for scan should be n^2 and use n to know the answer. So the totally tc=2^n*n^3=2^n. This is the worse case like bound does not work for every case. But as the answer of the formula is largely depend on the result before and it can be stopped before scanning every answer, there must be some better answer like divide and conquer. Also, we can make a graph of the different variables with the formula, and change the question into m graphs.

Answer 2

The concept revolves around constructing a rooted tree as a solution space, beginning from a root node where no truth values have been assigned to any of the 'n' variables. Two child nodes emerge from this root, each representing one of the binary states (true or false) of a chosen variable 'X_i'. Subsequent child nodes are generated, each focusing on a different variable. This structure results in a tree of height 'n' and 2ⁿ leaf nodes, indicating a potential for exponential time complexity in the worst case of the branch and bound algorithm. However, practical scenarios often allow for substantial pruning of the tree, greatly reducing time complexity.

For bounds, in a maximization problem, the lower bound represents a feasible solution, attainable in O(n) time, based on the truth status of certain clauses. The upper bound is the total number of clauses not confirmed as false. 

The efficiency of the algorithm largely depends on the ordering criteria. A suggested approach is to prioritize variables based on their 'incidence' count, which is the frequency of a variable's appearance in the clauses, adjusted by the frequency of its negation. This method significantly impacts the practical execution time of the algorithm.