1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
"""
A set partitioning model of a wedding seating problem
Adaptation where an initial solution is given to solvers: CPLEX_CMD, GUROBI_CMD, PULP_CBC_CMD
Authors: Stuart Mitchell 2009, Franco Peschiera 2019
"""
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,
"Must_seat_%s" % guest,
)
# I've taken the optimal solution from a previous solving. x is the variable dictionary.
solution = {
("M", "N"): 1.0,
("E", "F", "G"): 1.0,
("A", "B", "C", "D"): 1.0,
("I", "J", "K", "L"): 1.0,
("O", "P", "Q", "R"): 1.0,
}
for k, v in solution.items():
x[k].setInitialValue(v)
solver = pulp.PULP_CBC_CMD(msg=True, warmStart=True)
# solver = pulp.CPLEX_CMD(msg=True, warmStart=True)
# solver = pulp.GUROBI_CMD(msg=True, warmStart=True)
# solver = pulp.CPLEX_PY(msg=True, warmStart=True)
# solver = pulp.GUROBI(msg=True, warmStart=True)
seating_model.solve(solver)
print("The choosen tables are out of a total of %s:" % len(possible_tables))
for table in possible_tables:
if x[table].value() == 1.0:
print(table)
|
