# %%
from gurobipy import *
import json
import random
MEN = ["Herbert", "Christoph", "Martin", "Christian", "Marlon"]
WOMEN = ["Gaby", "Teresa", "Iris", "Anne-Christin", "Jenni", "Birgit", "Johanna"]
NAMES = MEN + WOMEN
PAIRS_2018 = [
("Martin", "Birgit"),
("Birgit", "Teresa"),
("Teresa", "Herbert"),
("Herbert", "Peter"),
("Peter", "Iris"),
("Iris", "Gaby"),
("Gaby", "Christoph"),
("Christoph", "Martin"),
("Christian", "Anne-Christin"),
("Anne-Christin", "Jenni"),
]
PAIRS_2019 = [
("Peter", "Herbert"),
("Herbert", "Gaby"),
("Gaby", "Christian"),
("Christian", "Renate"),
("Renate", "Anne-Christin"),
("Anne-Christin", "Martin"),
("Martin", "Iris"),
("Iris", "Teresa"),
("Teresa", "Jenni"),
("Jenni", "Christoph"),
("Christoph", "Birgit"),
("Birgit", "Peter"),
]
PAIRS_2021 = [
("Peter", "Teresa"),
("Teresa", "Christian"),
("Christian", "Birgit"),
("Birgit", "Jenni"),
("Jenni", "Iris"),
("Iris", "Herbert"),
("Herbert", "Martin"),
("Martin", "Christoph"),
("Christoph", "Gaby"),
("Gaby", "Anne-Christin"),
("Anne-Christin", "Peter"),
]
PAIRS_2022 = [
("Peter", "Christian"),
("Christian", "Herbert"),
("Herbert", "Anne-Christin"),
("Anne-Christin", "Birgit"),
("Birgit", "Iris"),
("Iris", "Christoph"),
("Christoph", "Teresa"),
("Teresa", "Gaby"),
("Gaby", "Martin"),
("Martin", "Jenni"),
("Jenni", "Peter"),
]
PAIRS_2022 = [
("Peter", "Christian"),
("Christian", "Herbert"),
("Herbert", "Anne-Christin"),
("Anne-Christin", "Birgit"),
("Birgit", "Iris"),
("Iris", "Christoph"),
("Christoph", "Teresa"),
("Teresa", "Gaby"),
("Gaby", "Martin"),
("Martin", "Jenni"),
("Jenni", "Peter"),
]
PAIRS_2023 = [
("Herbert", "Jenni"),
("Christoph", "Herbert"),
("Martin", "Johanna"),
("Christian", "Christoph"),
("Gaby", "Birgit"),
("Teresa", "Anne-Christin"),
("Iris", "Christian"),
("Anne-Christin", "Iris"),
("Jenni", "Gaby"),
("Birgit", "Martin"),
("Johanna", "Teresa"),
]
PAIRS_2024 = [
("Johanna", "Herbert"),
("Herbert", "Teresa"),
("Teresa", "Iris"),
("Iris", "Martin"),
("Martin", "Anne-Christin"),
("Anne-Christin", "Jenni"),
("Jenni", "Christoph"),
("Christoph", "Birgit"),
("Birgit", "Marlon"),
("Marlon", "Gaby"),
("Gaby", "Christian"),
("Christian", "Johanna"),
]
SEX_PAIRS = [
("Herbert", "Birgit"),
("Anne-Christin", "Christoph"),
("Christian", "Jenni"),
("Iris", "Jenni"),
("Iris", "Christian"),
# ("Teresa", "Martin"),
# ("Gaby", "Peter"),
("Johanna", "Christoph"),
("Johanna", "Anne-Christin"),
("Marlon", "Christoph"),
("Marlon", "Anne-Christin"),
("Marlon", "Johanna"),
]
# %%
m = Model("Silvester")
x = {}
y = {}
for i in NAMES:
for j in NAMES:
x[i, j] = m.addVar(vtype=GRB.BINARY)
if i == j:
x[i, j].ub = 0
sex_penalty = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2018 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2019 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2021 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2022 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2023 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2024 = m.addVar(vtype=GRB.CONTINUOUS)
old_penalty_2024_reverse = m.addVar(vtype=GRB.CONTINUOUS)
pair_penalty = m.addVar(vtype=GRB.CONTINUOUS)
m.update()
print("Finished Variable set-up")
# kein gegenseitiges Beschenken
m.addConstrs(x[i, j] + x[j, i] <= 1 for i in NAMES for j in NAMES)
# falls ein Teilnehmer im nächsten Jahr ausfällt
m.addConstrs(
x[i, j] + x[j, k] + x[k, i] <= 2 for i in NAMES for j in NAMES for k in NAMES
)
# add constraints
m.addConstr(
quicksum(x[p] + x[p[1], p[0]] for p in SEX_PAIRS if p[0] in NAMES and p[1] in NAMES)
<= pair_penalty
)
m.addConstr(
quicksum(x[i, j] for i in MEN for j in MEN)
+ quicksum(x[i, j] for i in WOMEN for j in WOMEN)
<= sex_penalty
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2018 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2018
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2019 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2019
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2021 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2021
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2022 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2022
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2023 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2023
)
m.addConstr(
quicksum(x[p[0], p[1]] for p in PAIRS_2024 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2024
)
# kein zurueckschenken
# m.addConstr(
# quicksum(x[p[1], p[0]] for p in PAIRS_2018 if p[0] in NAMES and p[1] in NAMES)
# <= old_penalty_2018
# )
# m.addConstr(
# quicksum(x[p[1], p[0]] for p in PAIRS_2019 if p[0] in NAMES and p[1] in NAMES)
# <= old_penalty_2019
# )
# m.addConstr(
# quicksum(x[p[1], p[0]] for p in PAIRS_2021 if p[0] in NAMES and p[1] in NAMES)
# <= old_penalty_2021
# )
# m.addConstr(
# quicksum(x[p[1], p[0]] for p in PAIRS_2022 if p[0] in NAMES and p[1] in NAMES)
# <= old_penalty_2022
# )
# m.addConstr(
# quicksum(x[p[1], p[0]] for p in PAIRS_2023 if p[0] in NAMES and p[1] in NAMES)
# <= old_penalty_2023
# )
m.addConstr(
quicksum(x[p[1], p[0]] for p in PAIRS_2024 if p[0] in NAMES and p[1] in NAMES)
<= old_penalty_2024_reverse
)
# m.addConstr(x['Teresa','Christoph'] == 0)
# MARLON
# allowed_names = ['Birgit', 'Gaby', 'Herbert']
# m.addConstr(quicksum(x["Johanna", name] for name in allowed_names) == 1)
# m.addConstr(quicksum(x["Marlon", name] for name in allowed_names) == 1)
for i in NAMES:
m.addConstr(quicksum(x[i, j] for j in NAMES) == 1)
m.addConstr(quicksum(x[j, i] for j in NAMES) == 1)
# Set objective
m.modelSense = GRB.MINIMIZE
m.setObjective(
0.01 * quicksum(random.uniform(0, 1) * x[key] for key in x.keys())
+ 10
* (
# 5 * sex_penalty
+ 100 * pair_penalty
+ 5000 * old_penalty_2024
+ 100 * old_penalty_2024_reverse
+ 1000 * old_penalty_2023
+ 500 * old_penalty_2022
+ 100 * old_penalty_2021
+ 50 * old_penalty_2019
+ old_penalty_2018
)
)
print("Finished Contraint set-up")
def generate_html_report(PAIRS, c, violations_data, obj_data):
"""Generate a beautiful HTML report for the solution"""
from datetime import datetime
current_time = datetime.now().strftime('%d.%m.%Y um %H:%M:%S')
html = f"""
Silvester Wichteln 2025 - Lösung #{c}
Geschenkpaare 2025
"""
for giver, receiver in PAIRS:
html += f"""
"""
html += """
Historie pro Person
| Person |
2018 |
2019 |
2021 |
2022 |
2023 |
2024 |
2025 |
"""
for n in NAMES:
hist_2018 = [t[1] for t in PAIRS_2018 if t[0] == n]
hist_2019 = [t[1] for t in PAIRS_2019 if t[0] == n]
hist_2021 = [t[1] for t in PAIRS_2021 if t[0] == n]
hist_2022 = [t[1] for t in PAIRS_2022 if t[0] == n]
hist_2023 = [t[1] for t in PAIRS_2023 if t[0] == n]
hist_2024 = [t[1] for t in PAIRS_2024 if t[0] == n]
hist_2025 = [t[1] for t in PAIRS if t[0] == n]
html += f"""
| {n} |
{', '.join(hist_2018) if hist_2018 else '-'} |
{', '.join(hist_2019) if hist_2019 else '-'} |
{', '.join(hist_2021) if hist_2021 else '-'} |
{', '.join(hist_2022) if hist_2022 else '-'} |
{', '.join(hist_2023) if hist_2023 else '-'} |
{', '.join(hist_2024) if hist_2024 else '-'} |
{', '.join(hist_2025) if hist_2025 else '-'} |
"""
html += """
Verletzungsprüfung
"""
violations_found = violations_data.get('violations_found', False)
violation_class = "" if violations_found else "no-violations"
html += f"""
"""
# Sex pair violations
sex_pair_violations = violations_data.get('sex_pair_violations', [])
if sex_pair_violations:
html += """
❌ VERLETZUNG
Verbotene Paare:
"""
for giver, receiver in sex_pair_violations:
html += f" - {giver} → {receiver}
\n"
html += """
"""
else:
html += """
✓ OK
Verbotene Paare: Keine Verletzungen
"""
# Previous year violations
prev_year_violations = violations_data.get('prev_year_violations', [])
if prev_year_violations:
html += """
❌ VERLETZUNG
Vorjahrespaare:
"""
for year, giver, receiver, direction in prev_year_violations:
html += f" - {year} {giver} → {receiver} ({direction})
\n"
html += """
"""
else:
html += """
✓ OK
Vorjahrespaare: Keine Verletzungen
"""
# Mutual violations
mutual_violations = violations_data.get('mutual_violations', [])
if mutual_violations:
html += """
❌ VERLETZUNG
Gegenseitiges Beschenken:
"""
for g1, r1, g2, r2 in mutual_violations:
html += f" - {g1} ↔ {r1}
\n"
html += """
"""
else:
html += """
✓ OK
Gegenseitiges Beschenken: Keine Verletzungen
"""
# Assignment violations
assignment_issues = violations_data.get('assignment_issues', {})
if assignment_issues.get('missing_givers') or assignment_issues.get('missing_receivers') or \
assignment_issues.get('duplicate_givers') or assignment_issues.get('duplicate_receivers'):
html += """
❌ VERLETZUNG
Zuordnungsfehler:
"""
if assignment_issues.get('missing_givers'):
html += f" - Fehlende Geber: {', '.join(assignment_issues['missing_givers'])}
\n"
if assignment_issues.get('missing_receivers'):
html += f" - Fehlende Empfänger: {', '.join(assignment_issues['missing_receivers'])}
\n"
if assignment_issues.get('duplicate_givers'):
html += f" - Doppelte Geber: {', '.join(set(assignment_issues['duplicate_givers']))}
\n"
if assignment_issues.get('duplicate_receivers'):
html += f" - Doppelte Empfänger: {', '.join(set(assignment_issues['duplicate_receivers']))}
\n"
html += """
"""
else:
html += """
✓ OK
Zuordnungen: Alle Teilnehmer geben und erhalten genau einmal
"""
html += f"""
{'✓ KEINE VERLETZUNGEN - LÖSUNG IST GÜLTIG' if not violations_found else '⚠️ VERLETZUNGEN ERKANNT'}
Zielfunktionswerte
"""
for label, value, weighted in obj_data:
html += f"""
{label}
{value:.4f}
→ {weighted:.2f}
"""
html += f"""
Gesamter Zielfunktionswert: {obj_data[0][1]:.4f}
"""
return html
objVal = 0
c = 0
final_solution_data = None
while objVal == 0:
c += 1
m.optimize()
PAIRS = []
for key in x.keys():
if x[key].x > 0.1:
PAIRS.append(key)
x[key].ub = 0
print("\n" + "="*80)
print(f"SOLUTION #{c}")
print("="*80)
print("\n--- GIFT PAIRS (2025) ---")
for p in PAIRS:
print(f" {p[0]} -> {p[1]}")
with open(f"sol_2024_{c}.json", "w") as f:
f.write(json.dumps(PAIRS))
print("\n--- HISTORY PER PERSON ---")
for n in NAMES:
print(n)
print("\t2018", [t[1] for t in PAIRS_2018 if t[0] == n])
print("\t2019", [t[1] for t in PAIRS_2019 if t[0] == n])
print("\t2021", [t[1] for t in PAIRS_2021 if t[0] == n])
print("\t2022", [t[1] for t in PAIRS_2022 if t[0] == n])
print("\t2023", [t[1] for t in PAIRS_2023 if t[0] == n])
print("\t2024", [t[1] for t in PAIRS_2024 if t[0] == n])
print("\t2025", [t[1] for t in PAIRS if t[0] == n])
# Check for violations
print("\n" + "="*80)
print("VIOLATION CHECKS")
print("="*80)
violations_found = False
# Check same-sex pairs
# same_sex_violations = []
# for giver, receiver in PAIRS:
# if (giver in MEN and receiver in MEN) or (giver in WOMEN and receiver in WOMEN):
# same_sex_violations.append((giver, receiver))
# if same_sex_violations:
# violations_found = True
# print("\n❌ SAME-SEX PAIR VIOLATIONS:")
# for giver, receiver in same_sex_violations:
# print(f" {giver} -> {receiver}")
# else:
# print("\n✓ No same-sex pair violations")
# Check sex pairs (forbidden pairs)
sex_pair_violations = []
for giver, receiver in PAIRS:
if (giver, receiver) in SEX_PAIRS or (receiver, giver) in SEX_PAIRS:
sex_pair_violations.append((giver, receiver))
if sex_pair_violations:
violations_found = True
print("\n❌ SEX PAIR VIOLATIONS (forbidden pairs):")
for giver, receiver in sex_pair_violations:
print(f" {giver} -> {receiver}")
else:
print("\n✓ No sex pair violations")
# Check previous year violations
prev_year_violations = []
for giver, receiver in PAIRS:
# Check 2018
if (giver, receiver) in PAIRS_2018:
prev_year_violations.append(("2018", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2018:
prev_year_violations.append(("2018", giver, receiver, "reverse"))
# Check 2019
if (giver, receiver) in PAIRS_2019:
prev_year_violations.append(("2019", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2019:
prev_year_violations.append(("2019", giver, receiver, "reverse"))
# Check 2021
if (giver, receiver) in PAIRS_2021:
prev_year_violations.append(("2021", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2021:
prev_year_violations.append(("2021", giver, receiver, "reverse"))
# Check 2022
if (giver, receiver) in PAIRS_2022:
prev_year_violations.append(("2022", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2022:
prev_year_violations.append(("2022", giver, receiver, "reverse"))
# Check 2023
if (giver, receiver) in PAIRS_2023:
prev_year_violations.append(("2023", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2023:
prev_year_violations.append(("2023", giver, receiver, "reverse"))
# Check 2024
if (giver, receiver) in PAIRS_2024:
prev_year_violations.append(("2024", giver, receiver, "same direction"))
if (receiver, giver) in PAIRS_2024:
prev_year_violations.append(("2024", giver, receiver, "reverse"))
if prev_year_violations:
violations_found = True
print("\n❌ PREVIOUS YEAR PAIR VIOLATIONS:")
for year, giver, receiver, direction in prev_year_violations:
print(f" {year}: {giver} -> {receiver} ({direction})")
else:
print("\n✓ No previous year pair violations")
# Check mutual gifting (should not happen)
mutual_violations = []
pair_set = set(PAIRS)
for giver, receiver in PAIRS:
if (receiver, giver) in pair_set:
mutual_violations.append((giver, receiver, receiver, giver))
if mutual_violations:
violations_found = True
print("\n❌ MUTUAL GIFTING VIOLATIONS:")
for g1, r1, g2, r2 in mutual_violations:
print(f" {g1} <-> {r1} (mutual)")
else:
print("\n✓ No mutual gifting violations")
# Check if everyone gives and receives exactly once
givers = [p[0] for p in PAIRS]
receivers = [p[1] for p in PAIRS]
missing_givers = set(NAMES) - set(givers)
missing_receivers = set(NAMES) - set(receivers)
duplicate_givers = [name for name in givers if givers.count(name) > 1]
duplicate_receivers = [name for name in receivers if receivers.count(name) > 1]
assignment_issues = {}
if missing_givers or missing_receivers or duplicate_givers or duplicate_receivers:
violations_found = True
print("\n❌ ASSIGNMENT VIOLATIONS:")
if missing_givers:
print(f" Missing givers: {missing_givers}")
assignment_issues['missing_givers'] = missing_givers
if missing_receivers:
print(f" Missing receivers: {missing_receivers}")
assignment_issues['missing_receivers'] = missing_receivers
if duplicate_givers:
print(f" Duplicate givers: {set(duplicate_givers)}")
assignment_issues['duplicate_givers'] = duplicate_givers
if duplicate_receivers:
print(f" Duplicate receivers: {set(duplicate_receivers)}")
assignment_issues['duplicate_receivers'] = duplicate_receivers
else:
print("\n✓ All participants give and receive exactly once")
# Summary
print("\n" + "="*80)
if violations_found:
print("⚠️ VIOLATIONS DETECTED")
else:
print("✓ NO VIOLATIONS - SOLUTION IS VALID")
print("="*80)
# Objective value details
print(f"\nObjective value: {m.objVal}")
# print(f" Sex penalty: {sex_penalty.x} -> {100*sex_penalty.x}")
print(f" Pair penalty: {pair_penalty.x} -> {100*pair_penalty.x}")
print(f" 2024 penalty: {old_penalty_2024.x} -> {5000*old_penalty_2024.x}")
print(f" 2024 reverse penalty: {old_penalty_2024_reverse.x} -> {100*old_penalty_2024_reverse.x}")
print(f" 2023 penalty: {old_penalty_2023.x} -> {1000*old_penalty_2023.x}")
print(f" 2022 penalty: {old_penalty_2022.x} -> {500*old_penalty_2022.x}")
print(f" 2021 penalty: {old_penalty_2021.x} -> {100*old_penalty_2021.x}")
print(f" 2019 penalty: {old_penalty_2019.x} -> {50*old_penalty_2019.x}")
print(f" 2018 penalty: {old_penalty_2018.x} -> {10*old_penalty_2018.x}")
print("="*80 + "\n")
# Store data for HTML report
violations_data = {
'violations_found': violations_found,
'sex_pair_violations': sex_pair_violations,
'prev_year_violations': prev_year_violations,
'mutual_violations': mutual_violations,
'assignment_issues': assignment_issues
}
obj_data = [
("Gesamtwert", m.objVal, m.objVal),
("Pair Penalty", pair_penalty.x, 100 * pair_penalty.x),
("2024 Penalty", old_penalty_2024.x, 5000 * old_penalty_2024.x),
("2024 Reverse", old_penalty_2024_reverse.x, 100 * old_penalty_2024_reverse.x),
("2023 Penalty", old_penalty_2023.x, 1000 * old_penalty_2023.x),
("2022 Penalty", old_penalty_2022.x, 500 * old_penalty_2022.x),
("2021 Penalty", old_penalty_2021.x, 100 * old_penalty_2021.x),
("2019 Penalty", old_penalty_2019.x, 50 * old_penalty_2019.x),
("2018 Penalty", old_penalty_2018.x, 10 * old_penalty_2018.x),
]
final_solution_data = {
'PAIRS': PAIRS,
'c': c,
'violations_data': violations_data,
'obj_data': obj_data
}
objVal = m.objVal
# Generate HTML report after optimization loop
if final_solution_data:
html_report = generate_html_report(
final_solution_data['PAIRS'],
final_solution_data['c'],
final_solution_data['violations_data'],
final_solution_data['obj_data']
)
html_filename = f"silvester2025_report_{final_solution_data['c']}.html"
with open(html_filename, "w", encoding="utf-8") as f:
f.write(html_report)
print(f"\n{'='*80}")
print(f"HTML Report erstellt: {html_filename}")
print(f"{'='*80}\n")
# %%
import matplotlib.pyplot as plt
import networkx as nx
G = nx.DiGraph()
G.clear()
G.add_nodes_from(NAMES)
G.add_edges_from(PAIRS)
pos = nx.kamada_kawai_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=500)
nx.draw_networkx_labels(G, pos)
nx.draw_networkx_edges(G, pos, edgelist=PAIRS, edge_color="r", arrows=True)
# nx.draw_networkx_edges(G, pos, edgelist=black_edges, arrows=False)
plt.savefig(f'silvester2025_{c}.png')
# plt.savefig(f'silvester2022_{c}.pdf')
plt.show()
# %%