## Tuesday, October 4, 2016

### Optimal Opera Seating: a MIP formulation

Here is an interesting problem that is somehow not so easy to model as a Mixed Integer Programming (MIP) problem:

So i have an opera houses with 10 rows and 10 columns of seats (Total :100). Each seat is allocated a preference value Aij. The preference value is halved if the group do not get seats in same row. Eg: If a reservation in opera house is for 5 people and only 2 can be accommodated in top row and 3 in next row, the preference value is actually halved for each seat. There are total of n reservations with 'n' > 100 seats. What will the best way to maximize the customer preference (n *Aij).If it can be done by linear programming, how should the equation look like.

Interior of Teatro de Romea in Murcia, Spain (link)

#### The data

I assume we have a set of groups $$g$$ and their sizes: $$size_g$$. A couple would be a group of size 2. Further use the rule that only complete groups can be seated (i.e. no partial groups).

The seats are organized as a grid $$(i,j)$$ where $$i$$ is the row and $$j$$ is the column. Each seat has a “preference value” $$a_{i,j}$$.

#### A simpler case: assignment

Let’s first ignore the difficulty about single or multiple row assignments. Without this complication we are essentially dealing with an assignment problem:

 \boxed{\begin{align}\max\>&\sum_{i,j,g} a_{i,j} x_{i,j,g}\\&\sum_g x_{i,j,g} \le 1 \>\>\forall i,j\\&\sum_{i,j} x_{i,j,g} = \mathit{place}_g \cdot \mathit{size}_g \>\>\forall g\\&x_{i,j,g} \in \{0,1\}\\&\mathit{place}_g \in \{0,1\}\end{align}}

Here $$x_{i,j,g}=1$$ if a member of group $$g$$ is seated in location $$(i,j)$$. The binary variable $$\mathit{place}_g$$ indicates whether we accommodate group $$g$$ (and thus seat all its members).

This model works both for the case where $$n=\sum_g \mathit{size}_g$$ exceeds the number of available seats or when $$n$$ is a smaller number.

This is quite easy. However using random $$a_{i,j}$$ we see groups scattered around the rows:

The numbers in each cell are the group IDs.

#### The tough case: penalize multiple row assignments

I am not sure if this is the best or even a good formulation. What I did is introduce a new index $$r = \{\text{OneRow},\text{MultipleRows}\}$$. Then my main variables are $$x_{i,j,g,r} \in \{0,1\}$$. Here is the complete model:

The parameter pref2 was populated as:

Admittedly: this model is not very straightforward and obvious. I am curious if there are better formulations.

The results look ok: there is a heavy preference for placing groups in the same row:

I would guess a constraint Programming (CP) approach may make it easier to model this problem.