key: cord-0527371-x9a9hs59
authors: Blom, Danny; Pendavingh, Rudi; Spieksma, Frits C.R.
title: Filling a theatre in times of corona
date: 2020-09-30
journal: nan
DOI: nan
sha: afcddd3d140ca645ae54cb47bda21968986da7c6
doc_id: 527371
cord_uid: x9a9hs59

In this paper, we introduce an optimization problem posed by the Music Building Eindhoven (MBE) to deal with the economical consequences of the COVID-19 pandemic for theatre halls. We propose a model for maximizing the number of guests in a theatre hall that respects social distancing rules, and is based on trapezoid packings. Computational results show that up to 40% of the normal capacity can be used for a single show setting, and up to 70% in case artists opt for two consecutive performances per evening.

Article submitted to INFORMS Journal on Applied Analytics; manuscript no. (Please, provide the manuscript number!) Clearly, these rules have a dramatic impact on the operation of any theatre, and despite governmental efforts theatres are struggling to survive. As a consequence, many employees in this sector risk losing their jobs.

Indeed, for many theatres, the challenge is to find a way to welcome their guests while satisfying the distance rules, and still be commercially viable. Many creative efforts have resulted in a number of ideas that are being experimented with (see, for example, the use of a so-called nebulizer device, see [Berliner Ensemble (2020)] ). Here, we focus on the question to what extent large audiences can still be accommodated in a theatre when distance rules must be satisfied. We describe a mathematical model that, given the layout of the seats in a theatre and the distribution of the demand, computes a safe seating arrangement that attains the maximum occupation of the theatre.

The Music Building Eindhoven (MBE), located in the city of Eindhoven in the Netherlands, features a "Grand Room" (1250 seats) and a "Small Room" (400 seats). This theatre has served as a motivation for this study, and all our computational efforts are based on its two rooms. Our findings have been implemented by the MBE, allowing them to remain open.

In Section 2 we give a precise problem description, and in Section 3 we phrase the problem in terms of packing of trapezoids. In Section 4 we give our model, and in Section 5 we show solutions of the model on instances coming from the MBE. Upper bounds are discussed in Section 6, and we conclude in Section 7.

Here, we describe the crucial ingredients of our problem. Seats, distances and forbidden zones are discussed in Section 2.1, and target profiles are explained in Section 2.2. This allows us to arrive at a problem statement given in Section 2.3.

When a theatre wants to offer a corona-proof experience to its customers, a few constraints need to be taken into account. Obviously, safety is of utmost importance and therefore, the subset of seats that could be used for reservations needs to be chosen according to the guidelines provided by the government. We realize that these guidelines vary for different countries. However, a common denominator between different countries is that members of distinct families (or bubbles) should keep a prespecified distance from each other to prevent Blom, Pendavingh, and Spieksma : Filling a theatre in times of corona Article submitted to INFORMS Journal on Applied Analytics; manuscript no. (Please, provide the manuscript number!) 3 the spread of the COVID-19 virus. In the Netherlands, two people should be seated at least 1.5 meter apart (unless they are members from the same household), as established by the Dutch Government [The Netherlands (2020) ]. Figure 1 shows a sketch of four consecutive seats, viewed from the front and from above, and the corresponding interseat distances of seats in the MBE. Due to the exception of the distance rules for family members, another relevant factor is the size t ∈ T of a family, with T ⊂ Z + the set of allowed family sizes. In particular, we will call a family of size 1 a singleton, of size 2 a pair, of size 3 a triple, and a family of size 4 a quad. Guests from the same household are allowed to sit next to each other, within the 1.5m bound; in fact, we assume that a family of size t occupies t consecutive seats. Based on the distances in Figure 1 , it follows that whenever a certain seat is occupied, there is a "ring" of seats around it that are forbidden for use by a member of another family. The forbidden ring corresponding to a pair is depicted in red in Figure 2 .

Consider a theatre, and let S denote the set of seats of the theatre. Each seat is specified by its row r, and its position s in row r. Formally, a seat is a pair of integers (r, s) ∈ Z × Z and the set of seats is a collection S ⊆ Z × Z. Typically, the seats in each row are numbered starting with s = 1, 2, 3, . . ., so that the relative position of the seats (r, s) and (r , s) will depend on where rows r and r start. For the description of our model it will be convenient to assume that the seats in each row are numbered such that for each s ∈ Z, the seats {(r, s) ∈ S : r ∈ Z} are in a straight line. Figure 2 also illustrates this convention for {(r, 3) ∈ S : r ∈ Z}. Blom, Pendavingh, Again, in a typical theatre (such as MBE), consecutive rows are shifted relative to each other (for reasons of visibility), so that the four seats (r + 1, s − 1), (r + 1, s), (r − 1, s), (r − 1, s + 1) form the corners of a rectangle with center (r, s). This seat renumbering method is illustrated in Figure 2 for (r, s) = (3, 3).

When we denote the distance between the centers of adjacent seats in a row by a, and the spacing of consecutive rows is denoted by b, then the distance between the centers of seats (r, s) and (r , s ) is

Assuming that members of different families may not be seated within distance c, the 'forbidden zone' for members of other families surrounding a person in seat (0, 0) is

Taking distances a = 0.51m and b = 0.95m as in Figure 1 , and a forbidden distance of c = 1.5m, a calculation reveals that F is a collection of 13 seats: the occupied seat itself, two seats on each side in in the same row, and four nearby seats in each adjacent row. In general, the forbidden zone for a family of size t consists of 13 + 2(t − 1) = 2t + 11 seats.

In Figure 2 , we indeed see that the forbidden zone of a pair consists of 15 seats, as there is an extra forbidden seat in both adjacent rows. Members of the same family are allowed to be in each other's forbidden zone, but the union of their forbidden zones is forbidden for members of other families. A family of size t located at (r, s) will occupy the seats S r,s,t := {(r, s + i) : i = 0, . . . , t − 1)} and will have a forbidden zone F r,s,t := S r,s,t + F = {(r + r , s + s + i) : i = 0, . . . , t − 1, (r , s ) ∈ F}.

(Notice that we use the Minkowski sum when adding two sets A and B, i.e.

indicates a possible location of a family of size t at (r, s), i.e. if S r,s,t ⊆ S for each (r, s, t) ∈ A and S r,s,t ∩ S r ,s ,t = ∅ for each distinct pair (r, s, t), (r , s , t ) ∈ A.

Thus, a seating arrangement A is safe if no member of a family is in the forbidden zone of another family.

For any seating arrangement A, let n t (A) := |{(r, s, t) ∈ A : (r, s) ∈ S}| capture the number of families of size t in A, t ∈ T .

Definition 2. The size of a seating arrangement A is t∈T t · n t (A).

Thus, the size of a seating arrangement corresponds to the number of customers present.

Apart from providing a safe environment for the audience while enjoying a performance, a theatre needs to consider its booking strategy. In general, multiple factors play a role when deciding upon such a strategy (see Baldin and Bille [Baldin and Bille (2018) ], and the references contained therein). One option is to sell the individual seats (perhaps after segmentation into classes) chosen by customers in a first-come first-serve manner. The risk of such a strategy is that customers choose seats that do not lead to a maximum occupancy.

Another option is to simply sell tickets, and only reveal very shortly before the start of the performance which particular seats are assigned to which individual customers. This allows the theatre flexibility to find a maximum occupancy, yet customers might find it unattractive not to be able to choose their specific seats. Without going into details of Blom, Pendavingh, the various considerations, we have opted, in collaboration with the MBE for a policy that (i) allows customers to choose their seats, and (ii) uses a so-called target profile to take the size of families visiting the performance into account. Indeed, prior information on the distribution of the customers over singletons, pairs, triples and quads is valuable information and can serve as a proxy for customer behaviour.

Definition 3. A target profile for a seating arrangement A is a vector p = (p t ) t∈T ∈

[0, 1] T such that t∈T p t = 1.

Each entry p t indicates a targeted proportion of the reservations corresponding to families of size t, i.e. we aim for a seating arrangement A for which

A target profile can be determined through statistical analysis or machine learning models applied on historical data. We show in Section 2.3 how we formalize this aim.

When we use the target profile to proxy customer behaviour as input, we can describe the problem in the following way:

Problem: MAXIMUM PROFILED SEATING ARRANGEMENT Instance: a tuple (S, T, p, ) consisting of a set of seats S ⊆ Z × Z, a set of allowed family sizes T ⊂ N + , a target profile p = (p t ) t∈T and ∈ (0, 1].

Goal: Find a safe seating arrangement A of maximum size such that the following conditions hold:

Notice that there is no unique way to model a condition as provided in Equation (1).

One alternative is to consider strict lower bounds on the number n t (A) of families of size t.

Furthermore, is used as a multiplicative threshold parameter, but one could also use it as an additional parameter instead. In the following section, we describe a nontrivial connection between finding a safe seating arrangement and the problem of packing a maximum weight set of trapezoids. 

We describe in Section 3.1 a nontrivial connection between finding a safe seating arrangement and the problem of packing a maximum number of trapezoids in a polygonal shape, and in Section 3.2 we prove a bound on the number of families that fit in a theatre. In Section 3.3 we analyze, as an intermezzo, a theatre with an infinite number of rows having each an infinite number of seats, and in Section 3.4 we discuss the occupation density of seating arrangements in large theatres.

Given the structure of the forbidden zone F, we are able to formulate a model based on

trapezoids. The trapezoid based at (0, 0) is the collection of seats

The trapezoid based at (r, s) then is

and the trapezoid of a family of size t located at (r, s) is

The trapezoid T3,4,2 together with its associated forbidden zone F3,4,2 (given by red and green seats).

The trapezoid T is chosen so that

where

This key property will allow us to show: 

{T r,s,t : (r, s, t) ∈ A} is a collection of pairwise disjoint trapezoids.

Theorem 1 forms the basis of the integer programming models in Section 4, which solve the main problem of this paper for the MBE, and which in principle apply to theatres S of any given shape or irregular form. Theorem 1 also enables us to analyse, in the remainder of this section, the limiting behaviour of optimal arrangements for large 'square' theatres.

The proof of Theorem 1 takes the form of 2 lemma's.

so that T r,s ∩ T r ,s = ∅, as required.

1} so that (r, s + i) ∈ F r ,s +i . By the previous lemma, this is equivalent to

In turn, this is equivalent to T r,s,t ∩ T r ,s ,t = ∅.

By this lemma, we may replace the asymmetrical condition S r,s,t ∩ F r ,s ,t = ∅ in the definition of a safe arrangement by the equivalent symmetrical condition T r,s,t ∩ T r ,s ,t = ∅.

This proves Theorem 1. 

Under normal circumstances, it is clear how guests of a theatre use the available resources: each guest needs one seat. With social distancing rules, it is not immediately clear to what extent guests claim the resources. There will be many empty seats in any safe seating arrangement, and it is not obvious which guest to blame or charge. Theorem 1 is helpful in this sense, as it makes clear that each family with t members at (r, s) blocks the seats T r,s,t ∩ S, and so is responsible at least for the emptiness of these seats. If (r, s) is sufficiently far away from the boundary of the theatre, so that T r,s,t ⊆ S, this amounts to blocking |T r,s,t | = 2t + 3 seats. Ignoring the boundary effect, this gives a rough upper bound on the number of families of size t that can fit the theatre safely: |S|/(2t + 3).

The following consequence of Theorem 1 describes how we may take the boundary of a collection of seats S into account when estimating the capacity of a theatre.

Theorem 2. Let A be a safe seating arrangement in S. We have:

Proof. For each (r, s, t) ∈ A, the family of size t which is located at (r, s) will occupy the seats S r,s,t ⊆ S and hence for the corresponding trapezoid we have T r,s,t = S r,s,t + T ⊆ S + T .

By Theorem 1, each seat of S + T is in at most one of trapezoids {T r,s,t : (r, s, t) ∈ A}, and hence

as required.

Note that the set (S + T ) \ S consists of a rim of seats adjacent to the boundary of S in

For large theatres with a relatively simple boundary, the collection S + T of the theorem is only marginally larger than S. For example, let S k be a block of k rows of k seats each, then |S k | = k 2 and |S k + T | ≤ (k + 1)(k + 2). Then as k → ∞.

We analyse the limiting case of this sequence in Section 3.3, and then we return to safe arrangements in large theatres S k in Section 3.4. Though the square theatre S k is perhaps artificial, very large venues such as sport stadiums are sufficiently similar to merit comparison. 

Inspired by the famous thought experiment of Hilbert on the concept of infinity, the Hilbert theatre has seats S ∞ = Z × Z: it is an infinite sea of regularly spaced seats.

For each family size t, the seating arrangement

is such that the corresponding collection of trapezoids {T r,s,t : (r, s, t) ∈ A t } covers each seat in S ∞ exactly once. The safe seating arrangement A 2 in the Hilbert theatre.

Hence A t is a safe seating arrangement, and the average density of occupied seats in A t equals the proportion of occupied seats within each trapezoid

We cannot hope to attain a better density than d t in any arrangement with families of size t. This shows that in the Hilbert theatre, the maximum density when packing families of size t is d t ; notice that this value increases with t and will never exceed 1 2 . The following table shows the density d t and its reciprocal 1/d t for small family sizes t. t 1 2 3 4 5 6 · · · ∞ d t 0.20 0.29 0.33 0.36 0.38 0.4 · · · 0.5 1/d t 5 3.5 3 2.75 2.6 2.5 · · · 2

As the table shows, the minimum use of seats per family member (1/d t ) decreases steeply in this initial range.

Finite theatres tend to approximate the Hilbert theatre as they become larger. For a seating arrangement A in a finite theatre S, we formally define the occupation density as In our square theatre S k , there is a seating arrangement of families of size t which arises by restricting A t to the locations available in S k :

Then each row of S k will see at least k 2t+3 families in A t,k , and hence A t,k attains an overall density of occupied seats of at least

Evidently, this lower bound on the density tends to d t as k → ∞.

For an upper bound on the occupation density of any arrangement A in S k consisting families of size t only, we may bound the number n t of families in A by applying Theorem 1.

This gives

Since each family has t members and the total number of seats in S k is k 2 , we obtain an upper bound on the occupation density of

So the occupation density of such A may marginally exceed the density d t of A t for low values of k, but the upper bound tends to d t as k → ∞. In particular, we find that the Moreover, for any p : N → R + such that t p t = 1, there exists a sequence of arrangements

We omit the proof, noting that it is a straightforward extension of the argumentation above. Let us analyze the densities d t that can be obtained for such special seating arrangements for a fixed t. Since A will have k/2 occupied rows, we have

as k → ∞, where d t := t/(2t + 4). This is worse than d t = t/(2t + 3), but not by much.

To assess the loss of density when using these special seating arrangements, we include a Remark on a shorter safe distance The above analysis can be straightforwardly adapted to a safe distance of 1 meter. Then the forbidden zone becomes There are safe seating arrangements in the Hilbert theatre that attain this density, and Theorem 3 remains valid. For suboptimal seating arrangements with empty rows between occupied rows, we obtain the densities d t = t 2t+2 . We have so far used our model to investigate a square and sufficiently large theatre S k . We will next explain how our model yields a computational strategy to find optimal packings for any specific theatre.

We describe our model in Section 4.1, and in Section 4.2 we show how the concept of multiple shows can be embedded in the model. In Section 4.3 we indicate how we speed up the solution process of the model.

With any collection A ⊆ S × T , where T ⊆ N + is a finite collection of allowed family sizes, we can associate a characteristic vector y ∈ {0, 1} S×T with y r,s,t = 1 if and only if (r, s, t) ∈ A.

Then A is a seating arrangement in S if and only if y r,s,t = 0 whenever S r,s,t ⊆ S.

This seating arrangement A is safe if and only if (r ,s ,t ):T r ,s ,t (r,s) y r ,s ,t ≤ 1, for all (r, s) ∈ S + T .

From a geometric point of view, constraints (4) ensure that each seat (r, s) ∈ S + T is covered by at most one of the trapezoids it is contained in. Finally, A accommodates n t families of each size t ∈ T if (r,s):Sr,s,t⊆S y r,s,t = n t , for each t ∈ T.

Thus, the feasibility of a safe seating arrangement that simultaneously accommodates n t families of size t for t ∈ T translates to an integer linear feasibility problem in variables y r,s,t and n t . However, without a priori conditions on the number of families of each size t,

the optimal solutions of this problem will tend towards including many large families and few small families. This is intuitively clear, since a family of t together 'wastes' a trapezoid Blom, Pendavingh, 

of 2t + 3 seats, so that 2 + 3/t(= 1/d t ) seats are taken per person in a family of size t. In the extreme case that T includes large enough sizes to fill entire rows of seats with a single family, then a solution where the even rows are empty and each odd row is filled with a single family is feasible, and similar for leaving the odd rows empty and filling the even rows. One of these solutions then is optimal, and uses at least half of the seats in S. Indeed, now that we are letting our imagination roam free, we can fill the entire theatre with a single large enough family if we also let go of our restriction that families must be seated in the same row. To ensure that we find safe seating arrangements that approximately correspond to the typical sizes of families that book seats for a performance, we use the target profile, as introduced in Section 2.2. Recall from the problem statement that the target profile imposes the condition

In this way we obtain an integer linear program that maximizes the size of a seating arrangement over all safe seating arrangements in S: max t∈T tn t : (3), (4), (5), (6), y ∈ {0, 1} S×T , n ∈ Z T .

Notice that the LP relaxation of (7) gives an upper bound which, by the safety constraints (4), is informed that each family of size t occupies at least 2t + 3 seats from S + T .

Evaluated with = 0, the LP relaxation will be at least as good as the bound of Theorem 3.

One of the ideas that the MBE has implemented to remain commercially viable is to perform the same show during the same evening twice, each time for a different audience.

We refer to this phenomenon as consecutive shows. Clearly, this puts a burden on the performing artist(s); in many cases however, this is a realistic option. The MBE, however, is not able to clean the seats in between the shows. This creates an interdependence between the two seating arrangements for each individual show as each seat can be used at most once in each of the two seating arrangements. However, it is relatively straightforward to extend our model to find k consecutive seating arrangements A v for v ∈ V = {1, . . . , k}, k ∈ Z + , so that no seat is used in two different

To model the problem of finding such consecutive seating arrangements, we use binary variables y ∈ {0, 1} S×T ×V , and integer variables n ∈ Z T . The condition that each A v is a seating arrangement of S becomes y r,s,t,v = 0, whenever S r,s,t ⊆ S.

We also need to ensure that no seat is used more than once.

v∈V (r ,s ,t ):S r ,s ,t (r,s) y r ,s ,t ,v ≤ 1, for all (r, s) ∈ S.

Letting the n t count the overall number of families of size t is accomplished by writing v∈V (r,s)∈S y r,s,t,v = n t , for each t ∈ T.

The profiling condition (6) need not change at all.

Maximizing the number of guests in consecutive arrangements in S, whilst respecting a profile p ∈ R T up to a fixed > 0, is then modelled as the following ILP: max t∈T tn t : (6), (8), (9), (10), (11), y ∈ {0, 1} S×T ×V , n ∈ Z T .

This model is rather flexible: many additional wishes can be formulated. For instance, upper bounds on n t for some t ∈ T , or a balance between the distribution in different shows, or specific (monetary) weights to maximize the revenue that could be gained, seats can all be arranged through standard modifications of the integer linear program. 

For some instances of ILP formulation (12), the corresponding LP relaxation leads to long running times of the solver. Hereunder we propose two methods that ameliorate solver performance, namely (i) adding a class of valid inequalities to strengthen the LP relaxation and (ii) using a symmetry breaking method for formulation (12).

The ILP formulations (7) and (12) only take into account for each individual seat (r, s) ∈ S the trapezoids T r ,s ,t that contain (r, s). Using the adjacency of seats, Lemma 3 finds a set of new valid inequalities.

Lemma 3. Let (r, s) ∈ S such that X = {(r, s), (r + 1, s − 1), (r + 1, s)} ⊆ S. Then, for each t ∈ T :

(r,s,t):|Tr,s,t∩X|≥2

Notice that X consists of three seats. Thus, from all trapezoids that contain at least two seats from X, one can select at most one.

To show that inequalities (13) it. Each of these four dark grey seats is contained in at most three trapezoids. so the LP solution with each of the four trapezoids chosen with 1/3 is feasible for (7), with value 4/3.

However, a safe seating arrangement A can clearly contain at most one seat.

A valid inequality for this example is y1,1,1 + y1,2,1 + y2,1,1 + y2,2,1 + y2,3,1 ≤ 1. It separates the previously feasible LP solution ( 1 3 , 1 3 , 1 3 , 0, 1 3 ).

The presence of symmetry in a ( many equivalent problems need to be solved in the branch-and-bound procedure to ensure optimality.

Consider now a sequence of consecutive safe seating arrangements (A v ) v∈V . Then, for an arbitrary permutation σ ∈ Sym(|V |), the sequence (A σ(v) ) v∈V is again feasible. The choice of permutations can even be done independently for each segment of the theatre,

i.e. the ground floor and its separate balconies. The following lemma provides a class of inequalities that drastically reduces the feasible region by removing symmetries caused by these permutation groups.

Proposition 1. Let a segment = 1, . . . , n in a theatre have a set of seats S ⊂ S. Let ≺ be the standard lexicographic ordering relation on S. For each (r , s ) ∈ S , v ∈ V , a class of symmetry breaking inequalities is

Suppose we are given a seat (r , s ) ∈ S , v ∈ V and v < v . The left hand side considers families of size t starting on seat (r , s ) for show v . The inequality tells us that we can only place at family starting at (r , s ) for show v whenever in an earlier show v < v a family was placed starting on some seat (r, s) ≺ (r , s ). Most importantly, we claim without proof that it is a correct symmetry breaking method.

Lemma 4. There exists an optimal solution to (12) that satisfies inequalities (14).

We implemented the models (7) and (12) above in Julia 1.3.0, using the modelling language JuMP to build the optimization model, with Gurobi as the lower level LP and MIP solver.

Experiments were run on a computer equipped with an Intel Core i7-7700HQ CPU @ 2.8

GHz with 32 GB of RAM. For our experiments we considered four different target profiles p = (p t ) t∈T , with T = {1, 2, 3, 4}, based on requests made by the MBE:

• Historical data on reservations: mge1 : p = (0.18, 0.7, 0.06, 0.06),

• Pairs only: mge2 : p = (0, 1, 0, 0),

• Singletons and pairs: mge3 : p = (0.2, 0.8, 0, 0),

• Pairs and quads: mge4 : p = (0, 0.5, 0, 0.5).

Blom, Pendavingh, and Spieksma: Filling a theatre in times of corona Article submitted to INFORMS Journal on Applied Analytics; manuscript no. (Please, provide the manuscript number!)

We solve the integer programming models in (7) and in (12) (6), as we empirically observe this choice for ε to give a suitable tradeoff between solver performance and solution structure with respect to target profiles. The same forbidden areas are considered for both theatre rooms, as the interseat distances coincide for both rooms. Additionally, we adapt the Gurobi parameters Symmetry, Cuts and Presolve to their aggressive settings. Table 1 and Table 2 provide the densities d(A( p)) for the Grand Room and the Small Room respectively, where A( p) is an optimal safe seating arrangement with respect to an indicated target profile p, both for the single show and double show case. Table 1 Densities d(A( p)) (in %) of maximum safe seating arrangements A( p) in the Grand Room, according to the target profiles. The reported numbers in the columns vanilla and speedup represent time in seconds (rounded to two decimal places). Table 2 Densities d(A( p)) (in %) of maximum safe seating arrangements A( p) in the Small Room, according to the target profiles. The reported numbers in the columns vanilla and speedup represent time in seconds (rounded to two decimal places). Let us first comment on the densities found in Tables 1 (Grand Room) rooms. Also, in case of a single show, the densities found are rather similar for the four different target profiles, with the exception of mge4. Target profile mge4 has a relatively large fraction of families of size 4 (the largest family size considered), which is beneficial for finding seating arrangements with a large density (see the discussion in Section 4.1). However, in case of a single show, all profiles allow a density of around 33% -this corresponds to a setting with 1/3 of the seats being occupied in a single show.

When analyzing the outcomes for a double show, we observe that the presence of large families (mge4) leads to better densities -this effect is more pronounced compared to a single show. Another interesting observation is that the densities almost double when compared to a single show. Hence, the effect of the constraint that a seat can be used at most once in two shows is negligible; in other words, the model is able to find two single show seating arrangements with no seats in common such that the numbers of seats occupied in both shows is (almost) balanced. For the target profile based on historical data, mge1, the model is able to find seating arrangements that use almost 2/3 of the available seats. This is an important finding as it gives the MBE an idea of the consequences of having consecutive shows.

Let us now comment on the computation times. In particular, we see that adding a second show to the model drastically increases the computation time of the solver, which can probably be explained by the fact that additional symmetries are introduced in the problem by adding a second show and that the number of variables and constraints both increase linearly in |S|. Furthermore, the choice for the target profile also largely influences the running time of the algorithm. It is striking to see that the instances for which the algorithm has the worst performance are also the ones for which the target profiles are further away from intuitively optimal, i.e. relatively large proportions of small families and relatively small proportions of large families. For the instances on the Grand Room, we see that the impact of adding the speedup techniques is rather large. This can be explained by the fact that these instances have a rich variety of symmetries.

Recall that in Section 3.3, we analyzed a setting where in each show, seats in row r could be occupied by guests whenever row r − 1 and r + 1 (if existent) were empty, for any row r. show, all odd-numbered rows are used, and all even-numbered rows in the second. We only report computation times for the vanilla descriptions, as these speedup techniques now only yield redundant inequalities. The column called "Loss (%)" indicates the percentual loss of occupied seats, which can be seen as a proxy for the loss in revenue. Clearly, as the results in Tables 3 and 4 correspond to a more restricted setting of our problem, the realized densities are always smaller than those achieved for the setting where all rows can be used for all shows. Indeed, we observe that for all instances, especially the ones based on the Small Room, the percentual loss of occupied seats is rather significant, with no percentual loss smaller than 5.7% of occupied seats.

Computation times for this setting are much smaller. This is caused by the much smaller size of the resulting instances and much fewer dependencies between the variables.

The solutions that correspond to the occupancies for the target profile mge1 given in Tables 1 to 4 are provided in the appendices. We used the color red to indicate that those seats are forbidden for use by guests and the color green (and blue for two consecutive shows) to indicate seats that can be occupied by guests. 

In Table 5 , we list the number of seats |S| and the number of virtual seats (the "rim") |(S + T ) \ S|, in each of the two rooms of the MBE. By applying Theorems 2 and 3 to the rooms of the MBE, we can find upper bounds on the achievable occupancy. We consider these volume bounds on the realized safe seating arrangements A max corresponding to the data in Table 1 and Table 2 on the single show setting, for the Grand Room and the Small Room respectively. The following table provides the left hand sides on these volume bounds to illustrate the strength of these bounds. Recall the right hand sides for the Grand Room (1708) and Small Room (533). The interpretation of the numbers depicted in Table 6 is the number of seats in S + T that are covered by the corresponding trapezoid packing. We observe that approximately 75 to 85 % of (virtual) seats are covered Blom, Pendavingh, and Spieksma: Filling a theatre in times of corona Article submitted to INFORMS Journal on Applied Analytics; manuscript no. (Please, provide the manuscript number!) 23 by a trapezoid. The gap on the volume bound can be explained by the fact that the trapezoid forms do not allow for a perfect packing of seats, and this effect is amplified by the inclusion of target profiles, which further restrict the set of possible trapezoid packings.

Secondly, we consider the bound given by Theorem 3. Now, we consider the upper bound for occupation densities d(A( p)) of this bound corresponding to maximum safe seating arrangements in the model of (12). For convenience, we include the results on the realized occupation densities for the single show setting using all rows again in Table 7 . Table 7 Upper bounds on the occupation density d(A( p)) (in %), where A( p) is a maximum density safe seating arrangement satisfying target profile p, together with actually realized densities.

Occupation density UB d(A( p)) d(A( p)) (Grand Room) d(A( p)) (Small Room) We observe that the realized optimal densities are not very far away from the respective upper bounds in Table 7 . Nevertheless, the bound of Theorem 3 is based on perfect tilings of trapezoids of one family size in a suitable chosen theatre architecture, which is not the case for typical inputs. This is a possible explanation for the gap between the bound and the realized density

The 1.5 meter constraint has a huge impact on the occupancy when filling a theatre. In case of the MBE, when performing a single show on an evening, occupancy will not exceed 40% (both for the Grand Room and the Small Room). However, allowing two shows per evening, it is possible to reach an occupancy of 70% while satisfying the constraint that no seat is sold twice. A more logistically suitable solution is to use alternating empty rows, but this comes at the cost of losing at least 5% on the number of occupied seats. The corresponding solutions, together with other innovations, may offer some hope to theatres to remain competitive.

Appendix A: Solutions for mge1 (all rows)

The labels in the figures indicate the segments within the theatre rooms that are depicted. Appendix B: Solutions for mge1 (occupied rows are between two empty rows)

The labels in the figures indicate the segments within the theatre rooms that are depicted. 

Modelling preference heterogeneity for theatre tickets: a discrete choice modelling approach on Royal Danish Theatre booking data

Mixed-integer programming models for nesting problems

Polytopes associated with symmetry handling

Irregular packing problems: A review of mathematical models

How to Pack Trapezoids: Exact and Evolutionary Algorithms

Two-dimensional packing problems: A survey

State Data and Policy Actions to Address Coronavirus

Filling a theatre in times of corona Article submitted to