qualifiers-solver

Erstellt und optimiert MIP-Modelle für die Gruppenbildung in UEFA-Qualifikationsturnieren.

Trigger

Neue Optimierungsregeln
Solver-Constraints
"grouping solver", "mip constraint", "optimization"

Kontext

Der Solver verwendet PuLP mit Xpress/CBC Backend zur Gruppenbildung. Hauptfunktion ist groupTeams() in qualifiers/solver/draws.py.

Regeln

Solver-Auswahl über Environment:

from leagues.settings import SOLVER

if SOLVER == 'xpress':
    solver = XPRESS_PY(msg=1, mipgap=mipgap)
else:
    solver = PULP_CBC_CMD(msg=1, mipGap=mipgap)

Entscheidungsvariablen als Dict:

# Team t in Gruppe g
x = pulp.LpVariable.dicts(
    "x",
    [(t, g) for t in teams for g in groups],
    cat='Binary'
)

Constraints mit lpSum:

from pulp import lpSum

# Jedes Team genau einer Gruppe zuordnen
for t in teams:
    model += lpSum(x[t, g] for g in groups) == 1

Zielfunktion mit Gewichtung:

# priority: 0-100 (Distanz vs. Koeffizient)
coeff_weight = priority / 100
dist_weight = 1 - coeff_weight

model += coeff_weight * coeff_deviation + dist_weight * total_distance

Infeasibility-Handling:

status = model.solve(solver)
if status != pulp.LpStatusOptimal:
    # IIS (Irreducible Infeasible Set) analysieren
    raise InfeasibleError(f"Solver status: {pulp.LpStatus[status]}")

Beispiel: Neuer Constraint

# qualifiers/solver/draws.py - in groupTeams()

# Beispiel: Maximal 2 Teams aus Top-10 Ländern pro Gruppe
top10_countries = ['ESP', 'ENG', 'GER', 'ITA', 'FRA', 'POR', 'NED', 'BEL', 'UKR', 'TUR']

for g in groups:
    model += lpSum(
        x[t, g]
        for t in teams
        if any(c in top10_countries for c in t_countries[t])
    ) <= 2, f"max_top10_in_group_{g}"

Beispiel: Soft Constraint (Zielfunktion)

# Strafe für ungleiche Gruppengrößen
size_penalty = pulp.LpVariable.dicts(
    "size_penalty",
    groups,
    lowBound=0,
    cat='Continuous'
)

avg_size = sum(groupsizes_all.values()) / len(groups)
for g in groups:
    model += size_penalty[g] >= lpSum(x[t, g] for t in teams) - avg_size
    model += size_penalty[g] >= avg_size - lpSum(x[t, g] for t in teams)

# Zur Zielfunktion addieren
model += ... + 0.1 * lpSum(size_penalty[g] for g in groups)

Debugging

# Verbose Output
model.solve(XPRESS_PY(msg=1))

# Variablenwerte ausgeben
for v in model.variables():
    if v.varValue > 0.5:
        print(f"{v.name} = {v.varValue}")

# Constraint-Slack prüfen
for name, constraint in model.constraints.items():
    if constraint.slack < 0:
        print(f"Verletzt: {name}, slack={constraint.slack}")

Performance-Tipps

Symmetrie-Breaking: Erste Gruppe fixieren

# Erstes Team immer in Gruppe 0
model += x[teams[0], 0] == 1

MIP-Gap setzen:

solver = XPRESS_PY(mipgap=0.01)  # 1% Toleranz

Warm-Start mit fixed_groups:

for (team_id, group_id) in fixed_groups:
    model += x[team_id, group_id] == 1

Referenz-Dateien

qualifiers/solver/draws.py - Solver-Code
docs/qualifiers/solver/ - Dokumentation

3.3 KiB Raw Permalink Blame History