CP-SAT Primer TDD实战优化问题的测试驱动开发——手把手搭建护士排班系统【免费下载链接】cpsat-primerThe CP-SAT Primer: Using and Understanding Google OR-Tools CP-SAT Solver项目地址: https://gitcode.com/gh_mirrors/cp/cpsat-primer在 cpsat-primer 开源项目中CP-SAT Primer 用测试驱动开发TDD的方式教你构建 CP-SAT 求解器的护士排班系统Nurse Rostering Problem。本文将手把手带你走完整条流程先用 Pydantic 定义数据模式再写独立的校验函数然后用测试先行的方式一步步实现约束模块最终组合出一个可维护、可扩展的 CP-SAT 护士排班求解器。为什么优化问题需要 TDD教科书式的做法是写数学模型 → 翻译成代码 → 跑通样例。简单问题这样完全够用但真实业务中的排班问题往往约束不断新增、需求反复变更单体大模型很快会变成只有作者本人看得懂的技术债一个隐藏的 bug 悄悄排除了优质解且不报任何错无法单独验证某个约束是否正确调试极其痛苦输入数据格式混乱脏数据直接污染求解结果。TDD 的核心思路是先写测试描述什么是合法排班再实现代码让测试通过。每个约束都是一个独立模块可以单独测试、单独替换。护士排班问题3个硬约束 2个软目标本例的排班需求如下类型规则说明 硬约束禁排班护士被明确禁止休假、病假的班次不能排 硬约束班次需求每个班次的护士人数必须达到最低需求 硬约束最短休息同一护士两个班次之间必须满足最小休息时长 软目标偏好满足尽量把护士排到她偏好的班次 软目标优先员工在满足硬约束前提下优先使用正式员工而非外包下面的排班时间轴图展示了这类调度问题的典型可视化效果——红点表示可行时段蓝色方块是最终排定的时间完整章节见 chapters/test_driven_optimization.md。第1步先定义数据模式别急着写算法真实项目里最坑的往往不是算法而是数据。项目用 Pydantic 声明式地定义了输入和输出两份模式examples/tdd/nurserostering/data_schema.pyNurse姓名、偏好班次集合、禁排班次集合、是否正式员工、最小休息时长、偏好权重Shift名称、开始/结束时间、需求人数NurseRosteringInstance护士列表 班次列表并内置校验器保证班次按时间排序、ID 唯一NurseRosteringSolution班次 → 护士列表的映射 目标函数值 时间戳。这样做的好处脏数据在边界就被拦截报错而不是等到求解结果莫名其妙时才排查同时模式本身就是与业务方沟通的共享语言避免时长单位是小时还是分钟这类歧义。第2步写求解器无关的校验函数这是 TDD 的基石在碰 CP-SAT 之前先写一组纯 Python 校验函数examples/tdd/nurserostering/validation.py来回答两个问题assert_solution_is_feasible(...)这个排班方案是否满足所有硬约束objective_value(...)这个方案的目标函数值是多少偏好奖励 外包惩罚这些函数不依赖任何求解器逻辑直白到业务专家也能看懂。它们同时扮演了正式规格说明书的角色——之后无论 CP-SAT 模型怎么改、甚至换成大邻域搜索等元启发式这套校验永远是你的裁判。第3步测试先行逐个实现约束模块项目定义了统一的模块接口ShiftAssignmentModuleexamples/tdd/nurserostering/modules.py每个约束/目标模块只需实现一个build方法往模型里加约束并可返回一个子目标表达式。五个模块分别是模块类型对应测试文件NoBlockedShiftsModule硬约束tests/test_no_blocked_shifts.pyMinTimeBetweenShifts硬约束tests/test_shifts_off.pyDemandSatisfactionModule硬约束tests/test_demand.pyPreferStaffModule软目标tests/test_staff_objective.pyMaximizePreferences软目标tests/test_preferences.py以禁排班约束为例TDD 循环是这样跑的借助cpsat-utils的断言工具with AssertModelInfeasible() as model: nurse_vars NurseDecisionVars(nurse, shifts, model) NoBlockedShiftsModule().build(instance, model, [nurse_vars]) nurse_vars.fix(shifts[0].uid, True) # 强制排到禁排班次 → 应无解先写测试护士没有禁排班次 → 模型应可行通过强制把护士排到禁排班次 → 模型应不可行失败再写实现给每个禁排班次加上x 0测试通过补边界用例把护士排到非禁排班次 → 仍应可行。 测试经验法则先覆盖基本功能再从两侧加差一点就违反的边界用例凡是可能差一的场景都是绝佳测试点。第4步组合模块得到完整求解器所有模块就位后NurseRosteringModelexamples/tdd/nurserostering/solver.py负责总装为每位护士创建决策变量容器NurseDecisionVarsexamples/tdd/nurserostering/nurse_vars.py每个班次一个布尔变量是否排这位护士把各模块的子目标求和后minimize求解后把解抽取回 Pydantic 的NurseRosteringSolution。最终的全量回归测试examples/tdd/tests/test_full_instances.py用了一个真实感很强的实例7 天 × 每天 3 班早/日/夜共 21 个班次8 位护士每人有不同的偏好、禁排和休息时长要求护士身份特征Alice正式偏好早班周日禁排Bob正式偏好夜班Clara正式偏好周末工作日禁排Dan正式无偏好Eve外包偏好日班Frank / Grace正式偏好日班 / 早班Heidi外包无偏好求解出的排班表会优先满足正式员工和偏好例如 D1 早班给了偏好早班的 Alice 和 Grace夜班给了偏好夜班的 Bob——求解后依然调用独立的assert_solution_is_feasible做最终验证。第5步用生产数据沉淀回归测试加上属性测试由于输入输出都是 Pydantic 模型把线上真实案例model_dump_json()存成 JSON就能随时作为回归测试回放——重构时风险降到最低tests/test_full_instances.py就是这么做的。更进一步项目还用了Hypothesis 属性测试examples/tdd/tests/test_hypothesis.py自动生成随机但合法的排班实例10–20 个班次、5–10 位护士断言求解器要么给出能通过独立校验的可行解要么正确报告不可行。失败时 Hypothesis 会自动把反例收缩到最小规模方便复现。这套排班思路也可以拿公开基准来横向对比下图是三个求解器在标准护士排班基准实例NRP Instance 19上的目标函数下降曲线CP-SAT 在最短时间内逼近了下界项目结构速查 文件作用examples/tdd/nurserostering/data_schema.pyPydantic 输入/输出模式examples/tdd/nurserostering/validation.py求解器无关的可行性校验与目标值计算examples/tdd/nurserostering/nurse_vars.py决策变量容器创建、固定、提取解examples/tdd/nurserostering/modules.py5 个约束/目标模块examples/tdd/nurserostering/solver.pyNurseRosteringModel总装与求解examples/tdd/nurserostering/generate_random_instance.py随机实例生成器examples/tdd/tests/pytest 单测 Hypothesis 属性测试chapters/test_driven_optimization.md完整 TDD 章节含全部代码与讲解总结用 TDD 搭建 CP-SAT 护士排班系统的关键收获模式先行Pydantic 定义输入输出脏数据在边界被拦截独立校验不依赖求解器的校验函数 可执行的规格说明书模块化每个约束一个build方法测试驱动逐个点亮回归沉淀生产实例存 JSON Hypothesis 随机实例让重构有底气。这条正确性优先的路线并不总是最快的但对需求持续演化的排班类问题它换来的是可维护性和对结果真正的信心。想深入可以直接阅读项目的 TDD 章节 并跑一遍examples/tdd/下的测试。【免费下载链接】cpsat-primerThe CP-SAT Primer: Using and Understanding Google OR-Tools CP-SAT Solver项目地址: https://gitcode.com/gh_mirrors/cp/cpsat-primer创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考