Comment by danvk

There are simpler ways to calculate a bound that don’t involve trees. You can read about the sum and max bounds in the WIP paper: https://github.com/danvk/hybrid-boggle/blob/main/paper

There are some examples in these old posts:

- https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde...

- https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-exampl...

These bounds are pretty effective at finding the global max for 3x3 Boggle, but 4x4 is a lot bigger.

There is a mapping from Boggle optimization to ILP, but I’ve seen no evidence that this is an efficient way to solve it. I’ve been told that branch and cut is usually better than branch and bound, but I don’t know whether it’s applicable to Boggle.