A Set Partitioning Problem

A set partitioning problem determines how the items in one set (S) can be partitioned into smaller subsets. All items in S must be contained in one and only one partition. Related problems are:

• set packing - all items must be contained in zero or one partitions;

• set covering - all items must be contained in at least one partition.

In this case study a wedding planner must determine guest seating allocations for a wedding. To model this problem the tables are modelled as the partitions and the guests invited to the wedding are modelled as the elements of S. The wedding planner wishes to maximise the total happiness of all of the tables.

A set partitioning problem may be modelled by explicitly enumerating each possible subset. Though this approach does become intractable for large numbers of items (without using column generation) it does have the advantage that the objective function co-efficients for the partitions can be non-linear expressions (like happiness) and still allow this problem to be solved using Linear Programming.

First we use allcombinations() to generate a list of all possible table seatings.

# create list of all possible tables
possible_tables = [tuple(c) for c in pulp.allcombinations(guests, max_table_size)]

Then we create a binary variable that will be 1 if the table will be in the solution, or zero otherwise.

# create a binary variable to state that a table setting is used
x = pulp.LpVariable.dicts(
    "table", possible_tables, lowBound=0, upBound=1, cat=pulp.LpInteger
)

We create the LpProblem and then make the objective function. Note that happiness function used in this script would be difficult to model in any other way.

seating_model = pulp.LpProblem("Wedding Seating Model", pulp.LpMinimize)

seating_model += pulp.lpSum([happiness(table) * x[table] for table in possible_tables])

We specify the total number of tables allowed in the solution.

# specify the maximum number of tables
seating_model += (
    pulp.lpSum([x[table] for table in possible_tables]) <= max_tables,
    "Maximum_number_of_tables",
)

This set of constraints defines the set partitioning problem by guaranteeing that a guest is allocated to exactly one table.

# A guest must seated at one and only one table
for guest in guests:
    seating_model += (
        pulp.lpSum([x[table] for table in possible_tables if guest in table]) == 1,
        f"Must_seat_{guest}",
    )

The full file can be found here wedding.py

"""
A set partitioning model of a wedding seating problem

Authors: Stuart Mitchell 2009
"""

import pulp

max_tables = 5
max_table_size = 4
guests = "A B C D E F G I J K L M N O P Q R".split()


def happiness(table):
    """
    Find the happiness of the table
    - by calculating the maximum distance between the letters
    """
    return abs(ord(table[0]) - ord(table[-1]))


# create list of all possible tables
possible_tables = [tuple(c) for c in pulp.allcombinations(guests, max_table_size)]

# create a binary variable to state that a table setting is used
x = pulp.LpVariable.dicts(
    "table", possible_tables, lowBound=0, upBound=1, cat=pulp.LpInteger
)

seating_model = pulp.LpProblem("Wedding Seating Model", pulp.LpMinimize)

seating_model += pulp.lpSum([happiness(table) * x[table] for table in possible_tables])

# specify the maximum number of tables
seating_model += (
    pulp.lpSum([x[table] for table in possible_tables]) <= max_tables,
    "Maximum_number_of_tables",
)

# A guest must seated at one and only one table
for guest in guests:
    seating_model += (
        pulp.lpSum([x[table] for table in possible_tables if guest in table]) == 1,
        f"Must_seat_{guest}",
    )

seating_model.solve()

print(f"The chosen tables are out of a total of {len(possible_tables)}:")
for table in possible_tables:
    if x[table].value() == 1.0:
        print(table)