# %% 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}

🎁 Silvester Wichteln 2025

Lösung #{c} - Generiert am {current_time}

Geschenkpaare 2025

""" for giver, receiver in PAIRS: html += f"""
{giver}
{receiver}
""" html += """

Historie pro Person

""" 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""" """ html += """
Person 2018 2019 2021 2022 2023 2024 2025
{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 '-'}

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() # %%