  Computational design of menu systems has been solved in limited cases such as
the linear menu (list) as an assignment task, where commands are assigned to
menu positions while optimizing for for users selection performance and
distance of associated items. We show that this approach falls short with
larger, hierarchically organized menu systems, where one must also take into
account how users navigate hierarchical structures. This paper presents a novel
integer programming formulation that models hierarchical menus as a combination
of the exact set covering problem and the assignment problem. It organizes
commands into ordered groups of ordered groups via a novel objective function
based on information foraging theory. It minimizes, on the one hand, the time
required to select a command whose location is known from previous usage and,
on the other, the time wasted in irrelevant parts of the menu while searching
for commands whose location is not known. The convergence of these two factors
yields usable, well-ordered command hierarchies from a single model. In
generated menus, the lead (first) elements of a group or tab are good
indicators of the remaining contents, thereby facilitating the search process.
In a controlled usability evaluation, the performance of computationally
designed menus was 25 faster than existing commercial designs with respect to
selection time. The algorithm is efficient for large, representative instances
of the problem. We further show applications in personalization and adaptation
of menu systems.
