Google OR-Tools 约束求解

bash pip install ortools

推荐使用 Python 3.8+ 版本。安装成功后，可运行以下代码验证：

```python
from ortools.sat.python import cp_model
print("安装成功！")

第一个约束求解程序：数字谜题

考虑一个简单问题：找出三个整数 x、y、z，满足：

• 它们都在 0 到 10 之间
• x + y + z = 15
• x 是 y 的两倍
• 所有变量互不相等

用 OR‑Tools 的实现如下：

from ortools.sat.python import cp_model

# 创建模型
model = cp_model.CpModel()

# 定义三个整数变量，取值范围 0~10
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')
z = model.NewIntVar(0, 10, 'z')

# 添加约束
model.Add(x + y + z == 15)          # 和为 15
model.Add(x == 2 * y)               # x 是 y 的两倍
model.AddAllDifferent([x, y, z])    # 所有变量互不相同

# 创建求解器并求解
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('x =', solver.Value(x))
    print('y =', solver.Value(y))
    print('z =', solver.Value(z))
else:
    print('无解')

逐行解释

• CpModel()：代表一个约束满足/优化问题。
• NewIntVar(lb, ub, name)：创建有界整数变量，lb 与 ub 分别是下界和上界。
• Add() 方法：将一条约束加入模型。支持 +、==、!= 等运算符。
• AddAllDifferent：强制所有变量取值不同，是组合优化中常用约束。
• CpSolver()：CP‑SAT 求解器实例。
• Solve(model)：返回求解状态，可能值为 OPTIMAL、FEASIBLE、INFEASIBLE、MODEL_INVALID。
• solver.Value(var)：提取变量的最终赋值。

模型构建核心要素

变量类型

除了 NewIntVar，CP‑SAT 还支持：

约束类型一览

线性约束
直接使用加、减与比较运算符。

model.Add(3*x + 2*y <= 20)
model.Add(x + y + z == 10)

全局约束（高内聚、高效率）

• AddAllDifferent(variables) – 所有变量取不同值。
• AddElement(index, array, target) – 实现数组索引：array[index] == target。
• AddMultiplicationEquality(target, [a,b]) – target = a * b（乘积约束）。
• AddCircuit(arcs) – 路径约束，常用于 TSP。
• AddCumulative(…) – 资源累积约束，用于调度。

逻辑约束
OR‑Tools 支持将布尔变量组合成逻辑表达式。

# 若 b 为 True，则 x == 5；否则 x == 10
model.Add(x == 5).OnlyEnforceIf(b)
model.Add(x == 10).OnlyEnforceIf(b.Not())

目标函数

若要寻找最优解（而不仅仅是可行解），需要定义目标函数并设置优化方向：

# 最大化 2x + 3y
model.Maximize(2*x + 3*y)
# 或 最小化
model.Minimize(x + y)

然后在求解后检查 status == cp_model.OPTIMAL。

实战示例：车间作业调度

我们将展示一个更贴近实际的应用——把三个作业分配到两台机器上，每台机器同一时间只能处理一个作业，如何最小化总完成时间（makespan）。

已知每个作业的加工时间（分钟）：
作业1：机器A 3分钟，机器B 2分钟
作业2：机器A 2分钟，机器B 4分钟
作业3：机器A 4分钟，机器B 1分钟

from ortools.sat.python import cp_model

jobs = [  # (machine_A_time, machine_B_time)
    (3, 2),
    (2, 4),
    (4, 1)
]
num_jobs = len(jobs)

model = cp_model.CpModel()

# 为每个作业定义在A、B上的开始时间（非负整数）
a_starts = [model.NewIntVar(0, 100, f'a_start_{i}') for i in range(num_jobs)]
b_starts = [model.NewIntVar(0, 100, f'b_start_{i}') for i in range(num_jobs)]

# 每个作业必须先完成A再开始B
for i in range(num_jobs):
    model.Add(b_starts[i] >= a_starts[i] + jobs[i][0])

# 机器A：三个作业间互不重叠（使用间隔变量）
a_intervals = []
for i in range(num_jobs):
    duration = jobs[i][0]
    interval = model.NewIntervalVar(a_starts[i], duration, a_starts[i] + duration, f'a_interval_{i}')
    a_intervals.append(interval)

model.AddNoOverlap(a_intervals)

# 机器B同理
b_intervals = []
for i in range(num_jobs):
    duration = jobs[i][1]
    interval = model.NewIntervalVar(b_starts[i], duration, b_starts[i] + duration, f'b_interval_{i}')
    b_intervals.append(interval)

model.AddNoOverlap(b_intervals)

# 目标：最小化所有作业完成B的最大时间
makespan = model.NewIntVar(0, 200, 'makespan')
for i in range(num_jobs):
    model.Add(makespan >= b_starts[i] + jobs[i][1])
model.Minimize(makespan)

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

if status == cp_model.OPTIMAL:
    print(f'最小总时间: {solver.Value(makespan)} 分钟')
    for i in range(num_jobs):
        print(f'作业{i}: A[{solver.Value(a_starts[i])}→{solver.Value(a_starts[i])+jobs[i][0]}) '
              f'B[{solver.Value(b_starts[i])}→{solver.Value(b_starts[i])+jobs[i][1]})')

关键点解读

• NewIntervalVar(start, size, end, name)：创建一个区间变量，用于表示一个固定长度的活动。
• AddNoOverlap(interval_list)：禁止区间重叠，直接表达了“机器同时只能做一个作业”的约束。
• 目标 makespan 约束为所有作业结束于B的最晚时间，通过最小化 makespan 找到最优调度。

高级技巧与调优

设置求解器参数

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10.0   # 限时 10 秒
solver.parameters.num_search_workers = 8       # 并行搜索线程数
solver.parameters.log_search_progress = True   # 打印日志

回调与解观察

使用 CpSolverSolutionCallback 可在搜索过程中实时获取中间解（例如当找到改进解时保存）：

class MyCallback(cp_model.CpSolverSolutionCallback):
    def on_solution_callback(self):
        print('发现新解，目标值=', self.ObjectiveValue())

solver = cp_model.CpSolver()
solver.SolveWithSolutionCallback(model, MyCallback())

使用假设进行假设推理

假设代表一种临时的条件赋值，可在不修改模型的情况下探索后果：

solver.SolveWithAssumptions(model, [x == 5])   # 强制 x=5 求解