For small n, you can reasonably brute-force all (n x n) multiplication formulae in characteristic 2 because there's a naive bound on the number of element multiplications and the coefficients are binary. As n gets large (say, n>3?), the cost of brute-force becomes prohibitive.

Beyond brute-force, I imagine that this problem could be phrased as a max-sat problem, mixed-integer linear program or similar. There are generic solvers that can get solutions for problems of moderate size. But unless it's a fairly rote translation to the solver's native representation, it's often better to write a custom solver and port heuristics into the notation native to the problem. As far as I understand it, that's the approach that the Fawzi et al and TFA took.