Applied Optimization with Julia
University of Hamburg - Fall 2024
Question: What are the main issues for the organizers?
Important
Optimizing seating plans can help to maximize revenue while ensuring distancing rules and other constraints are met.
Question: What are these approaches in general and how do they relate to arena seating?
Question: What is an example for this approach?
Question: What is an example for this approach?
Question: What is an example for this approach?
Task: Fill the seating area given distancing regulations and venue-specific constraints.
Question: Any ideas on how to approach this?
Note
Idea behind the model was developed by Dr. Matthes Koch.
Task: Allocate as many high-value groups as possible.
| Grouptype | Req. Seats | Score | Available | Allocated | Value |
|---|---|---|---|---|---|
| a | 1 | 1 | 3 | ||
| b | 2 | 2 | 2 | ||
| c | 2 | 4 | 3 | ||
| d | 4 | 4 | 5 | ||
| e | 4 | 5 | 2 | ||
| f | 6 | 6 | 1 | ||
| g | 6 | 12 | 1 | ||
| Total |
You have 5 minutes to find a solution.
Question: What is your total score?
Question: What could be the sets?
Note
\(\mathcal{C}_r\) ensures that we only consider unblocked seats in each row.
Question: What could be possible parameters?
Our goal is to:
Maximize the group values by filling the seating area given distancing regulations between groups and venue-specific constraints.
Tip
Each group is represented by one binary variable. We don’t need to block each seat explicitly with a binary variable!
We need the following sets:
Question: What could be our decision variable?
Our main objective is to:
Maximize the group values by filling the seating area given distancing regulations between groups and venue-specific constraints.
Question: How again are groups allocated?
We need the following parameters and variables:
Question: What could be our objective function?
\[ \text{maximize} \quad \sum_{g \in \mathcal{G}} \sum_{r \in \mathcal{R}} \sum_{c\in \mathcal{C}_{g,r}} v_g \times X_{g,r,c} \]
Question: What constraints do we need?
The goal of this constraint is to:
Ensure that each group is allocated only once in the entire seating area.
We need the following:
Question: What could be the constraint?
\[ \sum_{r \in \mathcal{R}} \sum_{c \in \mathcal{C}_{g,r}} X_{g,r,c} \leq 1 \quad \forall g \in \mathcal{G} \]
Note
This “set packing” constraint ensures that a group is only assigned once.
The goal of this constraint is to:
Ensure that the number of groups in each row does not exceed the maximum allowed number of groups.
We need the following:
Question: What could be the constraint?
\[ \sum_{g\in \mathcal{G}}\sum_{c\in \mathcal{C}_{g,r}} X_{g,r,c} \leq p_{r} \quad r \in \mathcal{R} \]
Note
We want to place as many highly scoring groups as possible, but people need to move to buy drinks or use restroom. Depending on the venue, they should not cross other groups in the same row.
The last two
constraints are
somewhat tricky!
Tip
Assume one seat between groups must be kept empty. If one group takes seat 8, it uses seats 8 and 9. We thus cannot allocate another group of size 2 to seats 6, 7 or 8.
Question: Any ideas how to implement this?
The goal of this constraint is to:
Ensure that the horizontal social distance is maintained between groups.
We need the following:
As the constraint is based on a rather complex set, you don’t have to find it by yourself.
\[\sum_{g \in \mathcal{G}} \sum_{\tilde{c} \in \tilde{\mathcal{C}}_{c,g}} X_{g,r,\tilde{c}} \leq 1 \quad \forall r\in \mathcal{R}, c\in \mathcal{C}\]
Note
At first glance, this constraint looks rather easy, but it is not - it is based on the set \(\mathcal{C}_{c,g}\) not defined yet in the lecture.
\[\tilde{\mathcal{C}}_{c,g} = \{\tilde{c}\in \mathcal{C}| c - d_g + 1 - h \leq \tilde{c} \leq c \}\]
Remember:
Question: Can anybody explain the set?
\[\underbrace{X_{1,2,\textbf{6}}+X_{1,2,\textbf{7}}+X_{1,2,\textbf{8}}}_{g=1} + \underbrace{X_{2,2,\textbf{6}}+X_{2,2,\textbf{7}}+X_{2,2,\textbf{8}}}_{g=2} \leq 1 \quad (r=2,c=8)\]
\[\underbrace{X_{1,2,\textbf{6}}+X_{1,2,\textbf{7}}+X_{1,2,\textbf{8}}}_{g=1} + \underbrace{X_{2,2,\textbf{5}}+X_{2,2,\textbf{6}}+X_{2,2,\textbf{7}}+X_{2,2,\textbf{8}}}_{g=2} \leq 1 \quad (r=2,c=8)\]
\[ \underbrace{X_{1,2,\textbf{6}}+X_{1,2,\textbf{7}}+X_{1,2,\textbf{8}}}_{g=1} + \underbrace{X_{2,2,\textbf{6}}+X_{2,2,\textbf{7}}+X_{2,2,\textbf{8}}}_{g=2} + \underbrace{X_{3,2,\textbf{5}}+X_{3,2,\textbf{6}}+X_{3,2,\textbf{7}}+X_{3,2,\textbf{8}}}_{g=3} \leq 1 \quad (r=2,c=8) \]
Do you see
the pattern?
The goal of this constraint is to:
Ensure that the vertical social distance is maintained between groups.
We need the following:
Question: What could be the constraint?
Tip
It is an extension of the horizontal social distance constraint we used before, but now we block a rectangular area instead of a single row.
\[ \sum_{g \in \mathcal{G}} \sum_{\tilde{r} \in \mathcal{R}_r} \sum_{\tilde{c} \in \tilde{\mathcal{C}}_{cg}} X_{g\tilde{r}\tilde{c}} \leq 1 \quad \forall r\in \mathcal{R}, c\in \mathcal{C} \]
Question: What could be the set?
\[ \tilde{\mathcal{R}}_{r} = \{\tilde{r}\in \mathcal{R}| r-b \leq \tilde{r} \leq r \} \]
Note
Remember:
Let’s look at an example.
\[ \text{maximize} \quad \sum_{g \in \mathcal{G}} \sum_{r \in \mathcal{R}} \sum_{c\in \mathcal{C}_r} v_g \times X_{g,r,c} \] subject to: \[ \begin{align*} & \sum_{r \in \mathcal{R}}\sum_{c \in \mathcal{C}_r} X_{g,r,c} \leq 1 && \forall g \in \mathcal{G} \\ & \sum_{g \in \mathcal{G}}\sum_{c\in \mathcal{C}_r} X_{g,r,c} \leq p_r && \forall r \in \mathcal{R} \\ & \sum_{g \in \mathcal{G}} \sum_{\tilde{r} \in \tilde{\mathcal{R}}_{r}} \sum_{\tilde{c} \in \tilde{\mathcal{C}}_{c,g}} X_{g,\tilde{r},\tilde{c}} \leq 1 && \forall r\in \mathcal{R}, c\in \mathcal{C} \\ & X_{g,r,c} \in \{0,1\} && \forall g \in \mathcal{G}, \forall r\in \mathcal{R}, c\in \mathcal{C}_r \end{align*} \]
Questions: On model characteristics
Questions: On model assumptions
Important
Estimated additional revenue of 8,435 EUR for one match.
Similar studies have been conducted globally:
And that’s it for todays lecture!
We now have covered the arena seating problem based on a real-world application and are ready to start solving the corresponding tasks in the upcoming tutorial.
Questions?
For more interesting literature to learn more about Julia, take a look at the literature list of this course.
Lecture XI - Arena Seat Planning under Distancing Rules | Dr. Tobias Vlćek | Home
Social Distance Implementation