139 lines
3.3 KiB
Markdown
139 lines
3.3 KiB
Markdown
# 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](qualifiers/solver/draws.py).
|
|
|
|
## Regeln
|
|
|
|
1. **Solver-Auswahl über Environment**:
|
|
```python
|
|
from leagues.settings import SOLVER
|
|
|
|
if SOLVER == 'xpress':
|
|
solver = XPRESS_PY(msg=1, mipgap=mipgap)
|
|
else:
|
|
solver = PULP_CBC_CMD(msg=1, mipGap=mipgap)
|
|
```
|
|
|
|
2. **Entscheidungsvariablen als Dict**:
|
|
```python
|
|
# Team t in Gruppe g
|
|
x = pulp.LpVariable.dicts(
|
|
"x",
|
|
[(t, g) for t in teams for g in groups],
|
|
cat='Binary'
|
|
)
|
|
```
|
|
|
|
3. **Constraints mit lpSum**:
|
|
```python
|
|
from pulp import lpSum
|
|
|
|
# Jedes Team genau einer Gruppe zuordnen
|
|
for t in teams:
|
|
model += lpSum(x[t, g] for g in groups) == 1
|
|
```
|
|
|
|
4. **Zielfunktion mit Gewichtung**:
|
|
```python
|
|
# priority: 0-100 (Distanz vs. Koeffizient)
|
|
coeff_weight = priority / 100
|
|
dist_weight = 1 - coeff_weight
|
|
|
|
model += coeff_weight * coeff_deviation + dist_weight * total_distance
|
|
```
|
|
|
|
5. **Infeasibility-Handling**:
|
|
```python
|
|
status = model.solve(solver)
|
|
if status != pulp.LpStatusOptimal:
|
|
# IIS (Irreducible Infeasible Set) analysieren
|
|
raise InfeasibleError(f"Solver status: {pulp.LpStatus[status]}")
|
|
```
|
|
|
|
## Beispiel: Neuer Constraint
|
|
|
|
```python
|
|
# 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)
|
|
|
|
```python
|
|
# 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
|
|
|
|
```python
|
|
# 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
|
|
|
|
1. **Symmetrie-Breaking**: Erste Gruppe fixieren
|
|
```python
|
|
# Erstes Team immer in Gruppe 0
|
|
model += x[teams[0], 0] == 1
|
|
```
|
|
|
|
2. **MIP-Gap setzen**:
|
|
```python
|
|
solver = XPRESS_PY(mipgap=0.01) # 1% Toleranz
|
|
```
|
|
|
|
3. **Warm-Start mit fixed_groups**:
|
|
```python
|
|
for (team_id, group_id) in fixed_groups:
|
|
model += x[team_id, group_id] == 1
|
|
```
|
|
|
|
## Referenz-Dateien
|
|
|
|
- [qualifiers/solver/draws.py](qualifiers/solver/draws.py) - Solver-Code
|
|
- [docs/qualifiers/solver/](docs/qualifiers/solver/) - Dokumentation
|