Improvements to Keyboard Optimization with Integer Programming, UIST 2014

Improvements to Keyboard Optimization with Integer Programming

Andreas Karrenbauer¹ Antti Oulasvirta²

¹ MPI for Informatics, Germany ² Aalto University, Finland

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 outcomes. Second, it guarantees bounds, which increases the designer's confidence over the quality of results. We report improvements to three keyboard optimization cases.

Materials for Download

	The paper (Adobe Acrobat PDF, 0.3 MB).
	The BibTeX.

UIST 2014 materials:

Talk (Adobe Acrobat PDF, 4.1 MB).

Addditional Materials

Experimental Data: probabilities, inter-key intervals, and parameters

	case data	26 Letter Trapezoid Layout for Touchscreens. Common on smartphones with touchscreens. Bigrams combines two corpora with equal weights: mobile email [25] and NUS SMS [7].
	case data	The Zhai-Hunter-Smith Hexagonal Layout. Movement model and bigrams as in Zhai et al. [25].
	case data	3-Row Physical Keyboard for Ten-Finger Typing. The full 34 character 3-row physical keyboard. Movement model based on Hiraga et al. [13]. Bigrams are combined from five corpora: chat room data, mobile email, newspaper English, SMS data, and Tweets.

Source Code: LP-file generators written in C++

source code in a gzipped tar archive also containing a README file with instructions.

Citation

Andreas Karrenbauer, Antti Oulasvirta
Keyboard Optimization by Integer Programming
Proceedings of the 27th Annual ACM Symposium on User Interface Software and Technology, UIST ’14, pp. 621-626, 2014.

  @inproceedings{KO2014,
  author = {Karrenbauer, Andreas and Oulasvirta, Antti},
  title = {{Improvements to Keyboard Optimization with Integer Programming}},
  booktitle = {Proceedings of the 27th Annual ACM Symposium on User Interface Software and Technology},
  series = {UIST '14},
  year = {2014},
  isbn = {978-1-4503-3069-5},
  location = {Honolulu, Hawaii, USA},
  pages = {621--626},
  numpages = {6},
  url = {http://doi.acm.org/10.1145/2642918.2647382},
  doi = {10.1145/2642918.2647382},
  acmid = {2647382},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {branch-and-bound, integer programming, keyboard layouts, random search methods, user interface optimization},
  }