Optimize event seat assignments with Corona restrictions

Question

Problem: Given a set of group registrations, each for a varying number of people (1-7), and a set of seating groups (immutable, at least 2m apart) varying from 1-4 seats, I'd like to find the optimal assignment of people groups to seating groups:

• People groups may be split among several seating groups (though preferably not)
• Seating groups may not be shared by different people groups
• (optional) the assignment should minimize the number of 'wasted' seats, i.e. maximize the number of seats in empty seating groups
• (ideally it should run from within a Google Apps script, so memory and computational complexity should be as small as possible)

First attempt: I'm interested in the decision problem (is it feasible?) as well as the optimization problem (see optional optimization function). I've modeled it as a SAT problem, but this does not find an optimal solution.

For this reason, I've tried to model it as an optimization problem. I'm thinking along the lines of a (remote) variation of multiple-knapsack, but I haven't been able to name it yet:

• items: seating groups (size -> weight)
• knapsacks: people groups (size -> container size)
• constraint: combined item weight >= container size
• optimization: minimize the number of items

As you can see, the constraint and optimization are inverted compared to the standard problem. So my question is: Am I on the right track here or would you go about it another way? If it's correct, does this optimization problem have a name?

Answer 1

You could approach this as an Integer Linear Programming Problem, defined as follows:

let P = the set of people groups, people group i consists of p_i people;
let T = the set of tables, table j has t_j places;
let x_ij be 1 if people from people group i are placed at table j, 0 otherwise
let M be a large penalty factor for empty seats
let N be a large penalty factor for splitting groups

     // # of free spaces = # unavailable - # occupied
     // every time a group uses more than one table,
     // a penalty of N * (#tables - 1) is incurred
min  M * [SUM_j(SUM_i[x_ij] * t_j) - SUM_i(p_i)] + N * SUM_i[(SUM_j(x_ij) - 1)]

     // at most one group per table
s.t. SUM_i(x_ij) <= 1 for all j

     // every group has enough seats
     SUM_j(x_ij * t_j) = p_i for all i

     0 <= x_ij <= 1

Although this minimises the number of empty seats, it does not minimise the number of tables used or maximise the number of groups admitted. If you'd like to do that, you could expand the objective function by adding a penalty for every group turned away.

---

ILPs are NP-hard, so without the right solvers, it might not be possible to make this run with Google Apps. I have no experience with that, so I'm afraid I can't help you. But there are some methods to reduce your search space.

One would be through something called column generation. Here, the problem is split into two parts. The complex master problem is your main research question, but instead of the entire solution space, it tries to find the optimum from different candidate assignments (or columns).

The goal is then to define a subproblem that recommends these new potential solutions that are then incorporated in the master problem. The power of a good subproblem is that it should be reducable to a simpler model, like Knapsack or Dijkstra.