brand new dev here, long time software product owner and designer.
I am creating a scheduling algorithm for scheduling polo games. There are a few user inputs and some game constraints that will also come from the app. Essentially a polo game is made up of rounds called Chukkers, and each round should have a certain number of players per team based on the size of the playing field/arena. When players opt in to play, they may opt in to play any number of chukkers, generally between 1-6 total. Many players will opt in, with varying desiredChukkers. Team matches for each Chukker must be balanced in terms of total team handicap (for fair play) and also for containing defaultNumberOfPlayers per team.
I have set this up in CP SAT with Google's OR-Tools.
Variables :
defaultPlayersPerTeam : 4
numberOfTeams: 2
desiredChukkers - varies per player object
maxChukkerColumns - calculating a max number of Chukker Columns to fascilitate in creating the grid ((int maxChukkerColumns = (int) Math.ceil((double) totalDesiredChukkers / defaultPlayersPerTeam);))
I have some methods that initially set up balancedTeams, that assigns team using a TeamID in each player object. The teams are balanced in terms of total number of requested chukkers and handicap, so that the initial data going into the solver is optimized from the start.
Ideally, the solver is outputting a schedule of chukker assignments that respects each player's desiredChukker count and arranges those chukkers across a schedule grid of chukker columns optimizing the number of chukker rounds with defaultplayersperteam, and ideally balances each chukker's team handicaps as much as possible. Note that as I am having difficulty with the desiredChukkers vs defaultPlayersPerTeam, I am not adding any handicap balancing to the solver just yet. Any leftover assignments would be in a chukker or two consecutive to the at-capacity chukkers.
Player (Desired Chk) Chukker 1 Chukker 2 Chukker 3 Chukker 4 Chukker 5
Team 1
Player 5 (4) X
Player 1 (1) X X
Player 2 (2) X X X
Player 4 (4) X X X X
Player 9 (4) X X X X
Player 3 (3) X X X X
Team 2
Player 6 (4) X X X X
Player 7 (4) X X X X
Player 8 (4) X X X X
Player 10 (4) X X X X
The above representation is what I am trying to get to.
I am having what seems to be an inherent problem with the cp model itself - if I add desiredChukkers are a direct constraint, the model does not respect the values, even when heavily weighted. If I add the desiredChukkers as an immutable value and feed the assignments into the solver, I get a no solution feasible result. It seems as though the model doesn't know that it can re-arrange the chukkers across the chukker columns, and I have tried endlessly to inform it, with only those two results, infeasibility or loss of desiredChukkers count integrity.
This is what the method looks like, this returns infeasible :
public SolverResult createInitialPlayerAssignments(List<Player> players, int maxChukkerColumns, int defaultPlayersPerTeam) {
CpSolver playerAssignmentsSolver = new CpSolver();
CpModel model = new CpModel();
// Initialize player assignment variables
IntVar[][] playerAssignments = new IntVar[players.size()][maxChukkerColumns];
System.out.println("playerAssignments array initialized with dimensions: " +
maxChukkerColumns + "x" + players.size());
// Pre-assign chukkers for each player according to their desired number
for (Player player : players) {
int desiredChukkers = player.getDesiredChukkers();
for (int c = 0; c < maxChukkerColumns; c++) {
if (c < desiredChukkers) {
// Assign the player to this chukker column
playerAssignments[player.getIndex()][c] = model.newIntVar(1, 1, "Player" + player.getIndex() + "_Chukker" + c);
} else {
// Do not assign the player to this chukker column
playerAssignments[player.getIndex()][c] = model.newIntVar(0, 0, "Player" + player.getIndex() + "_Chukker" + c);
}
}
}
// Initialize Boolean variables for full chukkers
BoolVar[] isFullChukker = new BoolVar[maxChukkerColumns];
for (int c = 0; c < maxChukkerColumns; c++) {
isFullChukker[c] = model.newBoolVar("full_chukker_" + c);
}
// Add constraints for full chukkers
for (int c = 0; c < maxChukkerColumns; c++) {
LinearExprBuilder totalPlayersInChukker = LinearExpr.newBuilder();
for (int p = 0; p < players.size(); p++) {
// Since playerAssignments is [players.size()][maxChukkerColumns], p and c will always be in bounds
totalPlayersInChukker.add(playerAssignments[p][c]);
}
model.addLessOrEqual(totalPlayersInChukker.build(), defaultPlayersPerTeam * numberOfTeams);
model.addGreaterOrEqual(totalPlayersInChukker.build(), defaultPlayersPerTeam * numberOfTeams).onlyEnforceIf(isFullChukker[c]);
}
// Objective: Maximize the number of full chukkers
model.maximize(LinearExpr.sum(isFullChukker));
// Solve the model
CpSolverStatus status = playerAssignmentsSolver.solve(model);
If helpful, below is my output, with details from the methods not shown that formulate teams prior to this createInitialPlayerAssignmentsMethod :
setNumberOfTeams called with value: 2
Before sorting by handicap:
Player: Player 1, Handicap: 0, Desired Chukkers: 1
Player: Player 2, Handicap: 0, Desired Chukkers: 2
Player: Player 3, Handicap: 3, Desired Chukkers: 3
Player: Player 4, Handicap: 1, Desired Chukkers: 4
Player: Player 5, Handicap: -1, Desired Chukkers: 4
Player: Player 6, Handicap: 0, Desired Chukkers: 4
Player: Player 7, Handicap: 0, Desired Chukkers: 4
Player: Player 8, Handicap: 1, Desired Chukkers: 4
Player: Player 9, Handicap: 1, Desired Chukkers: 4
Player: Player 10, Handicap: 1, Desired Chukkers: 4
After sorting by handicap:
Player: Player 5, Handicap: -1, Desired Chukkers: 4
Player: Player 1, Handicap: 0, Desired Chukkers: 1
Player: Player 2, Handicap: 0, Desired Chukkers: 2
Player: Player 6, Handicap: 0, Desired Chukkers: 4
Player: Player 7, Handicap: 0, Desired Chukkers: 4
Player: Player 4, Handicap: 1, Desired Chukkers: 4
Player: Player 8, Handicap: 1, Desired Chukkers: 4
Player: Player 9, Handicap: 1, Desired Chukkers: 4
Player: Player 10, Handicap: 1, Desired Chukkers: 4
Player: Player 3, Handicap: 3, Desired Chukkers: 3
Player Index: 0, Name: Player 5, Handicap: -1, Desired Chukkers: 4, Assigned to Team: 0
Player Index: 1, Name: Player 1, Handicap: 0, Desired Chukkers: 1, Assigned to Team: 0
Player Index: 2, Name: Player 2, Handicap: 0, Desired Chukkers: 2, Assigned to Team: 0
Player Index: 3, Name: Player 6, Handicap: 0, Desired Chukkers: 4, Assigned to Team: 1
Player Index: 4, Name: Player 7, Handicap: 0, Desired Chukkers: 4, Assigned to Team: 1
Player Index: 5, Name: Player 4, Handicap: 1, Desired Chukkers: 4, Assigned to Team: 0
Player Index: 6, Name: Player 8, Handicap: 1, Desired Chukkers: 4, Assigned to Team: 1
Player Index: 7, Name: Player 9, Handicap: 1, Desired Chukkers: 4, Assigned to Team: 0
Player Index: 8, Name: Player 10, Handicap: 1, Desired Chukkers: 4, Assigned to Team: 1
Player Index: 9, Name: Player 3, Handicap: 3, Desired Chukkers: 3, Assigned to Team: 0
After assigning players to teams:
Team: 0
Player: Player 5, Handicap: -1, Desired Chukkers: 4, Index: 0
Player: Player 1, Handicap: 0, Desired Chukkers: 1, Index: 1
Player: Player 2, Handicap: 0, Desired Chukkers: 2, Index: 2
Player: Player 4, Handicap: 1, Desired Chukkers: 4, Index: 5
Player: Player 9, Handicap: 1, Desired Chukkers: 4, Index: 7
Player: Player 3, Handicap: 3, Desired Chukkers: 3, Index: 9
Team: 1
Player: Player 6, Handicap: 0, Desired Chukkers: 4, Index: 3
Player: Player 7, Handicap: 0, Desired Chukkers: 4, Index: 4
Player: Player 8, Handicap: 1, Desired Chukkers: 4, Index: 6
Player: Player 10, Handicap: 1, Desired Chukkers: 4, Index: 8
Before team optimization:
After team optimization:
Team: 0
Player: Player 5, Handicap: -1, Desired Chukkers: 4, Index: 0
Player: Player 1, Handicap: 0, Desired Chukkers: 1, Index: 1
Player: Player 2, Handicap: 0, Desired Chukkers: 2, Index: 2
Player: Player 4, Handicap: 1, Desired Chukkers: 4, Index: 5
Player: Player 9, Handicap: 1, Desired Chukkers: 4, Index: 7
Player: Player 3, Handicap: 3, Desired Chukkers: 3, Index: 9
Team: 1
Player: Player 6, Handicap: 0, Desired Chukkers: 4, Index: 3
Player: Player 7, Handicap: 0, Desired Chukkers: 4, Index: 4
Player: Player 8, Handicap: 1, Desired Chukkers: 4, Index: 6
Player: Player 10, Handicap: 1, Desired Chukkers: 4, Index: 8
allPlayers at updateAllPlayersList : 6
allPlayers at updateAllPlayersList : 10
After final assignment and validation:
Team: 0
Player: Player 5, Handicap: -1, Desired Chukkers: 4, Index: 0
Player: Player 1, Handicap: 0, Desired Chukkers: 1, Index: 1
Player: Player 2, Handicap: 0, Desired Chukkers: 2, Index: 2
Player: Player 4, Handicap: 1, Desired Chukkers: 4, Index: 5
Player: Player 9, Handicap: 1, Desired Chukkers: 4, Index: 7
Player: Player 3, Handicap: 3, Desired Chukkers: 3, Index: 9
Team: 1
Player: Player 6, Handicap: 0, Desired Chukkers: 4, Index: 3
Player: Player 7, Handicap: 0, Desired Chukkers: 4, Index: 4
Player: Player 8, Handicap: 1, Desired Chukkers: 4, Index: 6
Player: Player 10, Handicap: 1, Desired Chukkers: 4, Index: 8
Player: Player 5, Index: 0, Desired Chukkers: 4, Handicap: -1, Team Index: 0
Player: Player 1, Index: 1, Desired Chukkers: 1, Handicap: 0, Team Index: 0
Player: Player 2, Index: 2, Desired Chukkers: 2, Handicap: 0, Team Index: 0
Player: Player 4, Index: 5, Desired Chukkers: 4, Handicap: 1, Team Index: 0
Player: Player 9, Index: 7, Desired Chukkers: 4, Handicap: 1, Team Index: 0
Player: Player 3, Index: 9, Desired Chukkers: 3, Handicap: 3, Team Index: 0
Player: Player 6, Index: 3, Desired Chukkers: 4, Handicap: 0, Team Index: 1
Player: Player 7, Index: 4, Desired Chukkers: 4, Handicap: 0, Team Index: 1
Player: Player 8, Index: 6, Desired Chukkers: 4, Handicap: 1, Team Index: 1
Player: Player 10, Index: 8, Desired Chukkers: 4, Handicap: 1, Team Index: 1
Team 1: Total Handicap = 4, Total Desired Chukkers = 18
Team 2: Total Handicap = 2, Total Desired Chukkers = 16
Numberofteams in TeamFormulation : 2
Number of players: 10
maxchukkercolumn value in VariableSchedule: 9
Numberofteams in DataLoader : 2
playerAssignments array initialized with dimensions: 9x10
No optimal solution found.
Thank you for your expertise!
- amy
I have tried to add the desiredChukkers as a constraint, but unfortunately I can not get the solver to respect the values as immutable. When added as a constraint the values are not respected and are changed, which renders the scheduler results useless.
You have no variables for assignments.
The model has no freedom. Everything is fixed.