Something makes this render infeasible and i dont know why

[martinohansen]

I've been pulling my hair out over this problem for a few days now, I hope a kind soul in here can help me find the problem.

Consider this slightly simplified and redacted function:

def find_optimal_team(candidates: Sequence[Candidate]) -> list[Candidate]:
    """
    Takes a list of candidates and returns the 11 candidates that maximize the
    combined value within the rules of the game.
    """
    # Create a linear programming problem
    problem = LpProblem("OptimalTeam", LpMaximize)

    # Create a dictionary to store the variables for each candidate
    variables = {}

    # Create a variable for each candidate. The variable is an integer between 0
    # and 1 where 1 means selected and 0 means not selected.
    for candidate in candidates:
        identifier = f"{candidate.id}_{int(candidate.captain)}"
        variables[candidate] = LpVariable(identifier, 0, 1, LpInteger)

    # Set the objective function to maximize the combined xValue of the team
    problem += sum(variables[c] * c.xValue for c in candidates)

    # Add the constraint that no two identical candidates can be selected
    for candidate in candidates:
        problem += (
            sum(variables[c] for c in candidates if c.name == candidate.name) <= 1
        )

    # Add the constraint that there must be exactly 11 players in total
    problem += sum(variables[c] for c in candidates) == 11

    # Solve the problem
    problem.writeLP("problem.lp")
    status = problem.solve(PULP_CBC_CMD(msg=0))
    logging.info(f"LpStatus: {LpStatus[status]}")

    # Iterate through the selected candidates and add them to the optimal team
    optimal_team = []
    for candidate in candidates:
        if value(variables[candidate]) > 0:
            optimal_team.append(candidate)

    return optimal_team

Being executed like this:

candidates = [...]
captain_variant = [copy.deepcopy(c) for c in candidates]
for c in captain_variant:
    c.captain = True
# This line is what makes it render as infeasible. If I comment this line out
# it works as expected. 
candidates = candidates + captain_variant

solution = find_optimal_team(candidates, 70 * 1000000)
print(solution)

It renders as infeasible unless I removes the captain variant from the input. The output looks similar to this, the crown means its the captain variant.

# With the captain variant
[10:11:28] INFO     LpStatus: Infeasible                                           lp.py:118
[
    ⚽️ Eberechi Eze (Crystal Palace), value=5.2M, xGrowth=120K,
    ⚽️ Trent Alexander-Arnold (Liverpool), value=7.2M, xGrowth=87K,
    ⚽️ Mohamed Salah (Liverpool), value=12.5M, xGrowth=213K,
    ⚽️ Callum Wilson (Newcastle), value=7.7M, xGrowth=176K,
    ⚽️ Ben Mee (Brentford), value=4.2M, xGrowth=91K,
    ⚽️ Ilkay Gündogan (Manchester City), value=8.1M, xGrowth=124K,
    ⚽️ Erling Håland (Manchester City), value=15.9M, xGrowth=164K,
    ⚽️ Mikkel Damsgaard (Brentford), value=3.8M, xGrowth=122K,
    ⚽️ Pervis Estupinan (Brighton and Hove), value=4.5M, xGrowth=84K,
    ⚽️ Julio Enciso (Brighton and Hove), value=3.2M, xGrowth=122K,
    ⚽️ Curtis Jones (Liverpool), value=3.4M, xGrowth=114K,
    ⚽️ Caoimhin Kelleher (Liverpool), value=4.9M, xGrowth=55K,
    👑 Eberechi Eze (Crystal Palace), value=5.2M, xGrowth=240K,
    👑 Trent Alexander-Arnold (Liverpool), value=7.2M, xGrowth=174K,
    👑 Mohamed Salah (Liverpool), value=12.5M, xGrowth=427K,
    👑 Callum Wilson (Newcastle), value=7.7M, xGrowth=352K,
    👑 Ben Mee (Brentford), value=4.2M, xGrowth=183K,
    👑 Ilkay Gündogan (Manchester City), value=8.1M, xGrowth=248K,
    👑 Erling Håland (Manchester City), value=15.9M, xGrowth=328K,
    👑 Mikkel Damsgaard (Brentford), value=3.8M, xGrowth=243K,
    👑 Pervis Estupinan (Brighton and Hove), value=4.5M, xGrowth=168K,
    👑 Julio Enciso (Brighton and Hove), value=3.2M, xGrowth=245K,
    👑 Curtis Jones (Liverpool), value=3.4M, xGrowth=228K,
    👑 Caoimhin Kelleher (Liverpool), value=4.9M, xGrowth=111K
]

# Without the captain variant:
[10:16:50] INFO     LpStatus: Optimal                                              lp.py:118
[
    ⚽️ Eberechi Eze (Crystal Palace), value=5.2M, xGrowth=120K,
    ⚽️ Sam Johnstone (Crystal Palace), value=4.0M, xGrowth=35K,
    ⚽️ Mohamed Salah (Liverpool), value=12.5M, xGrowth=213K,
    ⚽️ Callum Wilson (Newcastle), value=7.7M, xGrowth=176K,
    ⚽️ Ben Mee (Brentford), value=4.2M, xGrowth=91K,
    ⚽️ Alexis Mac Allister (Brighton and Hove), value=5.0M, xGrowth=113K,
    ⚽️ Erling Håland (Manchester City), value=15.9M, xGrowth=164K,
    ⚽️ Mikkel Damsgaard (Brentford), value=3.8M, xGrowth=122K,
    ⚽️ Pervis Estupinan (Brighton and Hove), value=4.5M, xGrowth=84K,
    ⚽️ Curtis Jones (Liverpool), value=3.4M, xGrowth=114K,
    ⚽️ Ibrahima Konate (Liverpool), value=3.1M, xGrowth=67K
]

If anyone can spot the problem I would be grateful.

[martinohansen]

Solution:

  # Create a variable for each candidate. The variable is an integer between 0
    # and 1 where 1 means selected and 0 means not selected.
    for candidate in candidates:
        identifier = f"{candidate.id}_{int(candidate.captain)}"
        variables[(candidate.id, candidate.captain)] = LpVariable(
            identifier, 0, 1, LpInteger
        )

    # Set the objective function to maximize the combined xGrowth of the team
    problem += sum(variables[(c.id, c.captain)] * c.xValue for c in candidates)