OR-Tools CP-SAT 调度约束问题 - Java

问题描述 投票：0回答：1

这里是全新的开发人员，长期的软件产品所有者和设计师。

我正在创建一个用于安排马球比赛的调度算法。还有一些用户输入和一些游戏限制也将来自应用程序。本质上，马球比赛由称为 Chukkers 的回合组成，每个回合应根据比赛场地/竞技场的大小，每队有一定数量的球员。当玩家选择参加比赛时，他们可以选择参加任意数量的回合，通常总共在 1-6 回合之间。许多玩家会选择加入，并有不同的愿望。每个楚克队的球队比赛必须在球队总让分方面保持平衡（为了公平竞争），并且还包含每队的默认球员人数。

我已经使用 Google 的 OR-Tools 在 CP SAT 中进行了设置。

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);))

我有一些最初设置balancedTeams的方法，它使用每个玩家对象中的TeamID来分配团队。各团队在请求的回合总数和障碍方面是平衡的，因此进入求解器的初始数据从一开始就得到优化。

理想情况下，解算器会输出一个 chukker 分配时间表，该时间表尊重每个玩家所需的 Chukker 数量，并将这些 chukker 排列在 chukker 列的时间表网格中，优化每个团队默认玩家的 chukker 轮数，并尽可能平衡每个 chukker 的团队障碍。请注意，由于我在desiredChukkers 与defaultPlayersPerTeam 方面遇到困难，因此我还没有向求解器添加任何障碍平衡。任何剩余的作业都将位于一个或两个连续的小组中。

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

上述表示是我想要达到的目的。

我遇到了 cp 模型本身的固有问题 - 如果我添加desiredChukkers 是直接约束，则模型不尊重这些值，即使权重很大时也是如此。如果我将desiredChukkers添加为不可变值并将分配输入求解器，我会得到无解可行的结果。似乎该模型不知道它可以在 chukkers 列上重新排列 chukkers，并且我一直在尝试告知它，只有这两个结果，不可行或丢失所需的 Chukkers 计数完整性。

这就是该方法的样子，这返回不可行：

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);

如果有帮助，下面是我的输出，其中包含在此之前制定团队的方法的详细信息（未显示）

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.

感谢您的专业知识！

  • 艾米

我尝试添加desiredChukkers作为约束，但不幸的是我无法让求解器将这些值视为不可变。当作为约束添加时，这些值不受尊重并被更改，这使得调度程序结果毫无用处。

java constraints scheduler or-tools cp-sat
1个回答
0
投票

您没有用于赋值的变量。

        // 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);
                }
            }
        }

模型没有自由度。一切都已确定。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.