Using JuMP to pick winners of a tournament

Specific Domains Optimization (Mathematical)
1

Hi,

I’m using JuMP to pick winners of games of a single-elimination tournament. I have everything running fine except for the fact that I can’t seem to figure out how to impose a constraint that eliminated teams not be picked in future rounds.

The full code for this example with 8 teams is here, but I’ll post a small excerpt:

function SolveModelMWE(data)
    N = size(data,1) 
    m = Model(solver=solver)

    ...

    @variable(m, picks[1:N,1:2], Bin)
    @objective(m, Max, sum(data[i,1] * sum(data[i,2+j] * picks[i,j] for j in 1:2) for i in 1:N))

    @constraints m begin

        ....

        # Constraint 2 - must have picked 7 winners, and appropriate number from each round
        sum(sum(picks[i,j] for j in 1:2) for i in  1:N ) ==  7
        sum(sum(picks[i,j] for j in 1:2) for i in r1idx) ==  4
        sum(sum(picks[i,j] for j in 1:2) for i in r2idx) ==  2
        sum(sum(picks[i,j] for j in 1:2) for i in r3idx) ==  1

        # Constraint 3 - can only pick one team per game
        sum(picks[:,j] for j in 1:2) .<=1

        # Constraint 4 - can't pick teams eliminated in prior rounds
        # ????
        
    end

    # Solve it
    status = solve(m)
    picked = getvalue(picks)
    points = getobjectivevalue(m)
    return picked,points
end

The output is

│ Row │ team1 │ team2 │ round_face │ game_number │ picked1 │ picked2 │
│     │ Int64 │ Int64 │ Int64      │ Int64       │ Bool    │ Bool    │
├─────┼───────┼───────┼────────────┼─────────────┼─────────┼─────────┤
│ 1   │ 7     │ 2     │ 1          │ 1           │ true    │ false   │
│ 2   │ 6     │ 3     │ 1          │ 2           │ false   │ true    │
│ 3   │ 1     │ 8     │ 1          │ 3           │ false   │ true    │
│ 4   │ 5     │ 4     │ 1          │ 4           │ false   │ true    │
│ 5   │ 7     │ 6     │ 2          │ 5           │ false   │ false   │
│ 6   │ 7     │ 3     │ 2          │ 5           │ false   │ false   │
│ 7   │ 6     │ 2     │ 2          │ 5           │ false   │ false   │
│ 8   │ 2     │ 3     │ 2          │ 5           │ true    │ false   │
│ 9   │ 1     │ 5     │ 2          │ 6           │ false   │ false   │
│ 10  │ 1     │ 4     │ 2          │ 6           │ false   │ false   │
│ 11  │ 8     │ 5     │ 2          │ 6           │ false   │ false   │
│ 12  │ 8     │ 4     │ 2          │ 6           │ true    │ false   │
│ 13  │ 7     │ 1     │ 3          │ 7           │ false   │ false   │
│ 14  │ 7     │ 8     │ 3          │ 7           │ false   │ false   │
│ 15  │ 7     │ 5     │ 3          │ 7           │ true    │ false   │
│ 16  │ 7     │ 4     │ 3          │ 7           │ false   │ false   │
│ 17  │ 6     │ 1     │ 3          │ 7           │ false   │ false   │
│ 18  │ 6     │ 8     │ 3          │ 7           │ false   │ false   │
│ 19  │ 6     │ 5     │ 3          │ 7           │ false   │ false   │
│ 20  │ 6     │ 4     │ 3          │ 7           │ false   │ false   │
│ 21  │ 2     │ 1     │ 3          │ 7           │ false   │ false   │
│ 22  │ 2     │ 8     │ 3          │ 7           │ false   │ false   │
│ 23  │ 2     │ 5     │ 3          │ 7           │ false   │ false   │
│ 24  │ 2     │ 4     │ 3          │ 7           │ false   │ false   │
│ 25  │ 3     │ 1     │ 3          │ 7           │ false   │ false   │
│ 26  │ 3     │ 8     │ 3          │ 7           │ false   │ false   │
│ 27  │ 3     │ 5     │ 3          │ 7           │ false   │ false   │
│ 28  │ 3     │ 4     │ 3          │ 7           │ false   │ false   │

and the issue is that, in game 7, the solver is picking from a match-up of team 5 and team 7 (see row 15 above), but team 5 was picked to lose in round 1 (see row 4) and team 7 was picked to win in round 1 but ignored as a participant in round 2.

I think the constraint would have to look something like

sum(picks[i,1] for i in index_of_team7_round_1) + 
sum(picks[i,2] for i in index_of_team7_round_1) 
 .<=
sum(picks[i,1] for i in index_of_team7_round_2) + 
sum(picks[i,2] for i in index_of_team7_round_2);

sum(picks[i,1] for i in index_of_team7_round_2) + 
sum(picks[i,2] for i in index_of_team7_round_2) 
 .<=
sum(picks[i,1] for i in index_of_team7_round_3) + 
sum(picks[i,2] for i in index_of_team7_round_3);

I was wondering if anyone has encountered a similar programming challenge before and has any ideas on how best to implement this? The approaches I’ve tried in the past haven’t worked.

2

I did not read your whole code, or understand what you are trying to do (if the results of the individual matches are already there, isn’t the winner determined? why solve an optimization model?) but here are two suggestions:

The Linear Ordering Problem has been used to find a ranking of a set of teams that is maximally compatible with pairwise match results.

If your pick variables have an index t for the team as well as r for the round, then you could ask for pick[t,r] >= pick[t,r+1]. That is, t can only be picked in round r+1 when it was picked in r.

3

Thanks for the tips!

The fact that the results are already there doesn’t make much difference to what I’m trying to do, but the idea is to simulate a bunch of different tournaments and see which team is picked the most.

This looks like a promising avenue. Thanks for taking the time to give feedback!