"""
A formulation in original variables of a wedding seating problem
Authors: Stuart Mitchell 2010
"""
from time import time
import coinor.pulp as pulp
import coinor.dippy as dippy
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(guest_a, guest_b):
"""
Return the happiness (0 is the best) of allocating two
guests together in the same table
"""
return abs(ord(guest_a) - ord(guest_b))
#create the set of possible tables
tables = range(max_tables)
possible_seatings = [(g, t) for g in guests
for t in tables]
#create a binary variable to model if a guest sits at a particular table
x = pulp.LpVariable.dicts('possible_seatings', possible_seatings,
lowBound = 0,
upBound = 1,
cat = pulp.LpInteger)
seating_model = dippy.DipProblem("Wedding Seating Model (DIP)", pulp.LpMinimize)
#specify the maximum number of guests per table
for table in tables:
seating_model.relaxation[table] += sum([x[(guest, table)]
for guest in guests]) <= \
max_table_size, \
"Maximum_table_size_%s"%table
#A guest must seated at one and only one table
for guest in guests:
seating_model += sum([x[(guest, table)] for table in tables]) == 1, "Must_seat_%s"%guest
#create a set of variables to model the objective function
possible_pairs = [(a, b) for a in guests for b in guests if ord(a) < ord(b)]
happy = pulp.LpVariable.dicts('table_happiness', tables,
lowBound = 0,
upBound = None,
cat = pulp.LpContinuous)
seating_model += sum([happy[table] for table in tables])
#create constraints for each possible pair
for table in tables:
for (a, b) in possible_pairs:
seating_model.relaxation[table] += \
happy[table] >= happiness(a, b) * (x[(a, table)] + x[(b, table)] - 1)
def relaxed_solver(prob, table, redCosts, convexDual):
"""
Generate columns (tables) with negative reduced costs
"""
dvs = []
neg_guests = [g for g in guests
if redCosts[x[(g,table)]] < 0.0]
neg_guests.sort()
# find all possible tables between two end points
for pos1, pos2 in [(i, j) for i in range(len(neg_guests))
for j in range(len(neg_guests))
if j > i]:
# find the suitable guests that can be included in between the end points
candidate_guests = [(redCosts[x[(g,table)]], g)
for g in neg_guests[pos1+1:pos2]]
candidate_guests.sort()
# pick the best guests (ie those with the negative reduced costs)
possible_table_inner = [g
for _, g in candidate_guests[:max_table_size-2]]
#This is the best table between the end points
possible_table = [neg_guests[pos1]] + possible_table_inner +\
[neg_guests[pos2]]
# calculate the sum of the reduced costs for each of the guests
neg_cost = sum(redCosts[x[(g, table)]] for g in possible_table)
table_happiness = happiness(possible_table[0], possible_table[-1])
rc = neg_cost + table_happiness * redCosts[happy[table]] - convexDual
if rc <= -0.000001:
var_values = [(x[(g, table)], 1)
for g in possible_table]
var_values.append((happy[table], table_happiness))
dv = dippy.DecompVar(var_values, rc, table_happiness)
dvs.append(dv)
return dvs
seating_model.relaxed_solver = relaxed_solver
seating_model.writeLP('wedding_main.lp')
for table in tables:
seating_model.writeRelaxed(table, 'wedding_relax%s.lp' % table);
dippy.Solve(seating_model, {
'doPriceCut' : '1',
'generateInitVars' : '1',
})
for table in tables:
print table,
for guest in guests:
if x[(guest,table)].value() >= 0.99:
print guest,
print happy[table].value()