Localizer
My next project, which evolved into my Ph.D. thesis, was the design and implementation of localizer, a modeling language for local search. Before localizer, the research on languages and tools for optimization focused exclusively on global search, i.e., algorithms based on systematic search, branch and bound, and constraint satisfaction.
Localizer demonstrates that local search can also be supported at a high level of abstraction. Local search algorithms perform a graph exploration by moving from configuration to configuration until some stability condition is met. The neighbors of the current configuration are defined in terms of local transformations affecting a small fraction of the computation state. Efficient local search implementation heavily depends on the ability to explore this neighborhood at minimal cost. Hence, an efficient local search algorithm requires incremental algorithms to maintain the computation state under local transformations.
The implementation of localizer is based on efficient algorithms which maintain complex algebraic and set expressions incrementally. These algorithms generalize finite differencing techniques used in optimizing compilers and other tools. The runtime complexity was analyzed in terms of the changes in the input/output which gives a better understanding of their performance than the traditional online model.
Localizer has been applied to a variety of problems including partitioning, scheduling, and routing problems. It generally reduced the development time by several orders of magnitude while inducing a small overhead in efficiency. The overall system is about 60000 lines of C++ and led to the publications of two journal papers.
