Regarding how to find a good partitioning of values for 2-way braching,
here's a suggestion, it's nothing amazing but might help as a starting
point:
The variable ordering heuristic selects which variable to branch
on next, and has a dramatic effect on search time. As you can imagine,
one which is quick to calculate but mildly inccurate might be rougly equal
in usefulness to one which is slower to calculate but more accurate. I
implemented two different [variable ordering] heursitics in NB-satz, MOMS
and UP (short for unit propagation). They are both explained in my report,
the MOMS one is quite intuitive and widely known, the UP one is well
presented in the Chu Min Li paper, referenced in my report (I couldn't
find it on the web anywhere, but your local university might have the
IJCAI '97 conference proceedings). Basically the UP heuristic does a
"lookahead" which is this:
- A number of candidate variables are chosen for further
examination.
- These variables are examined, one at a time. This means that the
first candidate variable is taken as the branching variable, the
branch is made and each of the 2 resulting subtrees are given a
score. The original formula is then restored and the same is
done for the second and third candidate variables and so on ...
- When all of the candidate variables have been scored, the one
with the highest score is chosen to be the branching variable.
The UP heuristic typically scores based on the amount of unit
propagation acheived in each of the resultant subtrees.
So basically a few candiaidates are chosen (to restrict the amount
of work to be done - the lookahead step is typically quite expensive
so a restriction can be efficient) and the effects of branching on
each of them are assessed. Now for my idea (finally!) - maybe something
similar could work for finding the optimal set partitioning? There could
be a restriction to get the number of lookaheads down to a reasonable
figure, possibly by restricting the sizes of the two partitions to be
roughly equal, or forcing them to be skewed one way (e.g. {1,4},
{2,3,5,6,7,8,9}). Then the lookahead step could again be scored by the
amount of unit propagation (or semi-unit propagation, or a weighted
combination of the two) and the best chosen, just as in the UP heuristic.
Seeing as the UP heuristic (basically a trial-and-error test on all likely
candidates) manages to work well, maybe the same technique could be
applied to the value-set partitioning problem?