DocEng 2011: Optimal Automatic Table Layout September 26, 2011

Favorite:

The 11th ACM Symposium on Document Engineering
Mountain View, California, USA
September 19-22, 2011

Optimal Automatic Table Layout
Graeme Gange, Kim Marriott, Peter Moulder, Peter Stuckey

Presented by Kim Marriott

ABSTRACT

Automatic layout of tables is useful in word processing applications and is required in on-line applications because of the need to tailor the layout to the viewport width, choice of font and dynamic content. However, if the table contains text, minimizing the height of the table for a fixed maximum width is a difficult combinatorial optimization problem. We present three different approaches to finding the minimum height layout based on standard approaches for combinatorial optimization. All are guaranteed to find the optimal solution. The first is an A*-based approach that uses an admissible heuristic based on the area of the cell content. The second and third are constraint programming (CP) approaches using the same CP model. The second approach uses traditional CP search, while the third approach uses a hybrid CP/SAT approach, lazy clause generation, that uses learning to reduce the search required. We provide a detailed empirical evaluation of the three approaches and also compare them with two mixed integer programming (MIP) encodings due to Bilauca and Healy.