如何用CP-SAT求解器解锁组合优化难题？7个实战案例+3步建模法

在生产排程、物流配送和资源分配等场景中，我们经常面临这样的挑战：如何在有限资源下做出最优决策？这类问题被称为组合优化问题，而约束规划（Constraint Programming）正是解决这类问题的强大工具。Google OR-Tools中的CP-SAT求解器就像一位智能规划师，能够高效处理复杂约束条件，找到最优解决方案。本文将带你从零开始掌握CP-SAT，用实战案例展示如何将它应用到实际业务中。

💡 5分钟环境部署：让智能规划师上线

要启用CP-SAT求解器，只需通过Python包管理器完成安装：

pip install ortools

这条命令会自动配置好所有依赖，包括求解器核心引擎和Python API。安装完成后，你可以通过导入cp_model模块来验证环境是否就绪：

from ortools.sat.python import cp_model
print("CP-SAT求解器已就绪！")

📌 3步建模法：把业务问题转化为数学语言

第1步：定义决策变量

就像规划师需要知道有哪些选项可供选择，建模首先要确定问题中的变量。这些变量可以是布尔型（是/否选择）、整数型（数量多少）或区间型（时间范围）。

第2步：设置约束条件

约束条件是问题的规则边界，比如资源上限、时间冲突或逻辑关系。CP-SAT支持丰富的约束类型，从简单的数值比较到复杂的逻辑表达式。

第3步：定义优化目标

明确你想要最大化（如利润）还是最小化（如成本）的目标函数，求解器会在满足约束的前提下找到最优解。

🔍 7大应用场景深度拆解

场景1：背包问题——有限空间的价值最大化

假设你是一位准备登山的探险家，背包容量2000克，面对一堆重量和价值不同的装备，如何选择才能带走最大价值的物品？

# 导入CP-SAT模型构建工具
from ortools.sat.python import cp_model

# 定义装备数据：重量(克)和价值评分
equipment_weights = [395, 658, 113, 185, 336, 494, 294]
equipment_values = [71, 15, 100, 37, 77, 28, 71]
backpack_capacity = 2000  # 背包最大承重

# 创建模型实例，相当于规划师的记事本
solver_model = cp_model.CpModel()

# 创建决策变量：每个装备是否携带(1=携带, 0=不携带)
selection_vars = [solver_model.new_bool_var(f"equip_{i}") 
                 for i in range(len(equipment_weights))]

# 添加约束：总重量不超过背包容量
solver_model.add(sum(sel * weight for sel, weight 
                    in zip(selection_vars, equipment_weights)) <= backpack_capacity)

# 设置目标：最大化携带装备的总价值
solver_model.maximize(sum(sel * value for sel, value 
                         in zip(selection_vars, equipment_values)))

# 启动求解器，相当于规划师开始计算
solver = cp_model.CpSolver()
result_status = solver.solve(solver_model)

# 输出结果
if result_status == cp_model.OPTIMAL:
    selected = [i for i, var in enumerate(selection_vars) if solver.value(var)]
    print(f"最优选择: {selected}")
    print(f"总价值: {solver.objective_value}")

场景2：车辆路径规划——物流配送的最短路径

当物流公司需要给多个客户配送货物时，如何规划车辆行驶路线才能使总里程最短？这就是典型的CVRP（ capacitated vehicle routing problem）问题。

通过CP-SAT的回路约束（circuit constraint），可以轻松实现对路径的建模，确保车辆从 depot 出发并返回，且不超过负载 capacity。

🚀 进阶技巧：让求解器跑得更快

参数调优三板斧

1. solver.parameters.max_time_in_seconds = 30：设置最大求解时间
2. solver.parameters.log_search_progress = True：开启搜索过程日志
3. solver.parameters.num_search_workers = 4：启用多线程搜索

增量求解策略

对于动态变化的问题（如订单实时增减），可以通过保存中间状态，只重新计算变化部分，大幅提升效率。

🔍 延伸学习：

• 官方文档：chapters/04_modelling.md
• 高级案例：examples/cvrp/
• 性能测试：evaluations/tsp/