Andreas Karrenbauer
Antti Oulasvirta
ABSTRACT
Keyboard optimization is concerned with the design of keyboards for different terminals, languages, user groups, and tasks. Previous work in HCI has used random search based methods, such as simulated annealing. These "black box" approaches are convenient, because good solutions are found quickly and no assumption must be made about the objective function. This paper contributes by developing integer programming (IP) as a complementary approach. To this end, we present IP formulations for the letter assignment problem and solve them by branch-and-bound. Although computationally expensive, we show that IP offers two strong benefits. First, its structured non-random search approach improves the out- comes. Second, it guarantees bounds, which increases the designer's confidence over the quality of results. We report improvements to three keyboard optimization cases.
- Adams, W. P., and Johnson, T. A. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS 16 (1994), 43--75.Google Scholar
- Bailly, G., et al. Menuoptimizer: Interactive optimization of menu systems. In Proc. UIST, ACM (2013), 331--342. Google ScholarDigital Library
- Bertsimas, D., and Tsitsiklis, J. Introduction to Linear Optimization, 1st ed. Athena Scientific, 1997. Google ScholarDigital Library
- Bi, X., Smith, B. A., and Zhai, S. Multilingual touchscreen keyboard design and optimization. Human--Computer Interaction 27, 4 (2012), 352--382.Google Scholar
- Bixby, R., and Rothberg, E. Progress in computational mixed integer programming. Annals of Operations Research 149, 1 (2007), 37--41.Google ScholarCross Ref
- Burkard, R. E., and Offermann, D. M. J. Entwurf von schreibmaschinentastaturen mittels quadratischer zuordnungsprobleme. Zeitschrift fur Operations Research 21, 4 (1977), B121--B132.Google Scholar
- Chen, T., and Kan, M.-Y. Creating a live, public short message service corpus: The nus sms corpus. Language Resources and Evaluation 47, 2 (2013), 299--335.Google Scholar
- Dunlop, M., and Levine, J. Multidimensional pareto optimization of touchscreen keyboards for speed, familiarity and improved spell checking. In Proc. CHI, ACM (2012), 2669--2678. Google ScholarDigital Library
- Eggers, J., et al. Optimization of the keyboard arrangement problem using an ant colony algorithm. European Journal of Operational Research 148, 3 (2003), 672--686.Google ScholarCross Ref
- Gajos, K., and Weld, D. S. Supple: automatically generating user interfaces. In Proc. IUI, ACM (2004), 93--100. Google ScholarDigital Library
- Goettl, J. S., Brugh, A. W., and Julstrom, B. A. Call me e-mail: arranging the keyboard with a permutation-coded genetic algorithm. In Proc. Applied Computing, ACM (2005), 947--951. Google ScholarDigital Library
- Hahn, P. M., et al. A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J. on Computing 24, 2 (Apr. 2012), 202--209. Google ScholarDigital Library
- Hiraga, Y., et al. An assignment of key-codes for a japanese character keyboard. In Proc. Computational Linguistics, ACL (1980), 249--256. Google ScholarDigital Library
- Kaufman, L., and Broeckx, F. An algorithm for the quadratic assignment problem using bender's decomposition. European Journal of Operational Research 2, 3 (1978), 207--211.Google ScholarCross Ref
- Koopmans, T. C., and Beckmann, M. Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society (1957), 53--76.Google ScholarCross Ref
- Lawler, E. L., and Wood, D. E. Branch-and-bound methods: A survey. Operations research 14, 4 (1966), 699--719.Google Scholar
- Lewis, J., Potosnak, K., and Magyar, R. Keys and keyboards. Handbook of Human-Computer Interaction (1997), 1285--1315.Google Scholar
- Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., and Querido, T. A survey for the quadratic assignment problem (2007). 657--690.Google Scholar
- MacKenzie, I. S., and Zhang, S. X. The design and evaluation of a high-performance soft keyboard. In Proc. CHI, ACM (1999), 25--31. Google ScholarDigital Library
- Oulasvirta, A., et al. Improving two-thumb text entry on touchscreen devices. In Proc. CHI, ACM (2013), 2765--2774. Google ScholarDigital Library
- Pollatschek, M., Gershoni, N., and Radday, Y. Optimization of the typewritter keyboard by computer simulation. Angewandte Informatik 10 (1976), 438--439.Google Scholar
- Rao, S. S. Engineering optimization. John Wiley & Sons, 2009.Google ScholarCross Ref
- Vertanen, K., and Kristensson, P. O. A versatile dataset for text entry evaluations based on genuine mobile emails. In Proc. MobileHCI'11, ACM (2011), 295--298. Google ScholarDigital Library
- Wolsey, L. A. Integer Programming, vol. 42. Wiley New York, 1998.Google Scholar
- Zhai, S., Hunter, M., and Smith, B. A. Performance optimization of virtual keyboards. Human--Computer Interaction 17, 2--3 (2002), 229--269.Google ScholarCross Ref
Index Terms
- Improvements to keyboard optimization with integer programming
Recommendations
Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming
This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to ...
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem
In this paper, we consider problem (P) of minimizing a quadratic function q(x)=xtQx+ctx of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective ...
Branch-And-Price: Column Generation for Solving Huge Integer Programs
We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound ...
Comments