  We consider the problem of maximizing the number of people that a dining room
can accommodate provided that the chairs belonging to different tables are
socially distant. We introduce an optimization model that incorporates several
characteristics of the problem, namely: the type and size of surface of the
dining room, the shapes and sizes of the tables, the positions of the chairs,
the sitting sense of the customers, and the possibility of adding space
separators to increase the capacity. We propose a simple, yet general,
set-packing formulation for the problem. We investigate the efficiency of space
separators and the impact of considering the sitting sense of customers in the
room capacity. We also perform an algorithmic analysis of the model, and assess
its scalability to the problem size, the presence of (or lack thereof) room
separators, and the consideration of the sitting sense of customers. We also
propose two constructive heuristics capable of coping with large problem
instances otherwise intractable for the optimization model.
