ortools

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

Google OR-Tools - Combinatorial Optimization

Google OR-Tools - 组合优化

OR-Tools provides specialized solvers for hard combinatorial problems. Its crown jewel is the CP-SAT solver, which uses Constraint Programming and Satisfiability techniques to find optimal solutions for scheduling and resource allocation problems that are impossible for standard linear solvers.

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

When to Use

适用场景

Vehicle Routing (VRP): Finding the best paths for a fleet of vehicles to deliver goods.
Scheduling: Creating shift rosters, project timelines, or job-shop schedules.
Bin Packing: Fitting objects of different sizes into a finite number of bins.
Knapsack Problem: Selecting items to maximize value within a weight limit.
Linear Programming (LP): Standard resource allocation with continuous variables.
Integer Programming (MIP): Optimization where variables must be whole numbers (e.g., "number of machines to buy").
Network Flows: Calculating max flow or min cost in a graph.

车辆路径规划（VRP）：为车队规划最优送货路线。
调度问题：生成班次表、项目 timeline 或作业车间调度计划。
装箱问题：将不同尺寸的物品装入有限数量的容器中。
背包问题：在重量限制内选择物品以最大化总价值。
线性规划（LP）：带连续变量的标准资源分配问题。
整数规划（MIP）：变量必须为整数的优化问题（例如“需要购买的机器数量”）。
网络流：计算图中的最大流或最小成本。

Reference Documentation

参考文档

Official docs: https://developers.google.com/optimization
GitHub: https://github.com/google/or-tools
Search patterns:

cp_model.CpModel

pywraplp.Solver

routing_enums_pb2

AddConstraint

官方文档：https://developers.google.com/optimization
GitHub仓库：https://github.com/google/or-tools
常用搜索关键词：

cp_model.CpModel

pywraplp.Solver

routing_enums_pb2

AddConstraint

Core Principles

核心原则

Modeling vs. Solving

建模与求解分离

OR-Tools separates the Definition of the problem (Variables, Constraints, Objective) from the Solver engine. You build a model, then pass it to a solver instance.

OR-Tools 将问题的定义（变量、约束、目标函数）与求解器引擎分离。你只需构建模型，再将其传入求解器实例即可。

CP-SAT (Constraint Programming)

CP-SAT（约束规划）

The most modern and recommended solver for discrete problems. Critical Note: CP-SAT works with integers only. If you have floating-point numbers (like

0.5

), you must scale them (e.g., multiply by 100 and work with integers).

这是针对离散问题最现代、最推荐使用的求解器。重要提示：CP-SAT仅支持整数运算。如果你需要处理浮点数（如

0.5

），必须对其进行缩放（例如乘以100后以整数形式处理）。

Status Codes

状态码

After solving, always check the status. It can be

OPTIMAL

FEASIBLE

(a solution found, but maybe not the best),

INFEASIBLE

(impossible to solve), or

LIMIT_REACHED

求解完成后，务必检查状态码。状态码包括

OPTIMAL

（最优解）、

FEASIBLE

（找到可行解，但可能不是最优）、

INFEASIBLE

（问题无解）或

LIMIT_REACHED

（达到求解限制）。

Quick Reference

快速参考

Installation

安装

bash

pip install ortools

bash

pip install ortools

Standard Imports

标准导入

python

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

python

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

Basic Pattern - CP-SAT Solver (Integer Logic)

基础示例 - CP-SAT求解器（整数逻辑）

python

from ortools.sat.python import cp_model

python

from ortools.sat.python import cp_model

1. Create the model

1. 创建模型

model = cp_model.CpModel()

2. Define variables: NewIntVar(lower_bound, upper_bound, name)

2. 定义变量：NewIntVar(下界, 上界, 变量名)

x = model.NewIntVar(0, 10, 'x') y = model.NewIntVar(0, 10, 'y')

3. Add constraints

3. 添加约束

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

4. Define Objective

4. 定义目标函数

model.Maximize(x + 2 * y)

5. Solve

5. 求解

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

if status == cp_model.OPTIMAL: print(f'x = {solver.Value(x)}, y = {solver.Value(y)}')

undefined

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

if status == cp_model.OPTIMAL: print(f'x = {solver.Value(x)}, y = {solver.Value(y)}')

undefined

Critical Rules

重要规则

✅ DO

✅ 建议做法

Use CP-SAT for Discrete Tasks - It is significantly faster than MIP solvers for scheduling and logic-heavy problems.
Scale your Floats - Since CP-SAT is an integer solver, convert
```
1.25
```
to
```
125
```
and adjust the logic.
Check Status First - Never access variable values if the status is
```
INFEASIBLE
```
.
Use AddElement for indexing - To use a variable as an index in an array, use the specialized constraint
```
model.AddElement
```
.
Set a Time Limit - For complex problems, use
```
solver.parameters.max_time_in_seconds = 60.0
```
to get the best possible solution within a minute.
Verify with Value() - Access results using
```
solver.Value(var)
```
, not the variable object itself.

离散任务优先使用CP-SAT - 在调度和逻辑密集型问题上，它比MIP求解器快得多。
缩放浮点数 - 由于CP-SAT是整数求解器，需将
```
1.25
```
转换为
```
125
```
并调整逻辑。
先检查状态码 - 如果状态为
```
INFEASIBLE
```
，绝不要访问变量值。
使用AddElement进行索引 - 若要将变量用作数组索引，请使用专用约束
```
model.AddElement
```
。
设置时间限制 - 对于复杂问题，使用
```
solver.parameters.max_time_in_seconds = 60.0
```
以在一分钟内获取最佳可行解。
用Value()获取结果 - 通过
```
solver.Value(var)
```
访问结果，而非直接使用变量对象。

❌ DON'T

❌ 禁止做法

Don't use Python if in Constraints - You cannot use
```
if x > 5: model.Add(...)
```
. Use boolean implications (
```
OnlyEnforceIf
```
).
Don't use non-linear math - CP-SAT and LP solvers don't support
```
x * y
```
(where both are variables) or
```
sin(x)
```
. For
```
x * y
```
, you need specialized linearization or piecewise approximations.
Avoid huge domains - Defining a variable with a range of 0 to 1,000,000,000 can slow down the solver. Narrow the bounds as much as possible.

在约束中使用Python条件语句 - 不能使用
```
if x > 5: model.Add(...)
```
，应使用布尔蕴含（
```
OnlyEnforceIf
```
）。
使用非线性运算 - CP-SAT和LP求解器不支持
```
x * y
```
（x和y均为变量）或
```
sin(x)
```
。对于
```
x * y
```
，你需要专门的线性化或分段近似处理。
避免过大的变量域 - 定义范围为0到10亿的变量会大幅减慢求解速度，应尽可能缩小变量的上下界。

Anti-Patterns (NEVER)

反模式（绝对避免）

python

from ortools.sat.python import cp_model

python

from ortools.sat.python import cp_model

❌ BAD: Using standard Python logic inside the model

❌ 错误：在建模阶段使用标准Python逻辑

if solver.Value(x) > 5: # ❌ Value() is not available during modeling!

if solver.Value(x) > 5: # ❌ 建模阶段无法调用Value()!

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

❌ 错误：在CP-SAT中使用浮点变量

x = model.NewIntVar(0, 1.5, 'x') # ❌ Error!

x = model.NewIntVar(0, 1.5, 'x') # ❌ 报错!

✅ GOOD: Scaling

✅ 正确：缩放处理

x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150 represents 1.50

x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150代表1.50

undefined

undefined

Linear Programming (pywraplp)

线性规划（pywraplp）

Resource Allocation (Continuous Variables)

资源分配（连续变量）

python

from ortools.linear_solver import pywraplp

python

from ortools.linear_solver import pywraplp

Create solver with GLOP backend (Google Linear Optimization Package)

使用GLOP后端创建求解器（Google线性优化包）

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

约束：x + 2y <= 14

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

Objective: Maximize 3x + 4y

目标函数：最大化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()}')

undefined

objective = solver.Objective() objective.SetCoefficient(x, 3) objective.SetCoefficient(y, 4) objective.SetMaximization()

solver.Solve() print(f'解决方案: x={x.solution_value()}, y={y.solution_value()}')

undefined

Vehicle Routing (VRP)

车辆路径规划（VRP）

The Logistics Engine

物流引擎示例

python

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

python

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

def solve_vrp():
    # 1. 距离矩阵（各地点间的距离）
    data = {'distance_matrix': [[0, 10, 20], [10, 0, 15], [20, 15, 0]],
            'num_vehicles': 1, 'depot': 0}
    
    # 2. 初始化索引管理器和路径规划模型
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)
    
    # 3. 创建距离回调函数
    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. 求解
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    return solution

Constraint Programming: Scheduling

约束规划：调度

Job-Shop Example (Tasks with dependencies)

作业车间调度示例（带依赖的任务）

python

model = cp_model.CpModel()

python

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])

undefined

model.AddNoOverlap([interval_var1, interval_var2, interval_var3])

undefined

Practical Workflows

实际工作流

1. Employee Shift Scheduling

1. 员工班次调度

python

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

python

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}')
                
    # 约束：每个班次必须分配给恰好一名员工
    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)
            
    # 约束：每位员工每天最多只能排班一次
    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. Multi-Knapsack (Packing items into bins)

2. 多背包问题（物品装箱）

python

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])

python

def bin_packing(items, bin_capacities):
    model = cp_model.CpModel()
    # x[i, j] = 1 表示物品i被装入容器j
    x = {}
    for i in range(len(items)):
        for j in range(len(bin_capacities)):
            x[i, j] = model.NewBoolVar(f'x_{i}_{j}')
            
    # 约束：每个物品必须被装入恰好一个容器
    for i in range(len(items)):
        model.Add(sum(x[i, j] for j in range(len(bin_capacities))) == 1)
        
    # 约束：容器容量限制
    for j in range(len(bin_capacities)):
        model.Add(sum(x[i, j] * items[i] for i in range(len(items))) <= bin_capacities[j])

Performance Optimization

性能优化

Hinting (Warm Start)

初始提示（热启动）

If you have a good initial guess, provide it to the solver to speed up search.

python

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

如果你有较好的初始猜测，可以将其提供给求解器以加快搜索速度。

python

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

Parallel Solving

并行求解

CP-SAT can use multiple threads to explore different parts of the search tree.

python

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

CP-SAT可以利用多线程同时探索搜索树的不同分支。

python

solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 8 # 使用8个CPU核心

Common Pitfalls and Solutions

常见陷阱与解决方案

Floating Point Math Errors

浮点运算错误

As mentioned, OR-Tools CP-SAT is strictly integer.

python

undefined

如前所述，OR-Tools的CP-SAT仅支持整数运算。

python

undefined

❌ Problem: model.Add(x * 0.1 <= 5)

❌ 问题：model.Add(x * 0.1 <= 5)

✅ Solution:

✅ 解决方案：

model.Add(x <= 50) # Multiply both sides by 10

undefined

model.Add(x <= 50) # 两边同时乘以10

undefined

Infeasible Models

不可行模型

solver.Solve(model)

returns

INFEASIBLE

, it means your constraints are contradictory.

python

undefined

如果

solver.Solve(model)

INFEASIBLE

，说明你的约束条件存在矛盾。

python

undefined

✅ Solution: Use 'Sufficient Assmptions' or 'Constraint Relaxation'

✅ 解决方案：使用“充分假设”或“约束松弛”来定位导致冲突的约束。

to identify which constraint is causing the conflict.

—

undefined

undefined

Symmetry

对称性问题

If items A and B are identical, the solver will waste time checking both "A in Bin 1, B in Bin 2" and "B in Bin 1, A in Bin 2".

python

undefined

如果物品A和B完全相同，求解器会浪费时间同时检查“A在容器1，B在容器2”和“B在容器1，A在容器2”两种情况。

python

undefined

✅ Solution: Add symmetry-breaking constraints

✅ 解决方案：添加对称性破缺约束

model.Add(x_A <= x_B) # Force an ordering

model.Add(x_A <= x_B) # 强制设定顺序

undefined

undefined

Best Practices

最佳实践

Always check solver status before accessing variable values
Scale floating-point values to integers when using CP-SAT
Set time limits for complex problems to get feasible solutions quickly
Use appropriate solver - CP-SAT for discrete, GLOP for continuous LP
Break symmetry in models with identical variables to speed up solving
Narrow variable domains as much as possible for better performance
Use hints when you have good initial guesses
Enable parallel solving for large problems when available
Verify solutions by checking constraints are satisfied
Document your model - variable names and constraint logic

Google OR-Tools is the heavy machinery of the optimization world. It solves the discrete puzzles that power global logistics, airline scheduling, and manufacturing, turning impossible "Trial and Error" into mathematical certainty.

始终先检查求解器状态，再访问变量值
使用CP-SAT时，将浮点数缩放为整数
为复杂问题设置时间限制，以快速获取可行解
选择合适的求解器 - CP-SAT处理离散问题，GLOP处理连续线性规划
为含相同变量的模型添加对称性破缺约束，以加快求解速度
尽可能缩小变量域，提升求解性能
当有较好初始猜测时，使用提示功能
大型问题在条件允许时启用并行求解
验证解决方案，确保所有约束都被满足
为你的模型添加文档 - 包括变量名称和约束逻辑

Google OR-Tools是优化领域的重型工具。它解决支撑全球物流、航空调度和制造业的离散难题，将原本只能靠“反复试错”的问题转化为数学上的确定性解决方案。