The line breaking problem is as follows: given some text and a page to print to, where are the best places to start new lines within the paragraphs for the most visually appealing layout? The most well-known and used optimizing typesetting software is T_eX, which solves the line breaking problem according to an internal function of a paragraph’s “badness” (Knuth & Plass1981).

We propose an alternative formulation of the problem in which the quality of a candidate paragraph is measured along several objective functions which are easily defined by real-world solution-space metrics. Rather than presenting a single solution to the user, our algorithm finds the Pareto-optimal set of paragraphs given a set of objective functions [multi-objective optimization].

To support our algorithm, we devise a new method for determining feasible hyphenation points within a paragraph in a single pass, which is general enough to apply to and improve the original T_eX algorithm.

Our results show that global multiple objective paragraph optimization gives solutions consistently better than T_eX along our real-world metrics, and that a range of solutions are returned representing a genuine trade-off in typographic quality.

…In this paper we present an alternative formulation of the line breaking procedure, in which the badness function is vector-valued. Each element of the vector corresponds to a single typographical feature, for example, the word spacing or the number of line-breaking hyphenations. Rather than return a single optimal solution, we return to the user the Pareto-optimal set of solutions. This set of solutions are optimal in the sense that none can be improved along any dimension without decreasing the score along another. The user is then free to apply a secondary weighting procedure to the set to select one, or use their domain-specific knowledge to choose the most appropriate or visually pleasing solution.

…Multiple objective optimization is a field gaining much recent attention across a range of problem types. Multiple objective dynamic programming is a particularly difficult problem that has not been “solved” to date. We also examine other methods of multiple objective optimization, such the use of evolutionary and sociological models.

See Also: