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:
| Quadratic model |
|---|
| \[\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
- Optimization solution / algorithm for occupying tenants in houses (combinations), https://stackoverflow.com/questions/54146767/optimization-solution-algorithm-for-occupying-tenants-in-houses-combinations
No comments:
Post a Comment