Why Local Search Excels in Expression Simplification
  Simplifying expressions is important to make numerical integration of large
expressions from High Energy Physics tractable. To this end, Horner's method
can be used. Finding suitable Horner schemes is assumed to be hard, due to the
lack of local heuristics. Recently, MCTS was reported to be able to find near
optimal schemes. However, several parameters had to be fine-tuned manually. In
this work, we investigate the state space properties of Horner schemes and find
that the domain is relatively flat and contains only a few local minima. As a
result, the Horner space is appropriate to be explored by Stochastic Local
Search (SLS), which has only two parameters: the number of iterations
(computation time) and the neighborhood structure. We found a suitable
neighborhood structure, leaving only the allowed computation time as a
parameter. We performed a range of experiments. The results obtained by SLS are
similar or better than those obtained by MCTS. Furthermore, we show that SLS
obtains the good results at least 10 times faster. Using SLS, we can speed up
numerical integration of many real-world large expressions by at least a factor
of 24. For High Energy Physics this means that numerical integrations that took
weeks can now be done in hours.
