# Google OR-Tools - 组合优化 OR-Tools 为困难的组合问题提供了专门的求解器。它皇冠上的宝石是 CP-SAT 求解器，它使用约束编程和可满足性技术来找到调度和资源分配问题的最佳解决方案，而这对于标准线性求解器来说是不可能的。 ## 何时使用 * **车辆路线 (VRP)**：寻找车队运送货物的最佳路径。 * **日程安排**：创建轮班表、项目时间表或作业车间时间表。 * **装箱** ：将不同尺寸的物体放入有限数量的箱子中。 * **背包问题**：选择物品以在重量限制内最大化价值。 * **线性规划（LP）**：具有连续变量的标准资源分配。 * **整数编程 (MIP)**：变量必须为整数的优化（例如，“要购买的机器数量”）。 * **网络流量**：计算图表中的最大流量或最小成本。 ## 参考文档 **官方文档**： **GitHub**： **搜索模式**：`cp_model.CpModel`、`pywraplp.Solver`、`routing_enums_pb2`、`AddConstraint` ## 核心原则 ### 建模与求解 OR-Tools 将问题的**定义**（变量、约束、目标）与**求解器**引擎分开。您构建一个模型，然后将其传递给求解器实例。 ### CP-SAT（约束规划）最现代、最推荐的离散问题求解器。 **重要说明**：CP-SAT 仅适用于整数。如果您有浮点数（例如“0.5”），则必须对其进行缩放（例如，乘以 100 并使用整数）。 ### 状态代码解决后，请务必检查状态。它可以是“OPTIMAL”、“FEASIBLE”（找到的解决方案，但可能不是最好的）、“INFEASIBLE”（不可能解决）或“LIMIT_REACHED”。 ## 快速参考 ### 安装 pip 安装或工具 ### 标准导入从 ortools.sat.python 导入 cp_model 从 ortools.linear_solver 导入 pywraplp 从 ortools.constraint_solver 导入routing_enums_pb2 从 ortools.constraint_solver 导入 pywrapcp ### 基本模式 - CP-SAT 求解器（整数逻辑）从 ortools.sat.python 导入 cp_model # 1.创建模型模型 = cp_model.CpModel() # 2. 定义变量：NewIntVar(lower_bound, upper_bound, name) x = model.NewIntVar(0, 10, 'x') y = model.NewIntVar(0, 10, 'y') # 3.添加约束模型.Add(x + y <= 8) 模型.Add(x > 2) # 4. 定义目标模型.最大化(x + 2 * y) # 5. 解决求解器 = cp_model.CpSolver() 状态 = 求解器.Solve(模型) 如果状态== cp_model.OPTIMAL： print(f'x = {solver.Value(x)}, y = {solver.Value(y)}') ## 关键规则 ### ✅ 做 * **使用 CP-SAT 处理离散任务** \- 对于调度和逻辑繁重的问题，它比 MIP 求解器快得多。 * **缩放浮点数** \- 由于 CP-SAT 是一个整数求解器，请将“1.25”转换为“125”并调整逻辑。 * **首先检查状态** \- 如果状态为“INFEASIBLE”，则切勿访问变量值。 * **使用 AddElement 进行索引** \- 要使用变量作为数组中的索引，请使用专门的约束 `model.AddElement`。 * **设置时间限制** \- 对于复杂问题，使用 `solver.parameters.max_time_in_seconds = 60.0` 在一分钟内获得最佳解决方案。 * **使用 Value() 验证** \- 使用 `solver.Value(var)` 访问结果，而不是变量对象本身。 ### ❌不要 * **如果在约束中，请勿使用 Python ** \- 您不能使用 `if x > 5: model.Add(...)`。使用布尔含义（`OnlyEnforceIf`）。 * **不要使用非线性数学** \- CP-SAT 和 LP 求解器不支持 `x * y` （其中两者都是变量）或 `sin(x)`。对于“x * y”，您需要专门的线性化或分段近似。 * **避免巨大的域** \- 定义范围为 0 到 1,000,000,000 的变量会减慢求解器的速度。尽可能缩小界限。 ## 反模式（从不）从 ortools.sat.python 导入 cp_model # ❌ 不好：在模型中使用标准 Python 逻辑 # ifsolver.Value(x) > 5: # ❌Value()在建模过程中不可用！ # 模型.Add(y == 1) # ✅ GOOD：条件约束（逻辑蕴涵） b = model.NewBoolVar('b') model.Add(x > 5).OnlyEnforceIf(b) model.Add(x <= 5).OnlyEnforceIf(b.Not()) model.Add(y == 1).OnlyEnforceIf(b) # ❌ 不好：CP-SAT 中的浮点变量 # x = model.NewIntVar(0, 1.5, 'x') # ❌ 错误！ # ✅ 好：缩放 # x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150 代表 1.50 ## 线性规划 (pywraplp) ### 资源分配（连续变量）从 ortools.linear_solver 导入 pywraplp # 使用 GLOP 后端创建求解器（Google 线性优化包）求解器 = pywraplp.Solver.CreateSolver('GLOP') # 定义连续变量 x = 求解器.NumVar(0, 求解器.infinity(), 'x') y = 求解器.NumVar(0, 求解器.infinity(), 'y') # 约束：x + 2y <= 14 ct = 求解器.约束(-求解器.无穷大(), 14) ct.SetCoefficient(x, 1) ct.SetCoefficient(y, 2) # 目标：最大化 3x + 4y 目标=solver.Objective() 目标.SetCoefficient(x, 3) 目标.SetCoefficient(y, 4) Objective.SetMaximization() 求解器.Solve() print(f'解: x={x.solution_value()}, y={y.solution_value()}') ## 车辆路线（VRP） ### 物流引擎从 ortools.constraint_solver 导入routing_enums_pb2 从 ortools.constraint_solver 导入 pywrapcp defsolve_vrp(): # 1.距离矩阵（位置之间的距离）数据 = {'距离矩阵': [[0, 10, 20], [10, 0, 15], [20, 15, 0]], 'num_vehicles': 1, '车厂': 0} # 2. 设置索引管理器和路由模型 manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), 数据['num_vehicles'], 数据['depot']) 路由= pywrapcp.RoutingModel（经理） # 3. 创建距离回调 def distance_callback(from_index, to_index): 返回数据['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)] Transit_callback_index = 路由.RegisterTransitCallback(distance_callback) 路由.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 4. 解决 search_parameters = pywrapcp.DefaultRoutingSearchParameters() 搜索参数.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) 解决方案=路由.SolveWithParameters(search_parameters) 返回解决方案 ## 约束编程：调度 ### Job-Shop 示例（具有依赖关系的任务）模型 = cp_model.CpModel() # 定义一个间隔变量（开始、持续时间、结束）持续时间 = 10 start_var = model.NewIntVar(0, 100, '开始') end_var = model.NewIntVar(0, 100, '结束') Interval_var = model.NewIntervalVar(start_var, 持续时间, end_var, '间隔') # 无重叠约束（机器一次只能执行一项任务） model.AddNoOverlap([interval_var1,interval_var2,interval_var3]) ## 实际工作流程 ### 1\.员工轮班安排 defsolve_shifts(num_employees, num_days, shifts_per_day): 模型 = cp_model.CpModel() 班次 = {} 对于范围内的 e(num_employees)：对于 d 在范围内（num_days）：对于范围内的 s(shifts_per_day)：移位[(e, d, s)] = model.NewBoolVar(f'shift_e{e}d{d}s{s}') # 约束：每个班次只分配给一名员工对于 d 在范围内（num_days）：对于范围内的 s(shifts_per_day)： model.Add(sum(shifts[(e, d, s)] for e in range(num_employees)) == 1) # 限制：每位员工每天最多工作一班对于范围内的 e(num_employees)：对于 d 在范围内（num_days）： model.Add(sum(shifts[(e, d, s)] for s in range(shifts_per_day)) <= 1) 求解器 = cp_model.CpSolver() 状态 = 求解器.Solve(模型) 返回班次，求解器 ### 2\.多背包（将物品装入垃圾箱） def bin_packing(物品, bin_capacities): 模型 = cp_model.CpModel() # x[i, j] = 1 如果项目 i 在 bin j 中 x = {} 对于范围内的 i(len(items))：对于范围内的 j(len(bin_capacities))： x[i, j] = model.NewBoolVar(f'x_{i}_{j}') # 每件物品都在一个箱子中对于范围内的 i(len(items))： model.Add(sum(x[i, j] for j in range(len(bin_capacities))) == 1) # Bin容量限制对于范围内的 j(len(bin_capacities))： model.Add(sum(x[i, j] * items[i] for i in range(len(items))) <= bin_capacities[j]) ## 性能优化 ### 提示（热启动）如果您有一个好的初始猜测，请将其提供给求解器以加快搜索速度。模型.AddHint(x, 5) 模型.AddHint(y, 2) ### 并行求解 CP-SAT 可以使用多个线程来探索搜索树的不同部分。求解器 = cp_model.CpSolver() solver.parameters.num_search_workers = 8 # 使用8个CPU核心 ## 常见陷阱和解决方案 ### 浮点数学错误如前所述，OR-Tools CP-SAT 是严格整数。 # ❌问题：model.Add(x * 0.1 <= 5) # ✅ 解决方案： model.Add(x <= 50) # 两边都乘以 10 ### 不可行的模型如果 `solver.Solve(model)` 返回 `INFEASIBLE`，则意味着您的约束是矛盾的。 # ✅ 解决方案：使用“充分假设”或“约束松弛” # 确定哪个约束导致了冲突。 ### 对称性如果项目 A 和 B 相同，则求解器将浪费时间检查“A 在 Bin 1 中，B 在 Bin 2 中”和“B 在 Bin 1 中，A 在 Bin 2 中”。 # ✅ 解决方案：添加对称破缺约束 # model.Add(x_A <= x_B) # 强制排序 ## 最佳实践 1. **在访问变量值之前始终检查求解器状态** 2. **使用 CP-SAT 时将浮点值**缩放为整数 3. **为复杂问题设定时间限制**，以便快速获得可行的解决方案 4. **使用适当的求解器** \- CP-SAT 用于离散，GLOP 用于连续 LP 5. **在具有相同变量的模型中打破对称性**以加快求解速度 6. **尽可能缩小变量域**以获得更好的性能 7. **当您有良好的初步猜测时使用提示** 8. **启用大型问题的并行求解**（如果可用） 9. **通过检查约束是否满足来验证解决方案** 10. **记录你的模型** \- 变量名称和约束逻辑 Google OR-Tools 是优化世界的重型机械。它解决了推动全球物流、航班调度和制造的离散难题，将不可能的“试错”转化为数学确定性。

或工具

包含技能