Optimal partitioning of n-tuples
You might start from an initial solution computed using one of your two models, and then apply local search: consider any movement of one set from a group to another, and apply it if it does not violate the group constraints and it improves $\Phi$. 

Local search is a common approach in graph partitioning, thus it is probably already a part of what KaHIP is doing, but even if it is, you would now do it with the correct measure, $\Phi$, not its surrogate, so the outcome is likely to be improved.