selection

selection

Squad selection and optimization.

BudgetConstraint

BudgetConstraint(max_budget: float = 100.0)

Budget constraint for FPL squad (applied to 15-player squad).

Source code in fplx/selection/constraints.py

def __init__(self, max_budget: float = 100.0):
    self.max_budget = max_budget

FormationConstraints

Formation constraints for FPL squad.

Rules: - Exactly 11 players - 1 GK - 3-5 DEF - 2-5 MID - 1-3 FWD

validate classmethod

validate(players: list[Player]) -> bool

Check if squad satisfies formation constraints.

PARAMETER	DESCRIPTION
players	List of players in squad TYPE: list[Player]

RETURNS	DESCRIPTION
bool	True if valid formation

Source code in fplx/selection/constraints.py

@classmethod
def validate(cls, players: list[Player]) -> bool:
    """
    Check if squad satisfies formation constraints.

    Parameters
    ----------
    players : list[Player]
        List of players in squad

    Returns
    -------
    bool
        True if valid formation
    """
    if len(players) != cls.TOTAL_PLAYERS:
        return False
    counts = {"GK": 0, "DEF": 0, "MID": 0, "FWD": 0}
    for p in players:
        counts[p.position] += 1
    return all(lo <= counts[pos] <= hi for pos, (lo, hi) in cls.POSITION_LIMITS.items())

get_valid_formations classmethod

get_valid_formations() -> list[str]

Get list of valid formation strings.

RETURNS	DESCRIPTION
List[str]	Valid formations (e.g., "3-4-3", "4-3-3")

Source code in fplx/selection/constraints.py

@classmethod
def get_valid_formations(cls) -> list[str]:
    """
    Get list of valid formation strings.

    Returns
    -------
    List[str]
        Valid formations (e.g., "3-4-3", "4-3-3")
    """
    formations = []
    for d in range(3, 6):
        for m in range(2, 6):
            for f in range(1, 4):
                if d + m + f == 10:
                    formations.append(f"{d}-{m}-{f}")
    return formations

SquadQuotas

Position quotas for the 15-player FPL squad.

Rules: - 2 GK, 5 DEF, 5 MID, 3 FWD (exactly). - Total = 15 players.

TeamDiversityConstraint

TeamDiversityConstraint(max_from_team: int = 3)

Max players from same real-world team (default 3).

Source code in fplx/selection/constraints.py

def __init__(self, max_from_team: int = 3):
    self.max_from_team = max_from_team

LagrangianOptimizer

LagrangianOptimizer(
    budget: float = 100.0,
    max_from_team: int = 3,
    max_iter: int = 200,
    tol: float = 0.01,
    risk_aversion: float = 0.0,
)

Lagrangian relaxation for the FPL squad selection ILP.

Relaxes the budget constraint into the objective:

L(lambda) = max_{x in X} sum_i (mu_i - lambda * c_i) * x_i + lambda * B

where X encodes squad size, position quotas, and team caps. The inner maximization decomposes: for each position, select the top-k players by modified score (mu_i - lambda * c_i).

The dual problem min_{lambda >= 0} L(lambda) is solved via subgradient ascent.

PARAMETER	DESCRIPTION
budget	Total budget (default 100.0). TYPE: float DEFAULT: 100.0
max_from_team	Maximum players from same club. TYPE: int DEFAULT: 3
max_iter	Maximum subgradient iterations. TYPE: int DEFAULT: 200
tol	Convergence tolerance on duality gap. TYPE: float DEFAULT: 0.01
risk_aversion	Mean-variance penalty (same as ILP). TYPE: float DEFAULT: 0.0

Source code in fplx/selection/lagrangian.py

def __init__(
    self,
    budget: float = 100.0,
    max_from_team: int = 3,
    max_iter: int = 200,
    tol: float = 0.01,
    risk_aversion: float = 0.0,
):
    self.budget = budget
    self.max_from_team = max_from_team
    self.max_iter = max_iter
    self.tol = tol
    self.risk_aversion = risk_aversion

solve

solve(
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    best_known_primal: Optional[float] = None,
) -> LagrangianResult

Solve via Lagrangian relaxation with subgradient ascent.

PARAMETER	DESCRIPTION
players	TYPE: list[Player]
expected_points	TYPE: dict[int, float]
expected_variance	TYPE: dict[int, float] DEFAULT: None
best_known_primal	Best known primal objective (e.g., from ILP). Used for better step size computation. TYPE: float DEFAULT: None

RETURNS	DESCRIPTION
LagrangianResult

Source code in fplx/selection/lagrangian.py

def solve(
    self,
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    best_known_primal: Optional[float] = None,
) -> LagrangianResult:
    """
    Solve via Lagrangian relaxation with subgradient ascent.

    Parameters
    ----------
    players : list[Player]
    expected_points : dict[int, float]
    expected_variance : dict[int, float], optional
    best_known_primal : float, optional
        Best known primal objective (e.g., from ILP).
        Used for better step size computation.

    Returns
    -------
    LagrangianResult
    """
    start_time = time.perf_counter()

    # Initialize lambda
    lam = 0.5  # initial budget multiplier
    best_dual = np.inf
    best_primal = -np.inf
    best_squad = None
    best_lineup = None

    # Step size parameters (Polyak-style)
    theta = 2.0
    theta_decay = 0.95
    no_improve_count = 0

    result = LagrangianResult()

    for k in range(self.max_iter):
        # Compute modified scores
        scores = self._compute_modified_scores(players, expected_points, expected_variance, lam)

        # Solve inner problem
        squad, lineup = self._solve_inner(players, scores)

        # Dual objective: L(lambda) = sum scores*x + lambda*B
        inner_value = sum(scores[p.id] for p in lineup)
        dual_obj = inner_value + lam * self.budget

        # Primal objective (original, without lambda penalty)
        primal_obj = sum(expected_points.get(p.id, 0.0) for p in lineup)
        if self.risk_aversion > 0 and expected_variance:
            for p in lineup:
                primal_obj -= self.risk_aversion * np.sqrt(max(expected_variance.get(p.id, 0.0), 0.0))

        # Budget slack (subgradient)
        squad_cost = sum(p.price for p in squad)
        budget_slack = squad_cost - self.budget  # positive = over budget

        # Track best
        if dual_obj < best_dual:
            best_dual = dual_obj
            no_improve_count = 0
        else:
            no_improve_count += 1

        # Only count as feasible primal if budget satisfied
        if squad_cost <= self.budget + 0.01 and primal_obj > best_primal:
            best_primal = primal_obj
            best_squad = squad
            best_lineup = lineup

        # Record history
        result.dual_history.append(float(dual_obj))
        result.primal_history.append(float(primal_obj))
        result.lambda_history.append(float(lam))
        result.budget_slack_history.append(float(budget_slack))

        # Convergence check
        gap = (best_dual - best_primal) / max(abs(best_dual), 1e-6)
        if gap < self.tol and best_primal > -np.inf:
            result.converged = True
            break

        # Step size (Polyak with target)
        target = best_known_primal if best_known_primal else best_primal
        step = 0.0 if abs(budget_slack) < 1e-08 else theta * (dual_obj - target) / budget_slack**2

        # Update lambda
        lam = max(0.0, lam + step * budget_slack)

        # Decay step size if no improvement
        if no_improve_count >= 5:
            theta *= theta_decay
            no_improve_count = 0

    elapsed = time.perf_counter() - start_time

    # Build FullSquad from best feasible solution
    if best_squad and best_lineup and len(best_squad) == 15 and len(best_lineup) == 11:
        pos_counts = {"DEF": 0, "MID": 0, "FWD": 0}
        for p in best_lineup:
            if p.position in pos_counts:
                pos_counts[p.position] += 1
        formation = f"{pos_counts['DEF']}-{pos_counts['MID']}-{pos_counts['FWD']}"

        ep_lineup = sum(expected_points.get(p.id, 0.0) for p in best_lineup)
        captain = max(best_lineup, key=lambda p: expected_points.get(p.id, 0.0))

        lineup_obj = Squad(
            players=best_lineup,
            formation=formation,
            total_cost=sum(p.price for p in best_lineup),
            expected_points=ep_lineup,
            captain=captain,
        )
        result.full_squad = FullSquad(squad_players=best_squad, lineup=lineup_obj)

    result.primal_objective = best_primal
    result.dual_bound = best_dual
    result.duality_gap = (best_dual - best_primal) / max(abs(best_dual), 1e-6)
    result.n_iterations = k + 1
    result.solve_time = elapsed

    logger.info(
        "Lagrangian: %d iters, primal=%.1f, dual=%.1f, gap=%.2f%%, time=%.3fs",
        result.n_iterations,
        best_primal,
        best_dual,
        result.duality_gap * 100,
        elapsed,
    )

    return result

LagrangianResult dataclass

LagrangianResult(
    full_squad: Optional[FullSquad] = None,
    primal_objective: float = 0.0,
    dual_bound: float = 0.0,
    duality_gap: float = 0.0,
    n_iterations: int = 0,
    converged: bool = False,
    solve_time: float = 0.0,
    dual_history: list[float] = list(),
    primal_history: list[float] = list(),
    lambda_history: list[float] = list(),
    budget_slack_history: list[float] = list(),
)

Convergence diagnostics for the Lagrangian solver.

GreedyOptimizer

GreedyOptimizer(
    budget: float = 100.0, max_from_team: int = 3
)

Bases: BaseOptimizer

Greedy baseline: select best-value players per position.

Fast heuristic for comparison. Selects 15-player squad, then picks best 11 as lineup.

Source code in fplx/selection/optimizer.py

def __init__(self, budget: float = 100.0, max_from_team: int = 3):
    self.budget = budget
    self.max_from_team = max_from_team

optimize

optimize(
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    formation: Optional[str] = None,
) -> FullSquad

Greedy squad + lineup selection.

Source code in fplx/selection/optimizer.py

def optimize(
    self,
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    formation: Optional[str] = None,
) -> FullSquad:
    """Greedy squad + lineup selection."""
    # Compute value = EP / price for each player
    for p in players:
        ep = expected_points.get(p.id, 0.0)
        p.expected_points = ep
        p._value = ep / max(p.price, 0.1)

    # Sort by value within each position
    by_pos: dict[str, list[Player]] = {"GK": [], "DEF": [], "MID": [], "FWD": []}
    for p in players:
        by_pos[p.position].append(p)
    for pos in by_pos:
        by_pos[pos].sort(key=lambda p: p._value, reverse=True)

    # Greedily fill squad (15 players)
    squad_quotas = {"GK": 2, "DEF": 5, "MID": 5, "FWD": 3}
    selected_squad: list[Player] = []
    team_counts: dict[str, int] = {}
    remaining = self.budget

    for pos in ["GK", "DEF", "MID", "FWD"]:
        count = 0
        for p in by_pos[pos]:
            if count >= squad_quotas[pos]:
                break
            if team_counts.get(p.team, 0) >= self.max_from_team:
                continue
            if p.price > remaining:
                continue
            selected_squad.append(p)
            team_counts[p.team] = team_counts.get(p.team, 0) + 1
            remaining -= p.price
            count += 1

    if len(selected_squad) != 15:
        logger.warning("Greedy only picked %d squad players.", len(selected_squad))
        # Pad if needed (shouldn't happen with 600+ players)
        return self._fallback(selected_squad, expected_points)

    # Select best 11 from the 15
    lineup = self._select_lineup(selected_squad, expected_points, formation)
    return FullSquad(squad_players=selected_squad, lineup=lineup)

OptimizationResult dataclass

OptimizationResult(
    full_squad: FullSquad,
    objective_value: float = 0.0,
    solve_time: float = 0.0,
    lp_objective: Optional[float] = None,
    integrality_gap: Optional[float] = None,
    shadow_prices: dict = dict(),
    binding_constraints: list = list(),
)

Container for optimization outputs including duality analysis.

TwoLevelILPOptimizer

TwoLevelILPOptimizer(
    budget: float = 100.0,
    max_from_team: int = 3,
    risk_aversion: float = 0.0,
)

Bases: BaseOptimizer

Two-level ILP: select 15-player squad then 11-player lineup jointly.

Supports risk-neutral and risk-averse (mean-variance) objectives. Also exposes LP relaxation for shadow price extraction.

PARAMETER	DESCRIPTION
budget	Maximum total squad budget (applied to 15 players). TYPE: float DEFAULT: 100.0
max_from_team	Maximum players from same club. TYPE: int DEFAULT: 3
risk_aversion	Lambda for mean-variance penalty. 0 = risk-neutral. TYPE: float DEFAULT: 0.0

Source code in fplx/selection/optimizer.py

def __init__(
    self,
    budget: float = 100.0,
    max_from_team: int = 3,
    risk_aversion: float = 0.0,
):
    self.budget = budget
    self.max_from_team = max_from_team
    self.risk_aversion = risk_aversion

    try:
        import pulp

        self.pulp = pulp
    except ImportError:
        raise ImportError("pulp required for ILP optimization. Install with: pip install pulp")

solve

solve(players, **kwargs)

Solve the optimization problem.

Source code in fplx/selection/optimizer.py

def solve(self, players, **kwargs):
    """Solve the optimization problem."""
    return self.optimize(players, **kwargs)

optimize

optimize(
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    downside_risk: Optional[dict[int, float]] = None,
    formation: Optional[str] = None,
) -> FullSquad

Solve the two-level ILP.

PARAMETER	DESCRIPTION
players	Available player pool. TYPE: list[Player]
expected_points	E[P_i] per player. TYPE: dict[int, float]
expected_variance	Var[P_i] per player. TYPE: dict[int, float] DEFAULT: None
downside_risk	Downside spread per player. If provided, risk penalty uses this directly (instead of sqrt(variance)). TYPE: dict[int, float] DEFAULT: None
formation	Not used (formation is optimized automatically). TYPE: Optional[str] DEFAULT: None

RETURNS	DESCRIPTION
FullSquad

Source code in fplx/selection/optimizer.py

def optimize(
    self,
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    downside_risk: Optional[dict[int, float]] = None,
    formation: Optional[str] = None,
) -> FullSquad:
    """
    Solve the two-level ILP.

    Parameters
    ----------
    players : list[Player]
        Available player pool.
    expected_points : dict[int, float]
        E[P_i] per player.
    expected_variance : dict[int, float], optional
        Var[P_i] per player.
    downside_risk : dict[int, float], optional
        Downside spread per player. If provided, risk penalty uses this
        directly (instead of sqrt(variance)).
    formation : Optional[str]
        Not used (formation is optimized automatically).

    Returns
    -------
    FullSquad
    """
    import time

    start = time.perf_counter()
    prob, s_vars, x_vars = self._build_problem(
        players,
        expected_points,
        expected_variance,
        downside_risk,
        relax=False,
    )
    prob.solve(self.pulp.PULP_CBC_CMD(msg=0))
    elapsed = time.perf_counter() - start

    if prob.status != 1:
        logger.error("ILP solver did not find optimal solution (status=%d).", prob.status)

    # Extract solution
    squad_players = [p for p in players if s_vars[p.id].varValue and s_vars[p.id].varValue > 0.5]
    lineup_players = [p for p in players if x_vars[p.id].varValue and x_vars[p.id].varValue > 0.5]

    # Determine formation
    pos_counts = {"DEF": 0, "MID": 0, "FWD": 0}
    for p in lineup_players:
        if p.position in pos_counts:
            pos_counts[p.position] += 1
    formation_str = f"{pos_counts['DEF']}-{pos_counts['MID']}-{pos_counts['FWD']}"

    # Captain = highest expected points
    for p in lineup_players:
        p.expected_points = expected_points.get(p.id, 0.0)
    captain = (
        max(lineup_players, key=lambda p: expected_points.get(p.id, 0.0)) if lineup_players else None
    )

    total_ep = sum(expected_points.get(p.id, 0.0) for p in lineup_players)
    lineup_cost = sum(p.price for p in lineup_players)

    lineup = Squad(
        players=lineup_players,
        formation=formation_str,
        total_cost=lineup_cost,
        expected_points=total_ep,
        captain=captain,
    )
    full_squad = FullSquad(squad_players=squad_players, lineup=lineup)

    logger.info("ILP solved in %.3fs. Formation: %s. EP: %.2f", elapsed, formation_str, total_ep)
    return full_squad

solve_lp_relaxation

solve_lp_relaxation(
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    downside_risk: Optional[dict[int, float]] = None,
) -> OptimizationResult

Solve the LP relaxation and extract shadow prices.

RETURNS	DESCRIPTION
OptimizationResult	Contains LP objective, shadow prices, binding constraints.

Source code in fplx/selection/optimizer.py

def solve_lp_relaxation(
    self,
    players: list[Player],
    expected_points: dict[int, float],
    expected_variance: Optional[dict[int, float]] = None,
    downside_risk: Optional[dict[int, float]] = None,
) -> OptimizationResult:
    """
    Solve the LP relaxation and extract shadow prices.

    Returns
    -------
    OptimizationResult
        Contains LP objective, shadow prices, binding constraints.
    """
    import time

    start = time.perf_counter()
    prob, s_vars, x_vars = self._build_problem(
        players,
        expected_points,
        expected_variance,
        downside_risk,
        relax=True,
    )
    prob.solve(self.pulp.PULP_CBC_CMD(msg=0))
    elapsed = time.perf_counter() - start

    lp_obj = self.pulp.value(prob.objective)

    # Extract shadow prices from constraints
    shadow_prices = {}
    binding = []
    for name, constraint in prob.constraints.items():
        slack = constraint.slack
        # PuLP: pi attribute gives the dual value for LP
        dual = constraint.pi if constraint.pi is not None else 0.0
        shadow_prices[name] = {
            "dual_value": dual,
            "slack": slack,
            "binding": abs(slack) < 1e-6,
        }
        if abs(slack) < 1e-6:
            binding.append(name)

    # Also solve ILP to compute integrality gap
    full_squad = self.optimize(players, expected_points, expected_variance, downside_risk)
    ilp_obj = full_squad.lineup.expected_points
    gap = (lp_obj - ilp_obj) / lp_obj if lp_obj > 0 else 0.0

    return OptimizationResult(
        full_squad=full_squad,
        objective_value=ilp_obj,
        solve_time=elapsed,
        lp_objective=lp_obj,
        integrality_gap=gap,
        shadow_prices=shadow_prices,
        binding_constraints=binding,
    )