Layout Construction: A Case Study In Algorithm Engineering

We design a system for generating newspaper layout proposals. The input to the system consists of editorial information (text, pictures, etc) and style information (non-editorial information that specifies the aesthetic appearance of a layout). We consider the automation of layout construction to pose two main problems. One problem consists in optimizing the layout with respect to the constraints and preferences specified in the style information. Another problem consists in finding a representation of the style information that both supports its use in the combinatorial optimization and supports its modification through high level user interaction and automatic inference from a database of examples. We propose a solution that combines heuristic search, randomization and neural networks. We have implemented a first version based on the bisection strategy -- a page is bisected recursively until the number of sub-divisions matches the number of articles to be placed