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: sizeg. 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” ai,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:
max∑i,j,gai,jxi,j,g∑gxi,j,g≤1∀i,j∑i,jxi,j,g=placeg⋅sizeg∀gxi,j,g∈{0,1}placeg∈{0,1} |
Here xi,j,g=1 if a member of group g is seated in location (i,j). The binary variable placeg indicates whether we accommodate group g (and thus seat all its members).
This model works both for the case where n=∑gsizeg exceeds the number of available seats or when n is a smaller number.
This is quite easy. However using random ai,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={OneRow,MultipleRows}. Then my main variables are xi,j,g,r∈{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.
No comments:
Post a Comment