Integer Programming for UI Design¶
Niraj Ramesh Dayama / Aalto University¶
This lecture provides a brief introduction to integer programming techniques. We will apply these techniques to formulate and solve some user interface design problems. The lecture assumes that the audience already has a general idea of UI optimization and also of basic optimization principles including heuristic techniques.
Content¶
1. Objective
2. Problem Formulation
3. The assignment problem
4. Variations of the assignment problem
5. Keyboard optimization
6. Branch and bound
Primary sources¶
1. Rao, S.R. Engineering Optimization: Theory and Practice. John Wiley & Sons, 2009.
2. George Nemhauser, Laurence Wolsey. Integer and Combinatorial Optimization. Wiley, 1998.
3. Andreas Karrenbauer and Antti Oulasvirta. 2014. Improvements to keyboard optimization with integer programming. In Proc. of the 27th annual ACM symposium on User interface software and technology (UIST ’14). ACM

Motivation — Representing decisions via numbers¶
Niraj Ramesh Dayama / Aalto University¶
The formal name of this technique is Mixed Integer (Linear) Programming but we shorten it to Integer Programming.
Why do we need to study this technique in the Computational User Interface Design course?
1. Systematic process to represent any situation
2. Commercial solvers available — You only need to tell your problem
3. Broad range of applications: Several classical problem representations available ready-made
4. Well-suited to HCI and UI Design
Examples:¶
1. Application interface (GUI)
2. Keyboard layout
3. Menus and toolbars
Introduction¶
Integer Programming is an exact method for solving optimization problems. It has been applied in many disciplines to solve all kind of different problems, such as:
• Deciding the best schedule for airline crews, lectures, or trains
• Finding the best location for depots, supermarkets, or firestations
• Planning the schedule to produce a product with different parts at different locations, including optimal transport
• Minimize waste in a production process, e.g. cutting fabric to make clothes
Many different areas make use of integer programming, from telecommunications to engineering, computer science, biology, economics, etc.
The goal of this lecture is to give you an introduction to Integer Programing, to convince you that it is a powerful tool also to solve problem in HCI, and to show you how to formulate and solve those problems.
Exact versus heuristic methods¶
Criterion
Exact methods
Heuristic methods
Solution
+ Guarantees to find the global optimum in finite time (but might be exponential)
+ Gives explicit optimality bounds for incumbent solutions
– may not give any reasonable solution within a given time
+ Can get some good solution quickly
– No notion of solution quality (bound)
– No guarantee to find the global optimum in finite time and might get stuck in local optimum
Performance and implementation
+ Fast solvers available (e.g. Gurobi, CPLEX)
+ Easy implementation once the model is decided
– Mathematical formulation of the problem may be hard and requires some practice
– Covering the full design space might be slow and unnecessary in certain cases
• Some implementations of common heuristics available (e.g. SciPy, Optimization Toolbox Matlab)
– Requires careful implementation of design space and tweaking of heuristics case by case
+ More flexibility when only some good solution is required
Flexibility in objectives
– Objective function may be hard or impossible to formulate in an efficient, closed mathematical form
– Limitations when trading-off different objectives
+ Objective function can be any data source or computable function (e.g. simulation model, crowdsourcing data, etc. )
+ Easier to compute pareto front for trading-off multiple objectives
– Flexibility comes at the cost of performance
Representation of feasible set
+ Rigorous constraints, clearly formulated
• Implementation of constraints can get confusing as problems become more complex
Exact methods give guarantees¶
Guarantees to find the global optimum¶
The simplest exact method is explicit enumeration, where the objective value of each element of the solution space is evaluated, and the current best solution — the so-called incumbent — is updated (basically brute-force).
In implicit enumeration relaxations are used to make the problem tractable. Relaxations are simplifications to a problem, obtained, for example by removing or simplifying constraints that make the problem easier to solve. Solving these simplified problems gives us a bound on the objective score of the original problem. This is used, for example, by the branch-and-bound method (discussed below) that uses these bounds to safely discard parts of the solution space.
Guarantees on the solution quality¶
The bounds obtained by the relaxation deliver us guarantees for the quality of the incumbent: no solution can be better than the bound and, thus if the objective value of the incumbent is only 1% away from the bound, we know that it can also be at most 1% away from the global optimum.
Powerful solvers available¶
such as Gurobi and CPLEX (IBM).
Here we will use Gurobi.
• Free for academic use
• Solves (Mixed Integer) Linear Programs, Quadratic Programs, and Quadratically Constrained Programs
• Interfaces for **Python**, C, C++, Java, .NET, MATLAB, R, and Excel
What is Integer Programing?¶
Recap: Design task and space¶
$$\mbox{Find } \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in \mathbf{X} \mbox{ which maximizes } f(\mathbf{x})$$
where
• $\mathbf{x}$ is an n-dimensional design vector, each dimension describing a design variable, and
• $\mathbf{X}$ is the set of designs (all to-be-considered design vectors).
Real variables are always allowed at any time. Howeer, Integer Programming allows us to restrict some variable to be integer (or boolean) and not real.¶
2. Formulating Problems¶
The formulation of the design problem is essentiel for exact methods, such as Integer Programming. In operations research, the problem formulation is called model. Formulating the model consists of three steps:
1. Define the decision variables and design space
2. Define constraints that characterize the set of feasible solutions
3. Define the objective function
Attention: the optimization model in this context should not be confused with behavioral models such as Fitts’ Law or other.
1. Decision variables¶
The design variables $\mathbf{x} = (x_1, \ldots x_n)$ are also called decision variables. We can consider the design process as a set of decisions, such as
• Is the button green, blue, or red?
• Does clicking the button provide auditory feedback or not?
• Should it be positioned on top of the form or below it?
All possible combinations of answers constitute the space of possible designs.
2. Constraints¶
Restrictions on the design variables that must be satisfied to produce an acceptable design. Constraints could be
• limitations inherent to the design problem (e.g. no entry in a menu should appear twice)
• functional or semantic (e.g. if an application offers the functionality “paste” it must also offer “copy”)
• user or customer pereferences (e.g. The companies logog must be place on the top right of the webpage)
• …
3. Objective function¶
Each decision is associated with a cost. The objective function (or evaluation function) consists of criteria that quantify the cost of a decision or design. The goal is then to find the design vector that minimizes the objective function. (Note: minimization = maximization)
Caveat: The objective function must be in closed mathematical form and only contain linear or quadratic terms
3. The assignment problem¶

Classical problem in combinatorial optimization. Similar to others, these are often inspired by real-life scenarios.
Given: a number N of agents and tasks
a cost $c_{ij}$ assigning agent i to task j
Task 1
Task 2
Task 3
Task 4
Agent 1
$c_{11}$
$c_{12}$
$c_{13}$
$c_{14}$
Agent 2
$c_{21}$
$c_{22}$
$c_{23}$
$c_{24}$
Agent 3
$c_{31}$
$c_{32}$
$c_{33}$
$c_{34}$
Agent 4
$c_{41}$
$c_{42}$
$c_{43}$
$c_{44}$
Goal: assign each task to exactly one agent so that the cost is minimized.
Warning: we will use a different metaphor here and then come back to HCI problems
1. Decision variables¶
Binary decision variables:

$\mathbf{x} = (x_{11},x_{12}, … x_{NN}), \quad x_{ij} \in \{0,1\}$
$x_{ij} = 1$ if agent i is assigned to task j, $0$ otherwise
Note: such decision variables can be represented as edges in a graph. Here we have the special case of a bipartite graph. This important property allows us to apply many concepts and algorithms from graph theory to solve our problems.
2. Constraints¶

Each task j must be assigned to exactly 1 agent: $$\sum_{i=1}^N x_{ij} = 1 \quad \forall j = 1 \cdots N$$
Each agent i must be assigned to exactly 1 task: $$\sum_{j=1}^N x_{ij} = 1 \quad \forall i = 1 \cdots N$$
3. Objective function¶

Minimize the costs for assigning agents to tasks
Example: 4 agents and 4 tasks
Cost for agent 1:
$$c_{11} x_{11} + c_{12} x_{12} + c_{13} x_{13} + c_{14} x_{14} = \sum_{j=1}^4 c_{1j} x_{1j} $$
Cost for the assignment:
$$\sum_{i=1}^N\sum_{j=1}^N c_{ij} x_{ij} = c_{11} x_{11} + c_{24} x_{24} + c_{33} x_{33} + c_{42} x_{42}$$
Objective function: $$min \sum_{i=1}^N\sum_{j=1}^N c_{ij} x_{ij} $$
The linear assignment problem:¶
$$min \sum_{i=1}^N\sum_{j=1}^N c_{ij} x_{ij} $$$$\text{subject to} \hspace{6cm} $$$$\sum_{i=1}^N x_{ij} = 1\hspace{1cm} \forall j = 1 .. N$$$$\sum_{j=1}^N x_{ij} = 1\hspace{1cm} \forall i = 1 .. N$$$$x_{ij} \in {0, 1} \hspace{1.6cm} \forall i, j = 1 .. N$$
The objective function and constraints contain only linear terms. Problems that can be modeled like this can be efficiently solved in polynomial time.
Note: The problem of assigning each agent to exactly one task, if the number of agents and tasks are the same, is the same as finding a matching in a bipartite graph . Formulating the problem like this allows us to make use of many standard algorithms that easily solve this problem in polynomial time.
Exercise 1: Assignment problems in HCI
Can you think of examples from HCI that involve an assignment problem?
Linear menu design¶
Consider again the example of designing a linear menu:
Aspect
Content
Design task
Given n menu items, decide their order to minimize expected selection time
Design space
All possible orderings of the items (n! in total)
Objective function
Minimize expected selection time
Task instance
Specification of elements and their relative importance
Solver
Gurobi solver for integer programming

Problem formulation: linear assignment problem¶
The cost $c_{ij}$ for assigning an item i to a position j is defined by the expected time to select the item: $c_{ij} = p_i \cdot d_j \cdot r$.
Thus the problem can be formulated as: $$min \sum_{i=1}^N\sum_{j=1}^N p_i \cdot d_j \cdot r \cdot x_{ij} $$ $$\text{subject to} \hspace{6cm} $$ $$\sum_{i=1}^N x_{ij} = 1\hspace{1cm} \forall j = 1 .. N$$ $$\sum_{j=1}^N x_{ij} = 1\hspace{1cm} \forall i = 1 .. N$$ $$x_{ij} \in {0, 1} \hspace{1.6cm} \forall i, j = 1 .. N$$
Gurobi implementation¶
The following code example shows how to implement and solve this model with the mathematical solver Gurobi:
1. Create the (empty) model
2. Define decision variables
3. Define constraints
4. Define objective function
5. Optimize model
6. Extract solution
In [3]:
We also need to define the particular task instance we want to solve including definition of elements, their ‘importance’ (frequency), and the available positions
In [4]:
In [5]:
In [6]:
Optimize a model with 18 rows, 81 columns and 162 nonzeros
Variable types: 0 continuous, 81 integer (81 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [8e-03, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 1.424
Presolve time: 0.00s
Presolved: 18 rows, 81 columns, 162 nonzeros
Variable types: 0 continuous, 81 integer (81 binary)
Root relaxation: objective 9.240000e-01, 38 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 0.9240000 0.92400 0.00% – 0s
Explored 0 nodes (38 simplex iterations) in 0.04 seconds
Thread count was 4 (of 4 available processors)
Solution count 2: 0.924 1.424
Pool objective bound 0.924
Optimal solution found (tolerance 1.00e-04)
Best objective 9.240000000000e-01, best bound 9.240000000000e-01, gap 0.0000%
Objective value (expected selection time): 0.924
Out[6]:
Quit
About
Insert
Open
Save
Edit
Close
Delete
Help
Gurobi Output explained:
Optimize a model with 18 rows, 81 columns and 162 nonzeros
Variable types: 0 continuous, 81 integer (81 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [8e-03, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Statistics about the to-be-solved problem: the number of constraints (rows), the decisions variables (columns) and properties about their values.
Found heuristic solution: objective 1.424
Presolve time: 0.01s
Presolved: 18 rows, 81 columns, 162 nonzeros
Variable types: 0 continuous, 81 integer (81 binary) Objective value of a solution find via heuristics, the time to simplify (presolve) the problem and updated statistic about the problem
Root relaxation: objective 9.240000e-01, 38 iterations, 0.00 seconds The objective value of the relaxed version of the original problem.
` Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
• 0 0 0 0.9240000 0.92400 0.00% – 0s` The number of explored and unexplored nodes in the enumerative tree, information about the current node, the objective value of the current incumbent solution, the best bound found so far, and the corresponding gap, The number of simplex iterations used per node to solve the realxation, and the time used so far for solving the problem
Explored 0 nodes (38 simplex iterations) in 0.05 seconds
Thread count was 4 (of 4 available processors) Information about the performance.
Solution count 2: 0.924 1.424
Pool objective bound 0.924 The objective values of the last X incumbent solutions and the best bound found for them.
Optimal solution found (tolerance 1.00e-04)
Best objective 9.240000000000e-01, best bound 9.240000000000e-01, gap 0.0000% If an optimal solution was found, the best objective value, best bound, and corresponding gap.
Model-data separation¶
Above, we have first implemented the model and then defined the concrete problem instance with elements, positions, and the corresponding cost factors.
A clean separation between the optimization model and the problem data (cost values, variables, etc.) is useful because:
• Makes it easy to switch between test data and a real system
• Allows to reuse optimization models for different instances
• Easily include data from different sources (database, files, generated, etc.)
• Good programing practice for more flexible and easier to understand code
Exercise 2: Trading off different users
Assume that you have two different user groups that use the menu in very different ways, e.g. novice versus expert users.
Given two sets of frequency distributions for the menu items, $p^{novice}$ and $p^{expert}$ your task is to reformulate the objective function so that it finds the best design for both user groups.
4. Variations of the linear assignment problem¶
The generalized assignment problem¶
Allows to model capacities for assigning several tasks to an agent:

Assigning an agent i to a task j has a profit $p_{ij}$ but also work cost $c_{ij}$
An agent i can work on multiple tasks but has a work capacity $t_i$
Goal: Assign each task to exactly one agent such that the profit is maximized and no agent works more than his capacity allows.
$$\color{red}{max} \sum_{i=1}^N\sum_{j=1}^M \color{red}{p_{ij}} x_{ij} $$$$\text{subject to} \hspace{6cm} $$$$\sum_{i=1}^N x_{ij} = 1 \hspace{1cm} \forall j = 1 \ldots M$$$$\color{red}{\sum_{j=1}^n c_{ij} x_{ij} \leq t_i \hspace{0.55cm} \forall i = 1 \ldots N}$$$$x_{ij} \in {0, 1} \hspace{1.6cm} \forall i = 1 .. N, j = 1 \ldots M$$
The quadratic assignment problem¶
Allows to model relationships between the elements of the two sets.

Scenario: we want to assign a number of factories to different locations in an optimal manner.
The difference to the linear assignment problem is that here the cost for assigning a factory to a location does also depend on its flow of good to other factories and the distance of that location to the locations of the other factories. If many goods are transported from one factory to another, they should be located close to each other.
Problem formulation¶
1. Decision varibales: $x_{ik} = 1$ if factory is i assigned to location k, $0$ otherwise.
2. Constraints:
At each location k there must be exactly one factory i : $$\sum_{i=1}^N x_{ik} = 1 \quad \forall k = 1 \cdots N$$ Each factory i must be assigned to exactly one location k: $$\sum_{k=1}^N x_{ik} = 1 \quad \forall i = 1 \cdots N$$

3 . Objective function:
In the example on the right, the cost for assigning factories 1 and 2 to locations 3 and 4 is: $$f_{12} \cdot d_{34} \cdot x_{13} \cdot x_{24}$$ To solve the optimization problem, we want to minimize this cost for all possible pairs of factories and locations. This is computed by: $$\color{red}{min \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=1}^n f_{ij} \cdot d_{kl} \cdot x_{ik} \cdot x_{jl}} $$
Thus, we can take into account relationships between elements of each set by simply changing the objective formulation. Overall, we get the following problem formulation:
$$\color{red}{min \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=1}^n f_{ij} \cdot d_{kl} \cdot x_{ik} \cdot x_{jl}}$$$$\text{subject to} \hspace{6cm} $$$$\sum_{i=1}^N x_{ij} = 1\hspace{1cm} \forall j = 1 .. N$$$$\sum_{j=1}^N x_{ij} = 1\hspace{1cm} \forall i = 1 .. N$$$$x_{ij} \in {0, 1} \hspace{1.6cm} \forall i, j = 1 .. N$$
The quadratic assignment problem in HCI¶
The quadratic assignment problem is useful if we want to model relationships between UI elements, for example with respect to:

• **User’s interaction**, e.g. the search button is often clicked after entering text in the search field
• **Functional, visual, or other similarity**, e.g. links to different supbages are placed in a row next to each other
• **Aesthetics or pleasure**, e.g. pictures are placed next to each other and vertically and horizontally aligned
• etc.
5. Keyboard optimization¶
The letter assignment problem¶

A prominent example of the quadratic assignmenr problem in HCI is the letter assignment problem:
Scenario: How should we place N characters on the keys of a keyboard so that we can type fastest?
For 26 letters and 26 keys there are $26! > 10^{25} $ different mappings, way to many to manually search and test for the best one.
Exercise 3a: Modeling the letter assignment problem
How can you model the problem of assigning characters to keyslots on a keyboard mathematically?
1. Define the decision variables
2. Add the necessary constraints
3. Formulate the objective function.
Exercise 3b: Implementing the letter assignment problem in Gurobi
Implement the model in Gurobi and optimize a keyboard layout for the given letters.
In [ ]:
In [ ]:
Bonus task:
We really want to name our keyboard the “HCI” keyboard.
Therefore, your task is to change the mathematical model and its implementation so that the letters H – C – I are placed next to each other on any of the rows of the computer, as in the example keyboard below. Do not change the input data.
How much worse is this keyboard in comparison to the unconstrained problem?
6. Branch and Bound¶
How is an Integer Program solved?¶
Mathematical solvers guarantee to find the global optimum. They can only do this by explicitly or implicitly evaluating every solution. In the following we are going to look at one method to do this in more detail: branch and bound
Linear versus Integer Program¶
In general, solving an integer program is hard, in the sense that it is computationally intensive. But, if we remove the integer constraint and allow the decison variables to take any real value, the problem becomes a linear program, which is much faster to solve for example with the simplex method. This linear problem is called relaxation.
Problem: there is no easy way to obtain the optimal integer solution from the optimal solution to the linear program.
The solution from the linear program only serves as a dual bound. In case of a maximization problem, this is also called upper bound: no integer solution can have a higher objective value than the solution to the linear program.
Any feasible solution is a primal bound or lower bound for maximization problems: the objective value of the optimal integer solution will be at least as good as the lower bound.

Example: $$max \hspace{0.3cm} x_1 + 0.64 x_2$$
$$\text{subject to} \hspace{4cm}$$$$\color{blue}{50 x_1 + 31 x_2 \leq 250}$$$$\color{red}{3 x_1 – 2 x_2 \geq -4}$$$$x_1, x_2 \in \mathbf{Z}^+ $$
Optimal value: $ 1.64 \leq z \leq 5.1$
Branch and bound¶
To solve the integer program, we iteratively compute tighter and tighter bounds by finding good approximate solutions, solving easier (linear) problems and refining the problem to make it easier to solve.
Branch and bound is one technique to do this. Basic idea for the binary integer program (e.g. keyboard optimization):
• Use an enumerative tree to go through all possible solutions
• At each node, divide the problem into easier subproblems by settting one of the decision variables either to 1 or 0 (*branch*)
• solve the subproblem to obtain a *primal bound* or solve a relaxation of the subproblem to obtain a *dual bound*
• use the bounds to exclude subsets of the solution space that cannot lead to an optimal solution (*prune*).
There are 3 ways of pruning:
•
• Pruning by infeasibility: the subproblem violates one or more constraints
• Pruning by optimality: the subproblem has been solved to optimality but the dual bound of another subproblem is better
• Pruning by bound: the dual bound is worse than the primal bound of another subproblem

•