ortools

Google OR-Tools - 组合优化

OR-Tools 为复杂的组合问题提供专用求解器。其核心是 CP-SAT 求解器，它利用约束规划和可满足性技术，为标准线性求解器无法处理的调度和资源分配问题寻找最优解。

适用场景

• 车辆路径问题（VRP）：为车队寻找配送货物的最佳路线。
• 调度：制定轮班表、项目时间表或作业车间计划。
• 装箱问题：将不同尺寸的物品装入有限数量的箱子。
• 背包问题：在重量限制内选择物品，使价值最大化。
• 线性规划（LP）：使用连续变量进行常规资源分配。
• 整数规划（MIP）：变量必须为整数的优化问题（例如“要购买的机器数量”）。
• 网络流：计算图中的最大流或最小成本。

参考文档

官方文档：https://developers.google.com/optimization
GitHub：https://github.com/google/or-tools
搜索模式：cp_model.CpModel、pywraplp.Solver、routing_enums_pb2、AddConstraint

核心原则

建模与求解

OR-Tools 将问题的定义（变量、约束、目标）与求解器引擎分开。你先构建模型，再将其传递给求解器实例。

CP-SAT（约束规划）

用于离散问题的最新且推荐的求解器。重要提示：CP-SAT 只支持整数。如果你有浮点数（例如 0.5），必须对其进行缩放（例如乘以 100 并使用整数）。

状态码

求解后，务必检查状态。状态可能为 OPTIMAL、FEASIBLE（找到了解，但可能不是最优解）、INFEASIBLE（问题无解）或 LIMIT_REACHED。

快速参考

安装

pip install ortools

常规导入

from ortools.sat.python import cp_model
from ortools.linear_solver import pywraplp
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

基本模式 - CP-SAT 求解器（整数逻辑）

from ortools.sat.python import cp_model

# 1. Create the model
model = cp_model.CpModel()

# 2. Define variables: NewIntVar(lower_bound, upper_bound, name)
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')

# 3. Add constraints
model.Add(x + y <= 8)
model.Add(x > 2)

# 4. Define Objective
model.Maximize(x + 2 * y)

# 5. Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == 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 - 不能使用 if x > 5: model.Add(...)。请使用布尔蕴含（OnlyEnforceIf）。
• 不要使用非线性数学 - CP-SAT 和 LP 求解器不支持 x * y（其中 x 和 y 都是变量）或 sin(x)。对于 x * y，需要使用专门的线性化方法或分段近似。
• 避免过大的取值范围 - 将变量范围设为 0 到 1,000,000,000 会拖慢求解器。应尽可能缩小上下界。

反模式（绝不要这样做）

from ortools.sat.python import cp_model

# ❌ BAD: Using standard Python logic inside the model
# if solver.Value(x) > 5: # ❌ Value() is not available during modeling!
#     model.Add(y == 1)

# ✅ GOOD: Conditional constraints (Logical Implication)
b = model.NewBoolVar('b')
model.Add(x > 5).OnlyEnforceIf(b)
model.Add(x <= 5).OnlyEnforceIf(b.Not())
model.Add(y == 1).OnlyEnforceIf(b)

# ❌ BAD: Floating point variables in CP-SAT
# x = model.NewIntVar(0, 1.5, 'x') # ❌ Error!

# ✅ GOOD: Scaling
# x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150 represents 1.50

线性规划（pywraplp）

资源分配（连续变量）

from ortools.linear_solver import pywraplp

# Create solver with GLOP backend (Google Linear Optimization Package)
solver = pywraplp.Solver.CreateSolver('GLOP')

# Define continuous variables
x = solver.NumVar(0, solver.infinity(), 'x')
y = solver.NumVar(0, solver.infinity(), 'y')

# Constraint: x + 2y <= 14
ct = solver.Constraint(-solver.infinity(), 14)
ct.SetCoefficient(x, 1)
ct.SetCoefficient(y, 2)

# Objective: Maximize 3x + 4y
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()

solver.Solve()
print(f'Solution: x={x.solution_value()}, y={y.solution_value()}')

车辆路径问题（VRP）

物流引擎

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_vrp():
    # 1. Distance Matrix (distance between locations)
    data = {'distance_matrix': [[0, 10, 20], [10, 0, 15], [20, 15, 0]],
            'num_vehicles': 1, 'depot': 0}
    
    # 2. Setup Index Manager and Routing Model
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)
    
    # 3. Create Distance Callback
    def distance_callback(from_index, to_index):
        return data['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # 4. Solve
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    return solution

约束规划：调度

作业车间示例（有依赖关系的任务）

model = cp_model.CpModel()

# Define an Interval Variable (Start, Duration, End)
duration = 10
start_var = model.NewIntVar(0, 100, 'start')
end_var = model.NewIntVar(0, 100, 'end')
interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval')

# No-overlap constraint (Machines can only do one task at a time)
model.AddNoOverlap([interval_var1, interval_var2, interval_var3])

实用工作流

1. 员工轮班排班

def solve_shifts(num_employees, num_days, shifts_per_day):
    model = cp_model.CpModel()
    shifts = {}
    for e in range(num_employees):
        for d in range(num_days):
            for s in range(shifts_per_day):
                shifts[(e, d, s)] = model.NewBoolVar(f'shift_e{e}d{d}s{s}')
                
    # Constraint: Each shift is assigned to exactly one employee
    for d in range(num_days):
        for s in range(shifts_per_day):
            model.Add(sum(shifts[(e, d, s)] for e in range(num_employees)) == 1)
            
    # Constraint: Each employee works at most one shift per day
    for e in range(num_employees):
        for d in range(num_days):
            model.Add(sum(shifts[(e, d, s)] for s in range(shifts_per_day)) <= 1)
            
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    return shifts, solver

2. 多重背包问题（将物品装入箱子）

def bin_packing(items, bin_capacities):
    model = cp_model.CpModel()
    # x[i, j] = 1 if item i is in bin j
    x = {}
    for i in range(len(items)):
        for j in range(len(bin_capacities)):
            x[i, j] = model.NewBoolVar(f'x_{i}_{j}')
            
    # Each item in exactly one bin
    for i in range(len(items)):
        model.Add(sum(x[i, j] for j in range(len(bin_capacities))) == 1)
        
    # Bin capacity constraint
    for j in range(len(bin_capacities)):
        model.Add(sum(x[i, j] * items[i] for i in range(len(items))) <= bin_capacities[j])

性能优化

提示（热启动）

如果你有一个不错的初始猜测，可以将其提供给求解器以加快搜索。

model.AddHint(x, 5)
model.AddHint(y, 2)

并行求解

CP-SAT 可以使用多个线程探索搜索树的不同部分。

solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 8 # Use 8 CPU cores

常见陷阱与解决方案

浮点数数学错误

如前所述，OR-Tools CP-SAT 严格使用整数。

# ❌ Problem: model.Add(x * 0.1 <= 5)
# ✅ Solution: 
model.Add(x <= 50) # Multiply both sides by 10

无可行解的模型

如果 solver.Solve(model) 返回 INFEASIBLE，就表示你的约束相互矛盾。

# ✅ Solution: Use 'Sufficient Assmptions' or 'Constraint Relaxation'
# to identify which constraint is causing the conflict.

对称性

如果项目 A 和 B 完全相同，求解器会浪费时间，同时检查“A 放在箱子 1 中，B 放在箱子 2 中”和“B 放在箱子 1 中，A 放在箱子 2 中”。

# ✅ Solution: Add symmetry-breaking constraints
# model.Add(x_A <= x_B) # Force an ordering

最佳实践

1. 访问变量值前，始终检查求解器状态
2. 使用 CP-SAT 时，将浮点数缩放为整数
3. 为复杂问题设置时间限制，以便快速获得可行解
4. 选择合适的求解器——离散问题使用 CP-SAT，连续线性规划使用 GLOP
5. 在含有相同变量的模型中打破对称性，以加快求解
6. 尽可能缩小变量的取值范围，以提升性能
7. 有较好的初始猜测时，使用提示
8. 条件允许时，为大型问题启用并行求解
9. 检查约束是否满足，以验证解
10. 记录模型文档——包括变量名称和约束逻辑

Google OR-Tools 是优化领域的重型装备。它能解决驱动全球物流、航空公司排班和制造业的离散难题，将不可能的“反复试错”变为数学上的确定性。