Domain Splitting

(2nd-May-2020)

• Another method for simplifying the network is domain splitting or case analysis. The idea is to split a problem into a number of disjoint cases and solve each case separately. The set of all solutions to the initial problem is the union of the solutions to each case.

• In the simplest case, suppose there is a binary variable X with domain {t,f}. All of the solutions either have X=t or X=f. One way to find them is to set X=t, find all of the solutions with this assignment, and then assign X=f and find all solutions with this assignment. Assigning a value to a variable gives a smaller reduced problem to solve.

• If the domain of a variable has more than two elements, for example if the domain of A is {1,2,3,4}, there are a number of ways to split it:

• Split the domain into a case for each value. For example, split A into the four cases A=1, A=2, A=3, and A=4.

• Always split the domain into two disjoint subsets. For example, split A into the two cases A∈{1,2} and the case A∈{3,4}.