Java中如何用Google OR-Tools设置特定数组约束（员工课程分配）

问题建模 #

核心要素定义：

• 决策变量：x[e][c1][c2]（布尔变量），代表员工e是否选择课程组合(c1, c2)
• 目标函数：最大化所有员工所选课程组合的评分总和，即 Σ(x[e][c1][c2] * a[e][c1][c2])，其中a[e][c1][c2]为员工e对课程c1和c2的评分总和
• 约束条件：
  1. 每位员工必须且只能选择一组两门课程
  2. 每门课程的总参与人数（作为第一门课+作为第二门课的员工数）需处于10-30之间
  3. 可选约束：员工不能选择同一门课程两次（若业务规则不允许重复选课）

Java 实现代码示例 #

使用Google OR-Tools的CP-SAT求解器（适配整数规划类问题）：

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

public class CourseAssignment {
    public static void main(String[] args) {
        Loader.loadNativeLibraries();

        // 自定义参数：员工总数、课程总数
        int numEmployees = 100;
        int numCourses = 20;
        // 三维评分数组（实际需根据业务数据填充）
        int[][][] a = new int[numEmployees][numCourses][numCourses];
        // TODO: 填充a数组的实际评分数据

        CpModel model = new CpModel();
        // 创建决策变量集合
        IntVar[][][] x = new IntVar[numEmployees][numCourses][numCourses];
        for (int e = 0; e < numEmployees; e++) {
            for (int c1 = 0; c1 < numCourses; c1++) {
                for (int c2 = 0; c2 < numCourses; c2++) {
                    // 若员工e无法参与c1或c2课程，可直接跳过变量创建（减少计算量）
                    x[e][c1][c2] = model.newBoolVar(String.format("x_%d_%d_%d", e, c1, c2));
                }
            }
        }

        // 约束1：每位员工仅选一组课程
        for (int e = 0; e < numEmployees; e++) {
            LinearExpr sum = LinearExpr.newBuilder();
            for (int c1 = 0; c1 < numCourses; c1++) {
                for (int c2 = 0; c2 < numCourses; c2++) {
                    sum.addTerm(x[e][c1][c2], 1);
                }
            }
            model.addEquality(sum, 1);
        }

        // 约束2：每门课程参与人数控制在10-30之间
        for (int c = 0; c < numCourses; c++) {
            LinearExpr totalParticipants = LinearExpr.newBuilder();
            // 统计选c作为第一门课的员工数
            for (int e = 0; e < numEmployees; e++) {
                for (int c2 = 0; c2 < numCourses; c2++) {
                    totalParticipants.addTerm(x[e][c][c2], 1);
                }
            }
            // 统计选c作为第二门课的员工数
            for (int e = 0; e < numEmployees; e++) {
                for (int c1 = 0; c1 < numCourses; c1++) {
                    totalParticipants.addTerm(x[e][c1][c], 1);
                }
            }
            model.addGreaterOrEqual(totalParticipants, 10);
            model.addLessOrEqual(totalParticipants, 30);
        }

        // 可选约束：禁止员工选择同一门课两次
        for (int e = 0; e < numEmployees; e++) {
            for (int c = 0; c < numCourses; c++) {
                model.addEquality(x[e][c][c], 0);
            }
        }

        // 设置目标函数：最大化总评分
        LinearExpr objective = LinearExpr.newBuilder();
        for (int e = 0; e < numEmployees; e++) {
            for (int c1 = 0; c1 < numCourses; c1++) {
                for (int c2 = 0; c2 < numCourses; c2++) {
                    objective.addTerm(x[e][c1][c2], a[e][c1][c2]);
                }
            }
        }
        model.maximize(objective);

        // 运行求解器
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.solve(model);

        // 输出结果
        if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
            System.out.println("总评分最大值：" + solver.objectiveValue());
            for (int e = 0; e < numEmployees; e++) {
                for (int c1 = 0; c1 < numCourses; c1++) {
                    for (int c2 = 0; c2 < numCourses; c2++) {
                        if (solver.value(x[e][c1][c2]) == 1) {
                            System.out.printf("员工%d 分配课程：%d 和 %d\n", e, c1, c2);
                            break;
                        }
                    }
                }
            }
        } else {
            System.out.println("未找到可行解");
        }
    }
}

关键说明 #

• 变量过滤：若存在员工无法参与的课程组合，创建变量时可直接跳过，减少求解器计算负载
• 灵活约束：若允许课程不开设（即参与人数可为0，但开设则需满足10-30人），可引入布尔变量标记课程状态，关联约束为isCourseOpen[c] * 10 <= totalParticipants[c] <= isCourseOpen[c] *30
• 性能优化：当员工/课程数量较大时，可通过预过滤无效组合、分组处理等方式压缩问题规模

内容的提问来源于stack exchange，提问作者Joachim Rode