Tuesday, January 15, 2019

Preferences for houses and neighbors

In [1] the following problem was posted:

• We have $$n$$ houses (denoted by index $$j$$)
• and $$m$$  tenants (using index $$i$$).
• Each tenant $$i$$ has a certain preference for a given house. The tenant can express this by providing three preferred houses: 1 for most preferred, and 2 for second most preferred and 3 for the third preferred house.
• Each tenant can also provide three preferred neighbors, using the same scheme: 1 for most preferred neighbor and 2 or 3 for less preferred.

Let's try to build a model for this.

Data

The first thing is I assume $$n\ge m$$: the number of houses exceeds the number of tenants.

To make the objective work, we need to decide what score to use when a house or neighbor is not preferred. We cannot just use zero for this, as 1 is most preferred. We can use the number 4, i.e.: 1 is most preferred, through 4: not preferred and then minimize the achieved score.

I like to use 0 as the default however. For this, I recode the preferences as 3 being the most preferred, and 0 being not preferred. Using zero as the default will lead to sparser models.

I generated some random data with 8 tenants and 10 houses:

----     40 PARAMETER hpref  preference for house, recoded, 3=first,2=second,1=third

house1      house2      house3      house4      house6      house7      house8      house9     house10

tenant1                       1                                   3                                   2
tenant2           1                                               2                                               3
tenant3                       1           3                                   2
tenant4                       1                                   2                                   3
tenant5                       2                       1           3
tenant6                                   1                       2                       3
tenant7           1           3                       2
tenant8                                   3                                   1           2

----     40 PARAMETER npref  preference for neighbor, recoded, 3=first,2=second,1=third

tenant1     tenant2     tenant3     tenant4     tenant5     tenant6     tenant7     tenant8

tenant1                       2           1                                               3
tenant2                                                           1                       3           2
tenant3                       3                       2                       1
tenant4                       1                                               2           3
tenant5                       1           3                                               2
tenant6           2                       3           1
tenant7                                   3                       2           1
tenant8           1                                               3           2


The parameter npref can be interpreted as: $\mathit{npref}_{i,i'} = \text{preference provided by tenant i for having tenant i' as neighbor}$ So each row should have three nonzero entries. This matrix is not symmetric. The benefit of having tenants $$i$$ and $$i'$$ as neighbors is $\mathit{npref}_{i,i'}+\mathit{npref}_{i',i}$ The matrix composed of values $$\mathit{npref}_{i,i'}+\mathit{npref}_{i',i}$$ is symmetric. I assume $$\mathit{npref}_{i,i}=0$$, i.e. the diagonal is zero.

In the following I will consider the preferences as a cardinal utility: we can add things up. Theoretically, the preferences may be more like an ordinal utility: only comparison is defined. I will sidestep this issue to make things easier for me.

Assignment

The main variables of the model are: $x_{i,j} = \begin{cases} 1 & \text{if tenant i is assigned to house j} \\ 0 & \text{otherwise}\end{cases}$ The assignment constraints can look like: \begin{align} & \sum_j x_{i,j} = 1 & \forall i \\ & \sum_i x_{i,j} \le 1 & \forall j \end{align} This will be the backbone of the model.

Housing preferences

The objective related to housing preferences is simple: $\max \> \sum_{i.j} \mathit{hpref}_{i,j} x_{i,j}$

Neighbor preferences

The objective that deals with preferences for neighbors, is more complicated. Let's assume all houses are in one long row. Then we can write: $\max \> \sum_{i,i',j} (\mathit{npref}_{i,i'}+\mathit{npref}_{i',i}) x_{i,j} x_{i',j+1}$ This is a quadratic objective. As we shall see later, it can be easily linearized.

Complete model

The complete model can look like:

\begin{align} \max \> & \color{DarkBlue} \lambda \color{DarkRed} f_1 + (1-\color{DarkBlue}\lambda) \color{DarkRed} f_2 \\ & \color{DarkRed} f_1 = \sum_{i.j} \color{DarkBlue}{ \mathit{hpref}}_{i,j} \color{DarkRed} x_{i,j} \\ & \color{DarkRed} f_2 = \sum_{i,i',j} \color{DarkBlue}{(\mathit{npref}}_{i,i'}+\color{DarkBlue}{\mathit{npref}}_{i',i}) \color{DarkRed}x_{i,j} \color{DarkRed}x_{i',j+1} \\ & \sum_j \color{DarkRed} x_{i,j} = 1 & \forall i \\ & \sum_i \color{DarkRed} x_{i,j} \le 1 & \forall j \\ & \color{DarkRed} x_{i,j} \in \{0,1\} \end{align}

Here $$\lambda\gt 0$$ is a weight. With $$\lambda = 0.8$$ (most weight on the housing preferences) I see as solution:

----     79 VARIABLE x.L  assignment

house2      house3      house4      house6      house7      house8      house9     house10

tenant1                                           1.000
tenant2                                                                                           1.000
tenant3                                                       1.000
tenant4                                                                               1.000
tenant5       1.000
tenant6                                                                   1.000
tenant7                               1.000
tenant8                   1.000

----     88 PARAMETER hpoints  preference points for house allocation

house2      house3      house4      house6      house7      house8      house9     house10

tenant1                                           3.000
tenant2                                                                                           3.000
tenant3                                                       2.000
tenant4                                                                               3.000
tenant5       2.000
tenant6                                                                   3.000
tenant7                               2.000
tenant8                   3.000

----     88 PARAMETER npoints  preference points for neighbors

tenant2     tenant3     tenant4     tenant6     tenant8

tenant1                   1.000
tenant3                                           4.000
tenant4       1.000
tenant5                                                       3.000
tenant6                               3.000


We can see that tenant3 and tenant6 are neigbors (house 7 and 8) and thus get 4 bonus points.

A solver like Cplex will be able to solve this model as given. There are some reformulations performed under the hood, as the problem as stated is actually non-convex.

Note: some other solvers will refuse this model as a quadratic equality constraint is non-convex. We can fix this by substituting out $$f_2$$. Other solvers will still refuse to solve the model after this reformulation: the Q matrix is not positive definite, while some other solvers recognize this can be linearized. Convex QP/MIQP solvers are not in agreement about what constitutes an acceptable model.

If the houses are not in a single row, the definition of a neighbor may be a bit more complicated. We can define the parameter $\vartheta_{j,j'} = \begin{cases} 1 & \text{if houses j and j' (with j'\gt j) are neighbors}\\ 0 & \text{otherwise}\end{cases}$ and use as objective: $\max \> \sum_{i,i',j,j'} (\mathit{npref}_{i,i'}+\mathit{npref}_{i',i}) \vartheta_{j,j'} x_{i,j} x_{i',j'}$ It is noted that we need to watch out for double counting. Hence $$\vartheta_{j,j'}= 0$$ for $$j'\le j$$.

Linearization

If you only have access to a MIP solver, this problem can be easily reformulated into a linear MIP model by observing that $$y_{i,i',j} = x_{i,j} x_{i',j+1}$$ can be linearized as: \begin{align} & y_{i,i',j} \le x_{i,j} \\ & y_{i,i',j} \le x_{i',j+1} \\ & y_{i,i',j} \ge x_{i,j} + x_{i',j+1} - 1 \\& y_{i,i',j} \in \{0,1\} \end{align} Plugging this into our model yields a linear model.

References

1. Optimization solution / algorithm for occupying tenants in houses (combinations), https://stackoverflow.com/questions/54146767/optimization-solution-algorithm-for-occupying-tenants-in-houses-combinations