AZERTY amélioré – French keyboard layout optimized

In 2015, France's Ministry of Culture wrote to the French Parliament, criticizing the lack of standards for a keyboard layout. It pointed out that Azerty, the traditional layout, lacks special characters (like À, œ, etc.) needed for `proper' French and that many variants exist. The ministry was concerned that this hinders proper use of the language. For example, some French people were taught, incorrectly, that accents for capital letters (É, À, etc.) are optional, a belief sometimes justified by reference to their absence from Azerty. One year later, AFNOR, the French national organization for standardization, was tasked with producing a standard that resolves the issues. We, Maximilian John and Andreas Karrenbauer, joined this project in 2016 as optimization experts. 

Our task was to modify the placement of the special characters of the traditional Azerty keyboard while letters and numbers remain at their known positions. Going beyond prior work, the goal was not only to ensure high typing performance but we also considered ergonomics and learnability factors. 

However, this was not a typical case of one-shot optimization with a clearly defined model, which just has to be solved, because such a rigid approach offers only poor support for such complex socio- technical endeavors. It was rather a process that could be described as Participatory Optimization with multiple stakeholders with various fields of expertise, having divers and conflicting opinions that changed over time (such as the set of the special characters to be included and their respective importance). Furthermore, the public was consulted. 

In several meetings, the standardization committee discussed several solutions, evaluated the impact of manual changes on different parts of the objective, and altered the optimization model to find a compromise. Hence, the whole standardization process consisted of several rounds of gathering data, adapting the mathematical model for the problem, finding a (near-) optimal keyboard, presenting it to the committee who expressed further wishes for the objective, modifying the weighting of its components, and adding or removing certain characters. Eventually, the objective function stabilized as a combination of four different measures:
performance  – special characters that are often used in combination with fixed characters should be close together in order to minimize the time to type;
ergonomics – frequently used special characters should be quite central on the keyboard to avoid unhealthy stretches of the fingers;
intuitiveness  – special characters should be placed close to similar fixed characters and other special characters to simplify finding them on the keyboard;
familiarity  – frequent special characters should be placed close to their position in the original Azerty keyboard if this character was already positioned there. 

In particular, the requirement for intuitiveness makes the optimization problem hard as it leads to a quadratic objective function, thus, yields quadratic assignment problems (QAP), which are generally very hard to solve. This is an obstacle for using computational support in such a standardization process, because not only after the public inquiry, but also for every committee meeting, the underlying model was updated and new solutions were computed. 

We provided the committee many solutions corresponding to their varying demands. To this end, we developed a method to quickly assess the quality of solutions by computing near-optimal lower bounds using a novel column-generation approach [2] that exploits the sparsity of the quadratic part of the objective, which is common for instances of this use-case. Having these bounds at hand in a timely manner is important because deciding model changes based on very sub-optimal solutions is pointless, since the observed solution might not properly represent the current model. Therefore, it is not sufficient to only find near-optimal solutions, but also to have a sharp picture of their quality, allowing for a well-founded discussion and decision process. Additionally, it is important that such solutions to updated models and corresponding bounds can be computed as fast as possible, ideally even in real-time.

Finally, the expert committee agreed on a layout for the new French keyboard standard [1], which was presented to the public on 2 April 2019.
 

References

1. AFNOR. Interfaces utilisateurs - Dispositions de clavier bureautique français, NF Z71-300, Avril 2019. La Plaine Saint-Denis: AFNOR, Version de 2019-04-P, 85 p.
2. M. John and A. Karrenbauer. Dynamic sparsification for quadratic assignment problems. In M. Khachay, Y. Kochetov, and P. Pardalos, editors, Mathematical Optimization Theory and Operations Research, pages 232{246, Cham, 2019. Springer International Publishing.