# Python辅导 | ELEC-E7851 Computational User Interface Design 2019

这个Assignment是整数编程在HCI中的应用

1

ELEC-E7851 Computational User Interface Design 2019

Aalto University

Antti Oulasvirta, Niraj Dayama

Assignment 2: Applications of Integer Programming in HCI

General advice: There are two tasks in this assignment. Both are to be done using integer

programming. The first task is somewhat more challenging.

Preparations: Install Python, Gurobi (with academic licenses). You need Jupyter notebook

to read the class notes. You might want to use PyCharm for a consolidated installation.

Send questions about installation to the TAs. For queries on the assignment itself please

contact Niraj Dayama <niraj.dayama@aalto.fi>

A2.1 Arrangement of a Linear Menu by association (3 points)

Consider a typical linear menu as discussed during the lecture. However, this time we

do not have frequency values for commands. Instead, you have been provided data for

association values.

The association value Aij specifies the logical interrelation between two commands i

and j. For example, the command Save and the command Save-As are very closely interrelated and hence have association value 1. Similarly, Print and Page-Setup are

closely interrelated and hence have association value 0.9. On the contrary, commands

New and Help are almost unrelated and have the association value 0.

These association values Aij are known constants specified for all pairs of commands

in advance. Your task is to formulate the complete linear menu layout problem to find

positions for all commands. The objective function is to minimize the distance between

commands where the association is higher. In mathematical terms, if the association

between a pair of commands i and j is Aij and the distance between their positions

within menu is Dij , then your objective is to minimize (Aij times Dij) for all such pairs

of commands i and j

Hint: Use the decision variables and constraints same as the linear menu problem. Add a new

decision variable for the distance between any pair of commands. Correlate the distance decision variable to the location variable.

Reminder: You should attach both a report file (PDF) and any new Python file in the submission

file (ZIP).

Grading: One mark each for the following:

1. Reformulation of objective function via some weights

2. Constraint to compute the distance between any pair of commands

3. Working implementation in Python+Gurobi with objective function and results.

A2.2. Software Control Panel (5 points)

The following description explains subtasks 2.2.1, 2.2.2 and 2.2.3. The specific questions for tasks 2.2.1, 2.2.2 and 2.2.3 are provided after this description.

2

Common description: You are designing the control panel for a software application.

The panel consists of 16 different controllable widgets (buttons or other elements of

interaction). The control panel needs to be orthogonally arranged, so that widgets are

placed in a matrix of 4 rows and 4 columns. So, you need to decide which widget must

be placed at what location in the matrix.

Subtask 2.2.1: The primary consideration in placing the buttons in the matrix is the

time needed to reach (access) the widgets. This access-time depends on the distance of

the widget from the bottom left corner of the control panel. This is because the user’s

hands are assumed to be at the bottom left corner by default. The access-time required

is calculated by the position. For every individual widget, an importance parameter is

defined (based on frequency of usage of that widget). Formulate the widget layout problem in terms of an Integer Program. (Hint: Is this related to the menu-assignment

formulation?)

Subtask 2.2.2: In addition to the access time, you must address one more requirement:

Some specific pairs of buttons must necessarily be NOT be adjacent to each other in

the same row. This means that for some specific pair of buttons, if one of those buttons

is in a particular row, the second button should NOT be immediately next to that widget

immediately before or after the first button in same row. However, it is permissible to

keep them on same row as long as there is some other button between them. Re-formulate the layout problem to address this requirement.

Subtask 2.2.3: Consider that a pair of buttons is strictly prohibited from being immediate neighbors: neither in same row nor in same column. How do you need to modify

the formulation?

Reminder: You should attach both a report file (PDF) and any new Python file in the submission

file (ZIP).

You are designing a control panel

like this one. But your control panel

has 16 elements to be arranged in a

matrix of 4 rows X 4 columns

This point (bottom left corner) is considered as the starting point for calculating

access time.