The bartender's problem: grouping a list of orders into easy to handle small sets

Question

Suppose that a bartender gets the orders just before the party gets started. There are many people attending this party and every person can order only one time and up to three different beverages from a list of, say, 5 different beverages: 1, 2, 3, 4, and 5.

The bartender is looking at the list of all orders, which is a simple table with the customer's name and his order. Let us look at a possible fragment from the list:

1. Jack 1,2,3
2. Beth 1,3,5
3. Ben 5 (meaning that Ben orders just one drink for the whole evening)
4. Liz 1,2,4
5. John 2,3,4
6. Mary 2,5
7. Tom 1,2,3

Our bartender wishes to optimize his work and go home as fast as he can since when he finishes with the preparations of the drinks, there is no longer a need for him. The total number of orders is, say, 20. The maximum number of orders per tray is 3. So he thinks to himself the following: I am willing to group the orders in such a way that each tray will contain the most intersected items(beverages). For example here is a possible list of trays:

1. Orders 1,7 and 5,
2. orders 2,3 and 6,
3. order 4.

Aiming to group the list into sets of three elements each, containing up to nine maximally common beverages possible. How should he proceed?

Remark 1: The above scenario was developed with a friend seeking an optimal strategy or algorithm which resolves the bartender's objective.

Remark 2: One can consider an order as a 3-tuple. Ben's order number 5, will look like $(0,0,5)$. Then a perfect candidate for $(a_1,a_2,a_3)$ sharing a tray with $(b_1,b_2,b_3)$ will be in case where $a_i=b_i$ for $i=1,2,3$.

Remark 3: One can think of the orders as vertices in a complete weighted graph, where each wight describes a measure of numbers of matches, that is: (1,2,3) and (1,2,4) this measure takes the value 2 since only the first two coordinates are same. Then finding triangular with maximum weight on the edges.

Remark 4: I still have the feeling that this problem is not yet enough well-defined. So any relevant resource to this or similar problem would be very appreciated.

Remark 5: The numbers chosen in the above problem description are almost arbitrary, and serve to ease the presentation of the problem.

Thank you.

Answer 1

It seems a programming task . The concept starts with all-vs-all intersection sets n-by-n. The result must be ordered by set cardinality. It presents factorial complexity, so beware. The decrescent picking must avoid orders already considered.

Answer 2

You can solve this set partitioning problem via integer linear programming as follows. Let $O$ be the set of orders. For each subset $S \subset O$ of up to $3$ orders ($|S| \le 3$), let binary decision variable $x_S$ indicate whether that subset appears as a tray, and let $w_S$ be the weight of that subset. The problem is to maximize the total weight $\sum_S w_S x_S$ subject to $$\sum_{S:\ o \in S} x_S = 1 \quad \text{for $o\in O$} \tag1$$ Constraint $(1)$ forces each order to appear on exactly one tray.