Using machine learning to synthesize search programs

This paper describes how machine learning techniques are used in the MULTI-TAC system to specialize generic algorithm schemas for particular problem classes. MULTI-TAC is a program synthesis system that generates Lisp code to solve combinatorial integer constraint satisfaction problems. The use of algorithm schemas enables machine learning techniques to be applied in a very focused manner. These learning techniques enable the system to be sensitive to the distribution of instances that the system is expected to encounter. We describe two applications of machine learning in MULTI-TAC. The system learns domain specific heuristics, and then learns the most effective combination of heuristics on the training instances. We also describe empirical results that reinforce the viability of our approach